Actually, for a ripple-carry adder in base 3+omega, we need to be able to add three single-digit numbers to form a double-digit sum (at which point we have a full-adder circuit). But that's possible, because the set of Eisenstein integers representable with 2 digits contains an order-3 hexagon: #C Copy and paste this into Golly to view the diagram x = 15, y = 17, rule = //3 7.A.A2$2.A.B.B.B.B2$.A.B.B.B.B.B.A2$2.B.B.B.B.B.B.A2$.B.B.B.B.B.B.B2$ A.B.B.B.B.B.B2$.A.B.B.B.B.B.A2$4.B.B.B.B.A2$5.A.A! Best wishes, Adam P. Goucher
Sent: Wednesday, May 16, 2018 at 9:54 AM From: "Adam P. Goucher" <apgoucher@gmx.com> To: math-fun@mailman.xmission.com Subject: [math-fun] Gosper island numerals
On the subject of complex-radix representations, it might be interesting to use base 3+omega with the seven digits:
{0, 1, -1, omega, -omega, omega^2, -omega^2}
where omega is a principal cube-root of unity. (So the digits are 0 together with the sixth roots of unity.)
Everything to the left of the radix-point represents an arbitrary Eisenstein integer. Truncation is very close to rounding to the nearest lattice point (but not quite, because the Gosper island is not exactly a hexagon). And because the hexagonal lattice is the best lattice quantizer, using base-(3+omega) is efficient in terms of mean-squared error between a complex number and the closest representable number (by a certain number of bits).
Other than the 'truncation is almost rounding' property, the utility stems from the fact that the digit set is closed under multiplication, i.e. the result of a single-digit multiplication is itself a single digit (like binary and balanced ternary, and unlike decimal).
Also, like balanced ternary, you can negate a value by simply negating every digit.
The result of two single-digit additions is (up to multiplication by a unit) either 0, 1, 2, or 2+omega. The latter two of these are the double-digit values (1, omega^2) and (1, -1), which makes this more convenient than base-(i-1) in terms of constructing an adder circuit.
Another advert for base 3+omega is that multiplications by sixth roots of unity are practically free, which has applications to Fast Fourier Transforms.
It's tempting to compare the logic gate complexity of base 3+omega against conventional complex addition and multiplication (using a pair of real and imaginary components in fixed-point binary representation). I envisage that 3 physical bits would be used for each digit (labelled 1, omega, omega^2, with the sum of ON bits giving the value of the digit). Negation is just bitwise NOT.
If there's a significant advantage, then this could be applicable to complex matrix multiplication and embedded systems requiring Fourier transforms.
Best wishes,
Adam P. Goucher
Sent: Wednesday, May 16, 2018 at 2:42 AM From: "Lucas, Stephen K - lucassk" <lucassk@jmu.edu> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Who wrote this paper?
More possibilities: negative integer bases are done by Gilbert & Green, 1979, Negative Based Number Systems, Mathematics Magazine, 52(4). Their section on arithmetic can be improved, but the representation in negative bases is beautifully presented. Katai & Szabo, Canonical Number Systems for Complex Integers, prove that base -n+i or -n-i with natural number n can be used to represent Gaussian integers using digits from 0 to n^2. Other bases require other digit sets, which include recent discussion with Joerg Arndt on this list on base 2+i using digits {0,1,-1,i,-i}.
--
Stephen Lucas, Professor Department of Mathematics and Statistics MSC 1911, James Madison University, Harrisonburg, VA 22807 USA Phone 540 568 5104, Fax 540 568 6857, Web http://educ.jmu.edu/~lucassk/ Email lucassk at jmu dot edu (Work) stephen.k.lucas at gmail dot com (Other)
Mathematics is like checkers in being suitable for the young, not too difficult, amusing, and without peril to the state. (Plato)
On May 15, 2018, at 8:54 PM, Henry Baker <hbaker1@pipeline.com<mailto:hbaker1@pipeline.com>> wrote:
Well, I'm not 100% certain, but *someone* must have written a paper *sometime* about positional number systems using an *algebraic* and/or *algebraic integer* radix and integer numerals.
Knuth? Knuth? Anyone? Anyone?
Several interesting things:
If p(r) is the minimal polynomial for r, and deg(p)=n, then we can express r^n in terms of lower powers of r, and thus there is some possible redundancy in the representations.
Also, if n>1, then there are multiple r's satisfying p(r)=0, so we have to relate representations using r and r', s.t. p(r)=p(r')=0.
Clearly, complex number systems of the 1+i type qualify, but I don't recall any such systems with n>2.
Also, cyclotomic polynomials have the same unfortunate property that base-(e^i) numbers have -- namely, it is a lot more difficult to represent large numbers.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com<mailto:math-fun@mailman.xmission.com> https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun