Carry propagation-free number systems and a kind of approximate groups (I)

Avizienis introduced a signed-digit number representation which allows fast, carry propagation-free addition (A. Avizienis, Signed-digit number representation for fast parallel arithmetic, IRE Trans. Comput., vol. EC-10, pp. 389-400, 1961, see also B. Parhami, Carry-Free Addition of Recoded Binary Signed-Digit Numbers, IEEE Trans. Computers, Vol. 37, No. 11, pp. 1470-1476, November 1988.)

Here, just for fun, I shall use a kind of approximate groups to define a carry-free addition-like operation.

1. The hypothesis is: you have three finite sets A, B, K, all sitting in a group G. I shall suppose that the group G is commutative, although it seems that’s not really needed further if one takes a bit of care. In order to reflect this, I shall use  + for the group operation on G, but I shall write M N  for the set of all elements of the form  x + y with x \in M and y \in N.

We know the following about the three (non-empty, of course) sets A, B, K:

  1. B \subset A,
  2. 0 \in B, 0 \in K, A = -A, B = -B, K = -K,
  3. \mid B \mid = \mid K \mid   (where \mid M \mid is the cardinal of the finite set M),
  4. A A B \subset A K  (that’s what qualifies A as a kind of an approximate group).

Let now choose a bijective function \phi: K \rightarrow B and two functions \psi: AAB \rightarrow A and \chi: AAB \rightarrow K such that

(1)   for any x, y \in A and any b \in B we have x+y+b = \psi(x+y+b) + \chi(x+y+b).

______________

2. Let X be the family of functions defined on \mathbb{Z} with values in A, with compact support, i.e. if x: \mathbb{Z} \rightarrow A belongs to X, then only a finite number of k \in \mathbb{Z} have the property that x_{k} = x(k) \not = 0.  The element 0 \in X is defined by x_{k} = 0 for any k \in \mathbb{Z}.  If x \in X with x \not = 0 then ind(x) \in \mathbb{Z} is the smallest index k \in \mathbb{Z} with x_{k} \not = 0.

______________

3.  The structure introduced at 1. allows the definition of an operation * on X. The definition of the operation is inspired from a carry-free addition algorithm.

Definition 1. If both x, y \in X are equal to 0 then x*y = 0. Otherwise, let j \in \mathbb{Z} be the smallest index k such that one of x_{k} or y_{k} is different than 0.  The element z = x*y is defined by the following algorithm:

  1. z_{k} = 0 for any k < j,
  2. let t_{j} = 0k = j. Repeat:

p_{k} = x_{k} + y_{k} + t_{k}

z_{k} = \psi(p_{k})

t_{k+1} = \phi(\chi(p_{k}))

k \rightarrow k+1

______________

4.  We may choose the functions \phi, \psi, \chi such that the operation * is starting to become interesting. Before doing this, let’s remark that:

  • the operation * is commutative as a consequence of the fact that + is commutative,
  • the operation * is conical, i.e. it admits the shift \delta: X \rightarrow X, \delta(x)(k+1) = x_{k} as automorphism ( a property encountered before for dilation structures on ultrametric spaces, see  arXiv:0709.2224  )

Proposition 1.  If the functions \phi, \chi, \psi satisfy the following:

  1. \phi(0) = \chi(0) = \psi(0) = 0
  2. \chi(x) = 0 for any x \in A
  3. \psi(-x) = - \psi(x)\phi(-x) = -\phi(x) for any x \in A A B, \chi(-x) = -\chi(x) for any x \in K,

then (X, *) is a conical quasigroup.

Advertisements

One thought on “Carry propagation-free number systems and a kind of approximate groups (I)”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s