After my binary fingermath stuff, a few people wrote to me to ask about just how binary really works. For someone who does the kinds of crazy stuff that I do, the idea of different number bases is so fundamental that it's easy to forget that most people really don't understand the idea of using different bases.
To start off with, I need to explain how our regular number system works. Most people understand how our numbers work, but don't necessarily understand *why* they're set up that way.
Our number system is *positional* - that is, what a given digit of a number means is dependent on its position in the number. The positions each represent one power of ten, increasing as you go from right to left, which is why our number system is called base-10. You can do positional numbers using any number as the base - each digit will correspond to a power of the base.
So suppose we have a number like 729328. The first position from the right, containing the digit "8" is called position zero, because it tells us how many 100=1s we have. The next position is position 1, or the 101=10s column, because it says how many tens there are (2). And then we have the digit three in position 2, meaning that there are 3 102s = 3 100s, etc. So the number really means 7×105+2×104+9×103+3×102+2×101+8×100 = 7×100,000 + 2×10,000 + 8×1,000 + 3×100 + 2×10 + 8×1. Now let's look at the same kind of thing in base 3, using the number 102120. That's 1×35 + 0×34+2×33+1×32+2×31+0×30 = 1×254+0×81+2×27+1×9+2×3+0×1 = 254 + 54 + 9 + 6 = 323 in base 10.
Normally, to show that we're using a different base, we'd write the numbers with a subscript showing the base - so we'd normally write the binary for 11 as 10112.
To write numbers in bases larger than 10, we have one very small problem, which is that we only have numbers to write digits from 0 to 9, but hex has digits from 0 to 15. The way that we work around that is by using letters of the alphabet: A=10, B=11, C=12, D=13, E=14, F=15, ... So base-16 uses 0-9 and A-F as digits.
Base-8 (octal) and base-16 (hexidecimal, or hex for short) are special to a lot of computer people. The reason for that is that because 8 and 16 are powers of 2, that means that each digit in octal and hexidecimal corresponds exactly to a specific number of binary digits. Every digit in hexidecimal is something between 0 and 15, which corresponds to exactly 4 binary digits. Base-10 doesn't have this property - a digit in base ten takes *between* three and four digits - and that means that you *can't* divide up a string of binary into parts that correspond to decimal digits without looking at the number. With hexidecimal, every hex-digit is 4 binary digits, which is remarkably convenient.
Why would that make a difference? Well, we store data in memory in 8-bit groups called bytes. How big a number can you store in one byte? 255. That's a strange looking number. But what about in hexidecimal? It's the largest number you can write in 2 digits: FF16. It gets worse as you get bigger. If you've got a computer that has bytes of memory numbered using 4 byte addresses, what's the largest memory address? In hex, it's easy to write: FFFFFFFF16. In decimal? 4294967296. The hex numbers are a lot more natural to work with when you're doing something close to the hardware. In modern programming, we rarely use hex anymore, but a few years ago, it was absolutely ubiquitous. I used to be able to do arithmetic in hex as naturally as I can in decimal. Not anymore; I've gotten rusty.
Among computer geeks, there's an old argument that number systems based on powers of two are more natural than others, but I'm not going to get into *that* basket of worms. If you're interested, take a look at the [Intuitor Hex Headquarters](http://www.intuitor.com/hex/).
- Log in to post comments
More like this
http://www.intuitor.com/hex/switch.html
"Clearly finger-chauvinism is arbitrary."
Any particular reason you're not spelling it "hexadecimal"?
I've always had a fondness for base (-2). Yes, all the positional stuff works, and then you don't even need negative numbers. (Of course, finger math isn't so easy anymore, though).
My favorite binary line:
"There are 10 kinds of people in the world:
Those who understand binary,
and those who don't."
I'm also a bit fond of "You and dead people understand hex. How many people understand hex?"
Ahcuah - I like playing around with off-kilter bases. What digits do you use in base(-2)?
"You and dead people understand hex. How many people understand hex?" would be a bit easier to parse if it read "You and DEAD people understand hex. How many people understand hex?"
But of course that's the point...
Okay, I've got to say it. Number systems based on powers of two are *not* more natural. There are a lot of nice reasons to use base 10.
First off, of course, is the fact that we happen to have 10 digits. That's simply a coincidence of anatomy. But 10 turns out to be a remarkably convenient.
10 is even. That means that we can tell if a number is a multiple of two by looking only at its last digit--we don't get that benefit with, say, base 7. We also gain this benefit with 5--in general, we gain it with any number that divides the base. But if we recognize that 2 is an especially important number--why else would number bases that are powers of 2 be useful at all--an even base is a necessesity. Powers of two also gain this benefit, of course.
10 is one more than a composite. Why is this important? Well, every number base has a nice divisibility test for the number one less than the base. (Summing the digits of a number in base b is equivalent to reducing modulo b-1.) Any number that divides b-1 inherits this nice divisibility test, by obvious properties of modular arithmetic. This is why we can check for divisibility by 3 by summing the digits. Base 16 is the smallest power of two that shares this property. Base 22 is the next smallest base that shares it.
10 has more than one prime factor. This is useful because we have neat divisibility tests for powers of primes that divide the base. Obviously, no power of 2 shares this benefit.
10 is one less than a prime. This is convenient because we have a divisibility test for the number one more than a base.
So, with all of these conveniences, we can do some quite effective primality testing. The smallest composite that we can't instantly recognize--provided we can easily test for a perfect square--is 91 (=7*13). By way of contrast, the smallest such composite in base 2 is 35 (100011=101*1111). The smallest in base 4 is 77 (1031=13*23). The smallest in octal is only 15 (17=3*5), and the next smallest is 33 (41=3*13). In base 16, we can't recognize 15 (F=3*5), but we'll give 15 the benefit of the doubt as a single-hexit number. The next largest we can't recognize is 77 again (4D=7*B).
The only number base that's better in this regard base 6, which gives tests for 2,3,5 and 7. The smallest hard-to-recognize composite in base 6 (again assuming we can spot perfect squares) is even larger, 143 (399=19*21).
Powers of two have their benefits as bases, but I find that people who think they're "natural" are almost always computer scientists. For computers, of course, powers of two are natural... but that's because computers only have two fingers to add on.
No Friday pathological language blogging for the 13th?
Quaternary usually gets overlooked in these discussions. I've even heard it called a two-bit number system!
Heh, and I wrote that about base 6 without ever having thought about its benefits to finger-arithmetic... wow. I think I'm going to have to start advocating a switch to base 6...
Of course, all this is moot. The reason we don't change number bases is the same reason we don't readily switch languages languages--we'd all need to learn to communicate all over again.
And... I shouldn't write math on too little sleep. In the bit on base 6, 9 is of course the symbol for 10-1 (base 6). Using the usual digits, that should of course read 355=15*21.
Lytefoot - several of your arguments for why 10 is better than 16 are based purely on primality tests. I don't think that's very useful to the everyday joe. The closest thing is the add-up-the-digits bit, which 16 is better at, since 15 is divisible by 3 *and* 5, while 9 is only divisible by 3.
The 'even' bit is quite useful, though. Base 16 is even down to the unit, though! Accurately dividing into fifths, though, is quite difficult, so it's hard to get at the unit in metric measurements. At least in our American base-12 length measurement, the hardest thing I have to do is divide a segment into thirds, which is relatively easy.
While I'm at it, 16 is *also* one less than a prime - 17.
So, it seems the major thing speaking for base 10 is inertia (which, btw, is why I'm *not* for switching to hex ^_^) and "it has more than one prime divisor". Everything else on your list is equalled or exceeded by hex.
Litefoot:
Since we use base 10, it is common sense to use 10 digits. If we used base 16 since the begining of math, we would have 16 digits. You could actually make up your own new digits for bases 11 and higher, but letters were more convienient I guess.
All powers of two are even like base 10, so you can tell just as easy if a given number is odd or even. In binary, numbers ending in 0 are even, ending in 1 are odd. In hex, numbers ending in 0,2,4,6,8,A,C,E, are even.
While I would like a power of 2 number system to be the norm, now that we are more than a few thousand years into using base 10, it just isn't feasable. Everything in the world would have to be changed over.
I think that they should change the way they teach math in schools though. They should teach how number systems work instead of just saying it works and moving on. It wasn't until I took math for computing in college that I really understood math. Learning how binary, octal, and hexadecimal works opens your eyes to how base 10 works.
Nice article, and you're right when you say bases are a common concept for computer scientists :-) I hope organic computer will soon emerge to free us from these.
But for those that already know all that binary stuff, could you go a bit beyond and talk to us about non-integer bases? A friend told me years ago that the most natural base is base e (Euler's number), and that the closes integer base, that is 3, would have been much more efficient for computations than binary. But he wasn't able to explain it to me in the details.
The Babylonians of course invented the first place value number system in about 1700 BCE, which was base 60, which is why we still have sixty minutes in an hour and 360 degrees in a circle. On a mathematical level base 60 has advantages over base 10 and does have some advocates for its introduction. Leibniz first investigated binary at the end of the 17th century.
As far as I know, the only time e is used as a base is as the base of the natural logarithm. I can't even think of how you would count in a non-integer base. I've only seen it as a constant in equations, and as the base of a logarithm. I'm no math genius though, so hopefully someone else can provide more info, if there is any.
Base 1+i. Base phi. Base e. Base pi. Factorial base. Primorial base. So many tangential topics, so little time. References on MathWorld, Wikipedia, and the Online Encyclopedia of Integer Sequences which, you know, can now be automatically coverted to Midi. Pythagorus and music. Relationships between bases and harmony. Or am I anticipating your follow-up pages?
No one ever brings up Base-12 anymore, and how much easier math is in it. Ah well.. Cursed with only 10 fingers I suppose :(
Base-16 has a digit extraction algorithm for Pi; no need to calculate the previous digit anymore BBP Formula (It's unfortunate that one doesn't exist for Base-10)
Xanthir -
Base (-2) still uses 0 and 1. And the positionals are powers of (-2), that is, 1, -2, 4, -8, 16, . . .. Here are a few numbers just to get a feel for it:
0 0
1 1
2 110 (4-2+0)
3 111 (4-2+1)
4 100 (4+0+0)
5 101 (4+0+1)
6 11010 (16-8+0-2+0)
-1 11 (-2+1)
-2 10 (-2+0)
-3 1101 (-8+4+0+1)
-4 1100 (-8+4+0+0)
I notice that the last equation on MathWorld's BBP-Type Formula page is an expression for π2 in terms of the golden ratio φ. Now that made my morning!
I have a deep distrust of teaching different number bases in elementary school math classes, at least as part of the basic curriculum. (Extra credit is a whole other cookie jar.) In first through third grades, I brushed against the leftovers of the "New Math", and I agree with what Richard Feynman had to say about it:
(In the original audio recording, which you can hear on Feynman Volume One, he does mention that computers use base two, so that there's a slight rationale for talking about that -- but even then, does it justify teaching binary in first grade? Studying how computers work using a book like Larry Gonick's Cartoon Guide to the Computer in fourth or fifth grade is a different matter, and much more plausible.)
Of course, the classic line is Tom Lehrer's quip that "Base eight is just like base ten - if you're missing two fingers."
Since we use base 10, it is common sense to use 10 digits.
No, I mean digits. Those wiggly things on the ends of your hands are called digits. We call the symbols we use to represent numbers the same thing, because of the coincidence of anatomy I mention. This is just a coincidence of anatomy... but it's very useful in building intuition in the young. A small child will have clearer insight into the numbers zero through 10 than he will into the numbers zero through 16--unless you sew a few extra fingers on him, heh.
As for primality testing... primality testing itself isn't useful... but multiplication and division are. If you're manually dividing a large number by, say, 15, it's nice to be able to reduce the problem. (Yes, there's a nice algorithm for performing long division... if you have lots of time, and space to write.) Divisibility checks are also quite handy in error-checking multiplication. "I multiplied those seven digit numbers wrong: I started with two multiples of three, but I didn't end up with a multiple of nine."
(Again, probably not a big problem for computer scientists... though I'm generalizing, I'm sure you forget your calculators just like the rest of us.)
Base 16 gains a divisibility-checking algorithm for 5... but only at the cost of an easier-to-use one. (Sum the hexits, vs. inspect the last digit... which seems easier to you?) It gains 17, but it loses 11. 11 is a smaller prime--so we encounter more multiples of 11 in our day-to-day life. The first multiple of 17 that we don't have another test for (in base 10 or base 16) is 119=17*7 (in hex 77=7*11, of course).
Back in 1999, I was irriated that the impending graphical change in the calendar actually represented the end of the last millenium, rather than the begining of the new. So is there something that necessitates the largest unit of a base system to be represented by two digits? Am I asking a question about zero?
Registering my vote for a discussion of non-integer number bases.
> the classic line is Tom Lehrer's quip...
And since we learned how to perform multiplication with "more primitive visual aids" last week, we're really ready for a rousing rendition of New Math.
If we get to pick, I want to vote for base 12. Yeah, hex may be convenient for representing integers, but at some point you have to start using decimals.
Base 12's advantage on decimals is illusory, though. (I generally write base 12 using digits 0-9 plus T for 10 and E for 11. Hex proponents sometimes prefer A and B.) Yes, you get 1/3 to be nice (because 3 divides 12), but it costs you 1/5, which becomes... err... (need a pencil for this one...) .294712 with all four digits repeating. Maximally periodic--uglier than 1/3 in base 10. (1/n has at most n-1 repeating digits. This is easy to see if you look at the long division.) 7 remains maximally periodic, .186T3512 with all six repeating. 1/E is nice, of course, .112 repeating, but we don't get anything else with period one, since E is prime.
Lytefoot - All right, you have to use a slower test for divisible-by-5, but you get a much faster div-by-8 and div-by-4 test (both become check-last-digit). Div-by-2 is easy in both.
So, the divisibility tests weight in thusly:
Number - decimal - hex - winner
2 - check-last-digit - check-last-hexit - tie
3 - sum-digits - sum-hexits - tie
4 - check-last-two-digits - check-last-hexit - hex
5 - check-last-digit - sum-hexits - decimal
6 - sum-digits & check-last-digit - sum-hexits & check-last-hexit - tie
7 - none - none - tie
8 - check-last-three-digits - check-last-hexit - hex
9 - sum-digits - none - dec
10 - check-last-digit - none - dec
11 - alternate-digits - none - dec
12 - none - none - tie
13 - none - none - tie
14 - none - none - tie
15 - sum-digits & check-last-digit - sum-hexits - hex (barely)
16 - none - check-last-digit - hex
17 - none - alternate-digits - hex
So, that gives... 4 wins to decimal, 4 clear wins to hex, with a *bare* 5th win on 15 (since checking for div by 5 is so easy in decimal). I'd call it an even split.
Now, you must take the other consideration into account, of course. You are correct that 11 is generally a more important divisor than 17. Plus, while they are equal on a straight win-basis, base-10 *does* have more numbers that have a test, even if it's less efficient than hex.
Looking further, it might be better to look simply at the # of good division tests that occur at or under the base, and the simple combinations past the base. By that I mean, one can easily check for some numbers greater than the base by combining the tests for numbers smaller than the base. For example, testing for 15 in base-10 is simply a combination of testing for 3 and 5. Armed with this information, let's do a new comparison with the number of unique tests, and the number of combos we can get out of that.
For 10, we can easily test for 2, 3, 5, 9, and 11. I am purposely excluding 10, as you can combine any other test with a test for any power of the base trivially. Normally all simply combinations would simply be the powerset, which has 25 members, but you have to exclude any combinations which include 3 and 9 (as that produces the same effect as simply testing for 9), as well as any combinations that include 2 and 5 (because that amounts to combining another number with 10, which is purposely excluded here). This gives us 12 combination divisors which can be tested for by combining the simple divisors. For example, one can test for 33 by summing the digits and then alternating adding and subtracting digits. If both tests come up positive, the number is divisible by both 3 and 11, and thus is divisible by 33.
In contrast, for 16 we have 2, 3, 4, 5, 8, 15, and 17. While this is a larger list, several of them suffer from the same problems that 3 and 9 did - you can't test numbers together unless they're coprime (unless one of them is the base). So, we must exclude anything which contains 3 and 5, 3 and 15, 5 and 15, 2 and 4, 2 and 8, or 4 and 8. This gives us 24 combination divisors, so twice as much.
So, you know, it's a little from Column A, a little from Column B.
For reference, and because I computed them, so damnit, I'm gonna share them, here are the combination divisors for 10 and 16 (both lists are in base-10):
(6 15 18 22 33 45 55 66 99 165 198 495)
(6 10 12 20 24 30 34 40 51 60 68 85 102 120 136 170 204 255 340 408 510 680 1020 2040)
Again, these are the numbers that one can easily do division tests with, by combining the respective 'primitive' divisor tests.
The introduction of color into your blog commentary is GREAT, making it easier to follow related text!
Are BASES not related to the MODULO function?
Classically base-3 contains the modulo numbers 0,1,2 then recycles.
Clock-face arithmetic, base-3 would use 1,2,3 then recycle.
In an helical arithmetic, base-3 would use 0,1,2,3 such as the do-re-me-fa-so-la-ti-do in the musical scale MOD[7].
I submit that base 10 already has easy divisibility tests for powers of 2, the big advantage that the two-power bases claim. It's a little harder--it's recursive, and takes a while--but I can do it without writing anything down. Of course, it relies on the fact that dividing by two is easy, so if you can't easily divide by two in your head you could have problems.
So, the algorithm for 2n (for n>=1) goes like this:
Observe the last n digits. Does 2n-1 divide them? (This is the recursive part.)
--No: Then 2n does not divide your number. Exit.
--Yes: Divide the number made up of the last n digits by 2. Does 2n-1 divide the quotient?
----No: 2n divides the original number if the next digit is odd.
----Yes: 2n divides the original number if the next digit is even.
We can use this algorithm to find the highest power of two that divides a number in base 10. Depending on your ability to divide by 2, you should be able to confirm divisibility by at least 32. A similar algorithm can be used for powers of 5, though the check when you retreat to the n+1th digit is a little tougher. The nicest feature is the abort in the recursive step. In general, we can do this for any divisor of the base (including the base itself, though this is trivial.)
Now, if what we intend to do is factor (for example, when we're reducing fractions, or doing long division), we don't need to be able to check divisibility by powers of primes--just be able to divide by them.
If we accept that multiplying and dividing by 2 is easy, that's another nice feature of base 10--we get a simple method for dividing by 5. We can do it by multiplying by 2, then moving the decimal point one left. Likewise we can multiply by 5 by dividing by two and moving the point one right. So 10 an odd primes with which we have easy division.
I wasn't joking about base phi, base e, base pi, and so forth.
http://en.wikipedia.org/wiki/Golden_mean_base
Golden ratio base refers to the use of the golden ratio, the irrational number â1.61803... symbolized by the Greek letter Ï (phi), as the base of a non-standard positional numeral system. It is sometimes referred to as the golden mean base, phi-base, or, colloquially, phinary. Any real number has a standard representation as a base-Ï numeral that uses only the digits 0 and 1, and the digit sequence "11" is avoided. A nonstandard base-Ï numeral with this digit sequence (or with other digits) can always be rewritten in standard form, relying on algebraic properties of the number Ï -- most notably that Ï+1 = Ï2. For instance, 11Ï = 100Ï.
Despite using an irrational number base, all integers have a unique representation as a terminating (finite) base-Ï expansion. Other numbers have standard representations in base-Ï, with rational numbers having recurring representations. These representations are unique, except that numbers with a terminating expansion also have a non-terminating expansion, as they do in base-10; for example, 1=0.99999....
Also, see:
http://en.wikipedia.org/wiki/Balanced_ternary
Balanced ternary is a non-standard positional numeral system, useful for comparison logic. It is a ternary system, but unlike the standard (unbalanced) ternary system, the digits have the values â1, 0, and 1. This combination is especially valuable for ordinal relationships between two values, where the three possible relationships are less-than, equals, and greater-than.
Balanced ternary is counted as follows. (In this example, the symbol 1 denotes the digit â1, but alternatively for easier parsing "â" may be used denote â1 and "+" to denote +1.)...
http://en.wikipedia.org/wiki/Bijective_numeration
Bijective numeration is any numeral system that establishes a bijection between the set of non-negative integers and the set of finite strings over a finite set of digits. In particular, bijective base-k numeration represents a non-negative integer by using a string of digits from the set {1, 2, ..., k}(k ⥠1) to encode the integer's expansion in powers of k. (Bijective base-k numeration is also called k-adic notation, not to be confused with the p-adic number system. Bijective base-1 is also called unary.)...
http://en.wikipedia.org/wiki/Biquinary
Biquinary, meaning 2-5, is used to refer to a 2-5 code. This can be implemented using a 4 bit binary structure. It is used in the software program Abacus, for example.
The first 10 Decimal numbers with the first 10 Biquinary code numbers are: 0 0100001 1 0100010 2 0100100 3 0101000 4 0110000 5 1000001 6 1000010 7 1000100 8 1001000 9 1010000
http://en.wikipedia.org/wiki/Factoradic
In combinatorial mathematics, the factoradic is a specially constructed number. Factoradics provide a lexicographical index for permutations, so they have potential application to computer security. The idea of the factoradic is closely linked to that of the Lehmer code. Dr. James D. McCaffrey has posted an article on MSDN documenting the factoradic index for permutations with supporting code written in C#. The origins of the term 'factoradic' are obscure. In his article he acknowledges Dr. Peter Cameron of Queen Mary, University of London, as having made the original suggestion....
http://en.wikipedia.org/wiki/Fibonacci_coding
In mathematics, Fibonacci coding is a universal code which encodes positive integers into binary code words. All tokens end with "11" and have no "11" before the end. The code begins as follows:
1 11
2 011
3 0011
4 1011
5 00011
6 10011
7 01011
8 000011
9 100011
10 010011
11 001011
12 101011
The Fibonacci code is closely related to Fibonacci representation, a positional numeral system sometimes used by mathematicians. The Fibonacci code for a particular integer is exactly that of the integer's Fibonacci representation, except with the order of its digits reversed and an additional "1" appended to the end.
To encode an integer X:
1. Find the largest Fibonacci number equal to or less than X; subtract this number from X, keeping track of the remainder.
2. If the number we subtracted was the Nth unique Fibonacci number, put a one in the Nth digit of our output.
3. Repeat the previous steps, substituting our remainder for X, until we reach a remainder of 0.
4. Place a one after the last naturally-occurring one in our output.
To decode a token in the code, remove the last "1", assign the remaining bits the values 1,2,3,5,8,13... (the Fibonacci numbers), and add the "1" bits....
http://en.wikipedia.org/wiki/Mixed_radix
Mixed radix numeral systems are non-standard positional numeral systems in which the numerical base varies from position to position. Such numerical representation is advantageous when representing units that are equivalent to each other, but not by the same ratio. For example, 32 weeks, 5 days, 7 hours, 45 minutes, 15 seconds, and 500 milliseconds might be rendered relative to minutes in mixed-radix notation as:
... 3, 2, 5, 7, 45; 15, 500
... 10, 10, 7, 24, 60; 60, 1000
http://en.wikipedia.org/wiki/Quater-imaginary_base
The quater-imaginary numeral system was first proposed by Donald Knuth in 1955, in a submission to a high-school science talent search. It is a non-standard positional numeral system which uses the imaginary number 2i as base. By analogy with the quaternary numeral system, it is able to represent every complex number using only the digits 0, 1, 2, and 3, without a sign....
I have had some online publications of even weirder number bases, but let's start with those above.
My personal favorite base-60 is the Sexigesimal system used in the novel Autonomy: Freedom of Thought.
http://autonomyseries.com/sexagesimal-numerals/
During a real analysis class we were talking about geometric series and convergence. A convergent geometric series can be thought of as a series that always adds a number of a lower order of magnitude than the last number to the running total. So in base 10 if you add 1+.1+.01+.001... this will obviously converge. Now we can think of trying to find the correct number base so that the terms of the series always are an order of magnitude less than the last.
Then the series is typically represented as a Sum from n=0 to infinity of some coefficent times x^n and diverges for abs(x)>1. Instead of x substitue x=1/y and y is the base. so an x>1 means y<1 which would be a base of less than one and that just doesn't seem like it should converge. Thats what I came up with at least. (Another use for noninteger bases like e)
(post got cutt off?)is the base. So an x>1 means y<1 which would be a base of less than one and that just doesn't seem like it should converge. Thats what I came up with at least. (Another use for noninteger bases like e)
so an x>1 means y(less than)1 which would be a base of less than one and that just doesn't seem like it should converge. Thats what I came up with at least. (Another use for noninteger bases like e) (sorry for repeat posting)
Fools! You shall never defeat me!
*disappears in a puff of smoke*
A few citations follow for Knuth's imaginary base number system, and advances since then.
"A imaginary number system"
Full text Pdf (267 KB)
Source Communications of the ACM archive
Volume 3 , Issue 4 (April 1960) table of contents
Pages: 245 - 247
Year of Publication: 1960
ISSN:0001-0782
Author Donald E. Knuth
Case Institute of Technology, Cleveland, OH
Publisher ACM Press New York, NY, USA
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/367177.367233
ABSTRACT
For centuries the decimal number system reigned supreme, except, perhaps, among the Mayan Indians, until the advent of digital computers brought the binary and octal systems into the limelight. This paper introduces another number system which may prove useful for manipulating complex numbers on machines.
CITINGS 5
Mahmoud A. Manzoul, A quaternary complex number CCD adder (abstract only), Proceedings of the 15th annual conference on Computer Science, p.434, February 1987, St. Louis, Missouri, United States
Morton Nadler, Division and square root in the quarter-imaginary number system, Communications of the ACM, v.4 n.4, p.192-193, April 1961
Asger Munk Nielsen , Peter Kornerup, Redundant Radix Representations of Rings, IEEE Transactions on Computers, v.48 n.11, p.1153-1165, November 1999
M. Davio , J. -P. Deschamps, Addition in signed digit number systems, Proceedings of the eighth international symposium on Multiple-valued logic, p.104-113, January 1978, Rosemont, Illinois, United States
Vassil S. Dimitrov , Graham A. Jullien , William C. Miller, Complexity and Fast Algorithms for Multiexponentiations, IEEE Transactions on Computers, v.49 n.2, p.141-147, February 2000
The sequence of last digits in fibonacci numbers is repeated every 60 numbers.
Next to last is repeated every 60^2 numbers.
Third to last every 60^3 numbers.
So all fibonacci numbers are repeating series of defined sequences.
Is this so?
Yes and no. There are repeating cycles, but the period is slightly more complicated: 60, 300, 1500, 15000, 150000 etc. For general bases, these are known as Pisano periods (from MathWorld).