[math-fun] Who wrote this paper?
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.
Henry, There are several papers on the topic, and at least one more currently in preparation. Knuth certainly has his famous base 2i paper, but the most famous algebraic positional system is base golden ratio using digits 0 and 1: Bergman, Mathematics Magazine, 1957. Rousseau (1995 Mathematics Magazine) also spends some time with base ph, and the website http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/phigits.html has more on the topic gathered in one place than any other reference I know. There is a lot of work on so-called “beta expansions”, which is all about representing numbers in irrational bases with a finite number of digits. This goes back to Renyi, 1957, Representations for real numbers and their ergodic properties, but there are lots of recent references, including Ambroz et al, Arithmetics on number systems with irrational bases, Bull. Belg. Math. Soc 2003. You will be pleased (?) to know that the theory of natural numbers and their representation in bases that are the solutions of quadratic equations is the topic of current research by Jim Propp and myself. At the most recent gathering for Gardner, Jim gave a presentation on how to represent natural numbers using digits that are simultaneously correct in base 2 AND base 3. This is equivalent to the carry rule (how to manipulate digits without changing the number) [+1,-5,+6] using the digits from zero to four. The good news is that the same approach works for any pair of bases that satisfy the same quadratic equation. Including irrationals and complex conjugate pairs. The bad news is that you will have to wait a while for this particular paper, because we are still writing it and trying to understand various special cases. But as a fun teaser, everything you read about base golden ration (1+sqrt(5))/2, it turns out for natural numbers the digits also represent the number in base (1-sqrt(5))/2, which is not something yet discussed in the literature. All of the “metallic means” (see the Wikipedia article with the same name) have nice carry rules [+1,-n,+1] using digits from 0 to n-1, so any natural number has a representation with a finite number of digits these irrational bases, and a simple finite construction exists — and arithmetic can be done on numbers in these forms automatically. But of course, we need to finish writing the paper :-) Steve -- 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...
Hi Steve: But as a fun teaser, everything you read about base golden ration
(1+sqrt(5))/2, it turns out for natural numbers the digits also represent the number in base (1-sqrt(5))/2, which is not something yet discussed in the literature.
It's not precisely the same, but I do dance around this in my expository paper on Jim's early rotor-router work, which appeared as a Mathematical Intelligencer column. Check out https://arxiv.org/abs/math/0501497. --Michael -- Forewarned is worth an octopus in the bush.
Nega-binary (base -2) existed in the mid-1960s, and maybe earlier, as a candidate for arithmetic circuits. Knuth discuses radix i-1 in TAoCP, as a way to represent complex numbers; the virtue is uniform arithemtic circuits, with no need to separately consider real & imaginary parts. He also mentions Fibonacci base; I don't recall if he treats radix phi. Nega-binary can be viewed in concert with other representations such as sign-magnitude w/wo ones-complement, and the various ways of doing floating point. The world seems to have settled on two's complement, with some churn remaining for floating point. Radix pi was at least mentioned c. 1965. Not good for computing with. Polynomials mod P are sometimes extended with sqrt(x). Rich --------- Quoting Henry Baker <hbaker1@pipeline.com>:
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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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...
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
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
Also there is a pretty long discussion about complex bases and automata in my book with Allouche, "Automatic Sequences", in the chapter on representations of integers. And a very large bibliography. Jeffrey Shallit On 5/15/18 9:42 PM, Lucas, Stephen K - lucassk wrote:
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
I should mention that one of the things I figured out in the past few months is that base 3/2 is best understood not in the context of the real numbers but in the context of the 3-adics. When you use the ordinary “(-1)-adic” notion of convergence, it’s unclear whether there’s a natural way to write a fraction like one-half in base 3/2 using the digits 0, 1, and 2, but switch to the 3-adics and you find that every 3-adic number has a unique representation. Something similar happens for base two-and-three with the digits 0 through 5; every rational number has a canonical representation that comes from viewing it 2-adically and 3-adically. But I’m not sure what the appropriate completion of Q_2 x Q_3 is. Jim Propp On Wednesday, May 16, 2018, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
Also there is a pretty long discussion about complex bases and automata in my book with Allouche, "Automatic Sequences", in the chapter on representations of integers. And a very large bibliography.
Jeffrey Shallit
On 5/15/18 9:42 PM, Lucas, Stephen K - lucassk wrote:
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:h baker1@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_cgi-2Dbin_mailman_listinfo_math-2Dfun&d= DwICAg&c=eLbWYnpnzycBCgmb7vCI4uqNEB9RSjOdn_5nBEmmeq0&r=vge6K Oo90zMf7Wx14WFtiQ&m=-cSAzcifT2gAcpAQ5jXhOl3UeeEyJy8ZtMvpdm9a vnk&s=qT-iB-oth1vofGyDa73Tnt2QANLtIbneLTEwlR8L8WQ&e=
_______________________________________________ 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
Thanks Jeffrey, clearly I am going to have to get a copy of your book! There does seem to be quite a scattering of material on positional representation, with some streams of references that run in parallel. It would be nice to be able to see all of them in one place at some point. -- 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 16, 2018, at 5:22 AM, Jeffrey Shallit <shallit@uwaterloo.ca<mailto:shallit@uwaterloo.ca>> wrote: Also there is a pretty long discussion about complex bases and automata in my book with Allouche, "Automatic Sequences", in the chapter on representations of integers. And a very large bibliography. Jeffrey Shallit On 5/15/18 9:42 PM, Lucas, Stephen K - lucassk wrote: 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><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><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://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg... _______________________________________________ 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...
I came up with rational bases of the A/B, A > B >= 1. Long addition is like regular addition, except when a digit becomes >= A, you subtract A from the digit and carry B to the next most significant digit. The value of place P is (A/B)^P. The digits are 0 through A-1. Base A/1 is isomorphic to standard base A. However, A/B = C/D does not imply base A/B = base C/D, for example, base 3/2 is different form base 6/4. For example, counting in base 3/2: 0, 1, 2, 20, 21, 22, 210, 211, 212, 2100, 2101, 2102, 2120, 2121, 2122, 21010, ... I invented this independently, but I would be surprised if I were the first.
The Fibonacci number representation stems from the *difference equation* for Fibonacci numbers, rather than from a traditional positional number system based on phi or 1/phi (or -phi or -1/phi). In my Google Scholar literature search, I found a number of papers investigating different number systems based upon *difference equations* which were inspired by Fibonacci, but essentially nothing about positional number systems based upon phi. At 05:54 PM 5/15/2018, Henry Baker 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.
There are tons of such papers, under the name "beta expansion". It's also discussed in Knuth. On 5/16/18 10:37 AM, Henry Baker wrote:
The Fibonacci number representation stems from the *difference equation* for Fibonacci numbers, rather than from a traditional positional number system based on phi or 1/phi (or -phi or -1/phi).
In my Google Scholar literature search, I found a number of papers investigating different number systems based upon *difference equations* which were inspired by Fibonacci, but essentially nothing about positional number systems based upon phi.
At 05:54 PM 5/15/2018, Henry Baker 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 https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I just discovered that there’s literature on p-adic beta-expansions: https://arxiv.org/pdf/1401.7530.pdf This might interest anyone who wants to understand base 3/2 and base 2-and-3. (I’ve just started reading it.) Jim On Wednesday, May 16, 2018, Jeffrey Shallit <shallit@uwaterloo.ca> wrote:
There are tons of such papers, under the name "beta expansion". It's also discussed in Knuth.
On 5/16/18 10:37 AM, Henry Baker wrote:
The Fibonacci number representation stems from the *difference equation* for Fibonacci numbers, rather than from a traditional positional number system based on phi or 1/phi (or -phi or -1/phi).
In my Google Scholar literature search, I found a number of papers investigating different number systems based upon *difference equations* which were inspired by Fibonacci, but essentially nothing about positional number systems based upon phi.
At 05:54 PM 5/15/2018, Henry Baker 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 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
Henry, my previous post had two references to base phi that are both from the Mathematics Magazine, so pretty accessible. I can send you pdfs if you want. Representation as sums of Fibonacci numbers aren’t strictly a “base” so I didn’t mention them earlier, but they have a long history, and are often called “Zeckendorf notation” after their discoverer. A nice paper that talks about various difference equations and as well as putting continued fractions in the same setting is A.S. Fraenkel, Systems of Numeration, Am. Math. Monthly 92(2) 1985. Blowing my own trumpet, a recent paper of mine presented at the first MOVES conference shows how Zeckendorf representation as a way of representing variable precision integers is particularly good, and is stunningly useful for representing continued fraction partial quotients. I also pull together references on arithmetic in Zeckendorf representation and add a few wrinkles of my own. And it is just enough different from base phi representation to be interesting. A copy can be found at http://educ.jmu.edu/~lucassk/Papers/MOVES%20paper%20revised.pdf There are some lovely relationships between Zeckendorf notation and base phi, but one of the more elegant uses Lucas numbers (no relation!). You can represent numbers as sums of Lucas numbers just like Fibonacci. Then Lucas numbers satisfy L_n= phi^n + (-phi)^n, and you can manipulate this into base phi after dealing with the negative for odd n. Steve -- On May 16, 2018, at 10:37 AM, Henry Baker <hbaker1@pipeline.com<mailto:hbaker1@pipeline.com>> wrote: The Fibonacci number representation stems from the *difference equation* for Fibonacci numbers, rather than from a traditional positional number system based on phi or 1/phi (or -phi or -1/phi). In my Google Scholar literature search, I found a number of papers investigating different number systems based upon *difference equations* which were inspired by Fibonacci, but essentially nothing about positional number systems based upon phi.
Beautiful paper! Thanks! At 09:19 AM 5/16/2018, Lucas, Stephen K - lucassk wrote:
Blowing my own trumpet, a recent paper of mine presented at the first MOVES conference shows how Zeckendorf representation as a way of representing variable precision integers is particularly good, and is stunningly useful for representing continued fraction partial quotients. I also pull together references on arithmetic in Zeckendorf representation and add a few wrinkles of my own. And it is just enough different from base phi representation to be interesting. A copy can be found at http://educ.jmu.edu/~lucassk/Papers/MOVES%20paper%20revised.pdf
participants (8)
-
Adam P. Goucher -
David Wilson -
Henry Baker -
James Propp -
Jeffrey Shallit -
Lucas, Stephen K - lucassk -
Michael Kleber -
rcs＠xmission.com