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 , , , all sitting in a group . I shall suppose that the group 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 , but I shall write for the set of all elements of the form with and .
We know the following about the three (non-empty, of course) sets :
- , , , , ,
- (where is the cardinal of the finite set ),
- (that’s what qualifies as a kind of an approximate group).
Let now choose a bijective function and two functions and such that
(1) for any and any we have .
2. Let be the family of functions defined on with values in , with compact support, i.e. if belongs to , then only a finite number of have the property that . The element is defined by for any . If with then is the smallest index with .
3. The structure introduced at 1. allows the definition of an operation on . The definition of the operation is inspired from a carry-free addition algorithm.
Definition 1. If both are equal to then . Otherwise, let be the smallest index such that one of or is different than . The element is defined by the following algorithm:
- for any ,
- let , . Repeat:
4. We may choose the functions 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 , as automorphism ( a property encountered before for dilation structures on ultrametric spaces, see arXiv:0709.2224 )
Proposition 1. If the functions satisfy the following:
- for any
- , for any , for any ,
then is a conical quasigroup.