[math-fun] When is base 2 not binary
New to the list, so I hope this will go in the right place. But replying to Joerg Arndt’s listing of the first few natural numbers in base 2+i using the digits {0,+1,-1,+i,-i}: The problem with this digit set is that it is not immediately obvious what the rule is to go from number to number adding one. Here is another idea: use the digits {-1,0,1,2,3}. And base 2+i has the carry rule [-1,+4,-5], which says if a digit is 4 or greater, subtract 5 from it, add 4 to the next most significant, subtract one from the next next most significant. One way of verifying this is to see that (-1)(2+i)^{k+2}+4(2+i)^{k+1}-5(2+i)^k=0. For example, with least significant digits on the right, 1 = 1, 2 = 2 3 = 3 4 = (-1)4(-1) = (-1)3(-1)(-1) 5 = (-1)3(-1)0 6 = (-1)3(-1)1 7 = (-1)3(-1)2 8 = (-1)3(-1)3 9 = (-1)3(-1)4 = (-1)23(-1) 10 = (-1)230 11 = (-1)231 12 = (-1)232 13 = (-1)233 14 = (-1)234 = (-1)17(-1) = (-2)52(-1) = (-1)202(-1) and so on. A couple of notes: these digits are exactly the same representing natural numbers in base 2-i as well. This is current (!) joint work with Jim Propp on digits representing numbers in different bases simultaneously. And in base 2+i, you can extend the classic work of Katai and Szabo and represent Gaussian integers in base 2+i. If you limit yourself to nonnegative digits, they proved only -n+i works, not n+i. But a negative digit does the job! Steve
That carry method: neat! The "classic work of Katai and Szabo" I assume is I.\ K\'{a}tai, J.\ Szab\'{o}: Canonical number systems for complex integers, Acta Sci.\ Math.\ (Szeged), vol.~37, no.~3-4, pp.~255-260, (1975). Best regards, jj * Lucas, Stephen K - lucassk <lucassk@jmu.edu> [Apr 27. 2018 09:05]:
New to the list, so I hope this will go in the right place. But replying to Joerg Arndt’s listing of the first few natural numbers in base 2+i using the digits {0,+1,-1,+i,-i}:
The problem with this digit set is that it is not immediately obvious what the rule is to go from number to number adding one. Here is another idea: use the digits {-1,0,1,2,3}. And base 2+i has the carry rule [-1,+4,-5], which says if a digit is 4 or greater, subtract 5 from it, add 4 to the next most significant, subtract one from the next next most significant. One way of verifying this is to see that (-1)(2+i)^{k+2}+4(2+i)^{k+1}-5(2+i)^k=0. For example, with least significant digits on the right, 1 = 1, 2 = 2 3 = 3 4 = (-1)4(-1) = (-1)3(-1)(-1) 5 = (-1)3(-1)0 6 = (-1)3(-1)1 7 = (-1)3(-1)2 8 = (-1)3(-1)3 9 = (-1)3(-1)4 = (-1)23(-1) 10 = (-1)230 11 = (-1)231 12 = (-1)232 13 = (-1)233 14 = (-1)234 = (-1)17(-1) = (-2)52(-1) = (-1)202(-1) and so on.
A couple of notes: these digits are exactly the same representing natural numbers in base 2-i as well. This is current (!) joint work with Jim Propp on digits representing numbers in different bases simultaneously. And in base 2+i, you can extend the classic work of Katai and Szabo and represent Gaussian integers in base 2+i. If you limit yourself to nonnegative digits, they proved only -n+i works, not n+i. But a negative digit does the job!
Steve
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Joerg, Yes, you have the reference correct to Katai & Szabo. If you read their proof carefully, you discover that they essentially use a carry rule to represent a Gaussian integer in base -n+i, and prove existence and uniqueness. But explicitly writing things in terms of a carry rule makes number conversion and arithmetic much easier to deal with. I must admit, after looking back at your list of representations in base 2+i using {1,-1,i,-1,0}, I’m intrigued at how you came up with the digits. It is far from obvious, and the number of digits going up then down is bizarre! Steve
On Apr 27, 2018, at 3:55 AM, Joerg Arndt <arndt@jjj.de> wrote:
That carry method: neat!
The "classic work of Katai and Szabo" I assume is I.\ K\'{a}tai, J.\ Szab\'{o}: Canonical number systems for complex integers, Acta Sci.\ Math.\ (Szeged), vol.~37, no.~3-4, pp.~255-260, (1975).
Best regards, jj
* Lucas, Stephen K - lucassk <lucassk@jmu.edu> [Apr 27. 2018 09:05]:
New to the list, so I hope this will go in the right place. But replying to Joerg Arndt’s listing of the first few natural numbers in base 2+i using the digits {0,+1,-1,+i,-i}:
The problem with this digit set is that it is not immediately obvious what the rule is to go from number to number adding one. Here is another idea: use the digits {-1,0,1,2,3}. And base 2+i has the carry rule [-1,+4,-5], which says if a digit is 4 or greater, subtract 5 from it, add 4 to the next most significant, subtract one from the next next most significant. One way of verifying this is to see that (-1)(2+i)^{k+2}+4(2+i)^{k+1}-5(2+i)^k=0. For example, with least significant digits on the right, 1 = 1, 2 = 2 3 = 3 4 = (-1)4(-1) = (-1)3(-1)(-1) 5 = (-1)3(-1)0 6 = (-1)3(-1)1 7 = (-1)3(-1)2 8 = (-1)3(-1)3 9 = (-1)3(-1)4 = (-1)23(-1) 10 = (-1)230 11 = (-1)231 12 = (-1)232 13 = (-1)233 14 = (-1)234 = (-1)17(-1) = (-2)52(-1) = (-1)202(-1) and so on.
A couple of notes: these digits are exactly the same representing natural numbers in base 2-i as well. This is current (!) joint work with Jim Propp on digits representing numbers in different bases simultaneously. And in base 2+i, you can extend the classic work of Katai and Szabo and represent Gaussian integers in base 2+i. If you limit yourself to nonnegative digits, they proved only -n+i works, not n+i. But a negative digit does the job!
Steve
_______________________________________________ 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 https://urldefense.proofpoint.com/v2/url?u=https-3A__mailman.xmission.com_cg...
* Lucas, Stephen K - lucassk <lucassk@jmu.edu> [Apr 28. 2018 09:09]:
Joerg,
Yes, you have the reference correct to Katai & Szabo. If you read their proof carefully, you discover that they essentially use a carry rule to represent a Gaussian integer in base -n+i, and prove existence and uniqueness. But explicitly writing things in terms of a carry rule makes number conversion and arithmetic much easier to deal with.
Thanks!
I must admit, after looking back at your list of representations in base 2+i using {1,-1,i,-1,0}, I’m intrigued at how you came up with the digits. It is far from obvious, and the number of digits going up then down is bizarre!
I am doing this in a truly brain-dead way: testing every possible digit! Here is my (UGLY) pari/gp code to do this: ----------- to_rdx(n, rx, dg)= /* convert n into radix rx expansion using digits given in dg[] */ { my(d, t, v, ct, i); i = 1; v = vector(30); /* vector of digits, must be long enough */ while ( n != 0, for (j=1, #dg, \\ for each digit d... \\ test whether denom((n-d)/rx)==1: d = dg[j]; t = (n - d) / rx; dt = denominator(t); if ( dt == 1, v[i] = d; i += 1; n = t; break(); ); \\ no digit worked: if ( j==#dg, error(" radix rx and digit set dg[] are not compatible") ); ); ); v = vector(i-1, k, v[k]); /* reverse digits */ return(v); } /* ----- */ from_rdx(v, rx, dg)= /* inverse of to_rdx(), for testing */ { return( sum(j=1, #v, v[j] * rx^(j-1) ) ); } \\ Our parameters: rx=+2+I; dg=[0,+1,-1,+I,-I]; { for (n=-33, 125, x = n; v=to_rdx(x, rx, dg); m=from_rdx(v, rx, dg); print(x,": ",v); if ( x!=m, error("Epic fail!") ); ); } ----------- Oh, there is s reference in that file: \\ From: rcs@xmission.com \\ To: math-fun@mailman.xmission.com \\ Subject: Re: [math-fun] Converting numbers with complex bases \\ cf. Message-ID: <20110713000524.2e83jckd4cgw400g@webmail.xmission.com> The message my code seems to refer to is this one: -----------
Date: Tue, 12 Jul 2011 12:51:50 -0400 From: Andy Latto <andy.latto@pobox.com> To: math-fun <math-fun@mailman.xmission.com> Reply-To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Converting numbers with complex bases X-Spam-Score: -3.3 (---)
On Tue, Jul 12, 2011 at 11:22 AM, Kerry Mitchell <lkmitch@gmail.com> wrote:
Hi,
Using the digits {0, 1} and the complex base -1+i, it's straightforward to show that 1010 = 1+3i. Is there an easy way to go backward? That is, given a complex number in the form a+bi, recover its "binary" representation? I'm immediately interested in the case for bases -1+i and -1-i (digits {0, 1}), but also interested in the general case.
The standard procedure for converting a number to another base works fine. If we want to express a number N in base B, divide N by B, finding Q and R such that
(*) N = B.Q + R
where R is a digit. Then find the base-B representation of Q, and add an R on the end. If (*) always has a solution, then any number can be represented in that base with that digit set. If the solution of (*) is always unique, the representation is unique.
Andy
Best regards, jj
Steve
[...]
Joerg has told us that he found the digits in base 2+i by brute force searching through all the digits. So I have managed to derive a way of finding the digits using a carry rule approach. This is surprisingly building on current research on representing Gaussian integers with an undergraduate student, that we are hoping to submit by the end of the summer. Katai and Szabo showed you can represent a+ib in base -n+i using digits 0 to n^2. My student discovered that base 1+i can be used with digits 0 and 1 except for occasionally a leading digit i, and later I found that digits -1 and 0 work as well. Base n+i with negative digits appears to work. In base b we have the carry rule [+1,-b] saying if we subtract b from one digit we add one to the next most significant, being how positional notation works. In base 2+i, the carry rule is [+1,-2-i], which is great to reduce numbers where the real part is bigger than the imaginary part. But in other cases we will want to reduce the imaginary part more, so times i we get the carry rule [+i,1-2i]. We can then alternate applying these carry rules to reduce a digit to a valid digit, and have a new digit in the next position to simplify. By the way, this is the first time I’ve attempted to use a carry rule with digits that aren’t a sequence of integers, I’m kind of surprised it works. For example, start with 14, are as a list of digits, (14). Applying the first carry rule 7 times gives us digits (most significant to the left) (7,-7i). Second carry rule (-3) times gives (7-3i,-3-i), then first carry rule times (-1) gives (6-3i,-1). Continuing, we get the sequence (3,-6i,-1), (3-3i,-3,-1), (2-3i,-1+i,-1), (2-2i,-i,-1), (1,-3i,-i,-1), (1-i,-1-i,-i,-1), (-i,1,-1,-1). This also gives us an approach to do arithmetic with these digits. Just add the digits then apply carry rules to reduce them back to the required set. Since possible digits after addition are +/- 1 +/- i, one carry rule application might be all you need. Unfortunately, this is a lot of applications of the carry rule. I think I have come up with an approach that works out how many applications of the two carry rules are needed at every step, identifying the next digit immediately and the carry. It uses modular arithmetic to choose the correct remainder to keep carries as Gaussian integers, which identifies {0,1,-1,i,-i} as necessary. It also proves uniqueness, but existence requires a proof that the process converges. But that should work out fine. Joerg also referenced back to the question of representing a+ib in base -1+i using digits 0 and 1. This goes back to Penney (A “binary” system for complex numbers, Journal of the ACM 12(2) 1965) with a horrible construction based on (-1+i)^4=-4 and lots of special cases. Jamil (The complex binary number system, IEEE Potentials 20(5) 2002) did it slightly better, but still horrible. Using the carry approach, this is almost trivial, and directly from my current research paper: start with a+ib = (a+b)+(b)(-1+i), so digits (b,a+b). Then the carry rule for base -1+i over three digits can be proven to be [+1,+2,+2], so apply to the rightmost digit to make it 0 or 1, then keep applying the carry rule right to left and you get the digits. Steve
And now I probably need to retract some of my “discovery,” because much of it has been done by William Gilbert of Waterloo. He has a whole set of research papers on fractal geometry and complex bases, and if you are interested, please check out his manuscript (unpublished but dated 2002) at https://www.math.uwaterloo.ca/~wgilbert/Research/CxBases/CxBases.html His section 4 shows how to convert to a Gaussian integer to a complex base, and what he calls a “clearing algorithm” is exactly the idea of a carry rule. The only novelty of my approach over Gilbert’s is that I allow for a carry rule with Gaussian integers, which makes base 2+i easier to work with. Unfortunately, Gilbert references: M. DAVIO, J. P. DESCHAMPS AND C. GOSSART, Complex arithmetic, Philips M. B. L. E. Research Lab. Report R369 (May 1978) Brussels. He states that they study base 1+2i and its arithmetic, which may be what I did in base 2+i, and so nothing here is new at all! Unfortunately, I don’t have access to a Phillips Research Lap report to find out… 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 Apr 28, 2018, at 11:52 AM, Lucas, Stephen K - lucassk <lucassk@jmu.edu<mailto:lucassk@jmu.edu>> wrote: Joerg has told us that he found the digits in base 2+i by brute force searching through all the digits. So I have managed to derive a way of finding the digits using a carry rule approach. This is surprisingly building on current research on representing Gaussian integers with an undergraduate student, that we are hoping to submit by the end of the summer. Katai and Szabo showed you can represent a+ib in base -n+i using digits 0 to n^2. My student discovered that base 1+i can be used with digits 0 and 1 except for occasionally a leading digit i, and later I found that digits -1 and 0 work as well. Base n+i with negative digits appears to work. In base b we have the carry rule [+1,-b] saying if we subtract b from one digit we add one to the next most significant, being how positional notation works. In base 2+i, the carry rule is [+1,-2-i], which is great to reduce numbers where the real part is bigger than the imaginary part. But in other cases we will want to reduce the imaginary part more, so times i we get the carry rule [+i,1-2i]. We can then alternate applying these carry rules to reduce a digit to a valid digit, and have a new digit in the next position to simplify. By the way, this is the first time I’ve attempted to use a carry rule with digits that aren’t a sequence of integers, I’m kind of surprised it works. For example, start with 14, are as a list of digits, (14). Applying the first carry rule 7 times gives us digits (most significant to the left) (7,-7i). Second carry rule (-3) times gives (7-3i,-3-i), then first carry rule times (-1) gives (6-3i,-1). Continuing, we get the sequence (3,-6i,-1), (3-3i,-3,-1), (2-3i,-1+i,-1), (2-2i,-i,-1), (1,-3i,-i,-1), (1-i,-1-i,-i,-1), (-i,1,-1,-1). This also gives us an approach to do arithmetic with these digits. Just add the digits then apply carry rules to reduce them back to the required set. Since possible digits after addition are +/- 1 +/- i, one carry rule application might be all you need. Unfortunately, this is a lot of applications of the carry rule. I think I have come up with an approach that works out how many applications of the two carry rules are needed at every step, identifying the next digit immediately and the carry. It uses modular arithmetic to choose the correct remainder to keep carries as Gaussian integers, which identifies {0,1,-1,i,-i} as necessary. It also proves uniqueness, but existence requires a proof that the process converges. But that should work out fine. Joerg also referenced back to the question of representing a+ib in base -1+i using digits 0 and 1. This goes back to Penney (A “binary” system for complex numbers, Journal of the ACM 12(2) 1965) with a horrible construction based on (-1+i)^4=-4 and lots of special cases. Jamil (The complex binary number system, IEEE Potentials 20(5) 2002) did it slightly better, but still horrible. Using the carry approach, this is almost trivial, and directly from my current research paper: start with a+ib = (a+b)+(b)(-1+i), so digits (b,a+b). Then the carry rule for base -1+i over three digits can be proven to be [+1,+2,+2], so apply to the rightmost digit to make it 0 or 1, then keep applying the carry rule right to left and you get the digits. Steve _______________________________________________ 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...
participants (2)
-
Joerg Arndt -
Lucas, Stephen K - lucassk