[go: up one dir, main page]

  home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics
 border
 border

Final Answers
© 2000-2021   Gérard P. Michon, Ph.D.

Numbers & Numeration

 Carl Friedrich Gauss 
 1777-1855 To what heights would science now be raised    
if Archimedes had made that discovery
 !    
Carl Friedrich Gauss (1777-1855)    
[ about the positional system of numeration ]
 Michon
 
 
 border
 border

See also:

Related Links (Outside this Site)

Number systemsMath 750J  (Wichita State University, 1999 & 2000).
Bijective Numeration  (positional system without a zero digit).
Negative radix  positional number system.

Babylonian numbers (4:59)  Eleanor Robson  (Cambridge,  2011-03-18).
The Maya Base-20 Number System (10:45)  Jill Britton  (2011-01-12).
Russian Binary Multiplication (6:49)  Johnny Ball  (Numberphile, 2020-02-04).
Shadok quaternary numerationGa Bu Zo Meu  (French TV broadcast)
We Might Use Different Numbers  (11:53)  by  Jade  (Up and Atom, 2020-04-18).

 
border
border

Numeration Systems & Computations


(2002-05-22)   [Anonymous query collected by Site's search engine.]
If you multiply together all the odd numbers from 1 to 999, what will be the final digit? and why?

The answer is 5.  As the product of a number ending with 5 into any odd number ends in a 5,  so does the product of many odd numbers if at least one of them ends in a 5.  Let's investigate a slightly less trivial question:

What's the final digit of the product of all the odd numbers not divisible by 5 from 1 to 999?

This is an example of what's called modular arithmetic: The remainder in the division by some fixed modulus of a sum, a difference or a product depends only on the remainders for both operands. Here, the modulus is 10 and each remainder is simply equal to the last decimal digit of the number involved.

So, the product of 4 decimal numbers ending with 1, 3, 7 and 9 will end with 9.  If you multiply together an even number of such products, the result ends in a 1  (because the product of two factors ending with 9 ends in a 1).

As our product of 400 factors is obtained as the product of 100 such 4-tuples, its final digit is thus 1 as well.

How do I find the last [least significant] digits of such huge numbers?

Modular arithmetic is, again, the key:  If you want the last 5 digits of a product, use modular arithmetic modulo 100000. A regular pocket calculator with 10-digit accuracy will give an exact result for the product of any pair of two 5-digit numbers, which is what any integer reduces to modulo 100000.  That's all you need to find the last 5 digits of the above products of 500 or 400 factors.  With less modest means, we found that...

  • The above product of 500 factors ends with: ...821809277089697420848324327380396425724029541015625.
  • The above product of 400 factors ends with: ...251632034302682442928182392469846896720096892926001.
What about the leading digits?   [most significant digits]

If you want a few leading digits, as well as the number of digits in the result, the easiest way is to compute the decimal logarithm of such a huge product as the sum of the decimal logarithms of its factors. For the 500-factor product, we find a decimal logarithm of 1283.0032378550076961..., corresponding to a 1284-digit number starting with 100748329763750854004...  For the 400-factor product, we find a decimal logarithm of 1026.28235200247947115..., corresponding to a 1027-digit number starting with 1915808088370632042699972791343618517...

We may summarize both of the above approaches for either product thusly:
500-factor product of 1284 digits:  10074832976375... ...724029541015625.
400-factor product of 1027 digits:  19158080883706... ...720096892926001.


(2013-07-10)   Leading digit(s) of  insanely  large numbers.
It's usually impossible to determine the logarithms of  huge  numbers.

As discussed above,  modular arithmetic can be used to work out the least significant digits of numbers defined in arithmetical terms.  That may remain true even when their decimal lengths are too large to be described by common methods.  For example the last digits of  Graham's number  are:

...2464195387

What's the leading digit of Graham's number?  I don't know and I'm convinced nobody else does either.  What's for sure is that the straight logarithmic approach from the previous section is of no use at all, because the leading digits of a number are determined by the  fractional part  of its logarithm.  The logarithm of an N-digit number must be known to a precision of at least  log N  digits for this fractional part to be known at all.  In the case of Graham's number,  log N  is far greater than the information that can be stored in the entire observable universe!

To the best of my knowledge, the only  truly huge  numbers whose leading digits are known have definitions explicitely involving powers of ten.  For example, if  N  is any integer greater than  3  (N could be Graham's number)  then the leading digits of the following factored number are  195603290000...

2N . 5N . 19 . 59 . 17449


Iggy (2004-03-31; e-mail)
What two integers without zero digits have a product of 1000 000 000 ?

Answer:  512 ´ 1953125   =   1000000000.

The first number is the ninth power of 2, the second is the ninth power of 5.  This pair is the only [positive] solution, because neither factor could have both a 2 and a 5 in its prime factorization, or else it would be a multiple of 10 and would thus have a 0 as its last digit, which is ruled out.

Generalization :

We may wonder what powers of 10 are products of two integers without any zero digits.  For large numbers, this is very unlikely because there will normally be 10% of zeroes among many random digits...  In fact, there seems to be only 11 possibilities, of which the above is the third largest.  Namely:

10 0   =           1 x 1
10 1   =           2 x 5
10 2   =           4 x 25
10 3   =           8 x 125
10 4   =          16 x 625
10 5   =          32 x 3125
10 6   =          64 x 15625
10 7   =         128 x 78125
10 9   =         512 x 1953125
10 18  =      262144 x 3814697265625
10 33  =  8589934592 x 116415321826934814453125

The probability is roughly (0.9)n that the nth power of 10 would yield a solution.  So, the expected number of solutions above the nth power of 10 is roughly  10 (0.9)n.  As we've actually checked that there's no other solution below n = 1500, we can be extremely confident that the above is all there is  (the expected number of remaining solutions is less than 10-67 ).


(Peter of Portland, OR. 2000-10-10)
What is the divisibility rule of 13?
(D. S. of Hurricane, WV. 2000-11-29)
What is the divisibility rule for 7?

Recall that a number is divisible by 3 or 9 iff the sum of its digits is.

More generally, a positive integer and the sum of its digits leave the same remainder when divided by 9.  This can be proved by noticing that the successive powers of 10 are all equal modulo 9  (since 9, 99, 999, 9999, etc. are all divisible by 9).  The other "divisibilty tests" presented below are based on similar considerations.

An integer is divisible by 11 iff the difference between the sum of its odd digits (units, hundreds, etc.) and the sum of its even digits (tens, thousands, etc.) is so divisible.

The  quick tests  of divisibility by 7 or 13 are somewhat more complex. Strangely enough,  these two are very strongly related  (see below for an explanation).  Modulo 7, 13 or 91, the quantity X+10Y+9Z 
 is the same as the original number. The basic process is to form an alternating sum of digits using only every third digit:

From the rightmost digit (the units), you subtract the 4th rightmost (the thousands), add the 7th, subtract the 10th, add the 13th, etc. This gives you the first of three numbers, call it X.

Do the same starting with the second rightmost digit (the tens), subtract the 5th, add the 8th, subtract the 11th, etc. This gives you a second number Y.

Finally, you start with the 3rd rightmost (the hundreds), subtract the 6th, add the 9th, subtract the 12th, add the 15th, etc. This yields a third number Z.

Now, compute the quantity  X + 10Y + 9Z,  which is best obtained mentally with just three additions and one trivial multiplication by 10:

10 (Y + Z)  +  X - Z

The original number is divisible by 13 iff this quantity is divisible by 13. The original number is divisible by 7 iff this quantity is divisible by 7.

It's remarkable that the same test works for both 7 and 13.  The reason is that  7´13 = 91 = 100-10+1. We're really dealing with divisibility by 91...

Proof :   To clarify,  let's consider  any  base of numeration  B  (which may or may not be equal to ten)  and use arithmetic  modulo  M  =  B2-B+1
  • (1 mod M) is 1,
  • (B mod M) is B,
  • (B2 mod M) is B-1,
  • (B3 mod M) is M-1  (equivalent to "-1" modulo M, that's the ticket ! )
  • (B4 mod M) is M-B,
  • (B5 mod M) is M-(B-1) and
  • (B6 mod M) is 1, after which the sequence repeats with period 6.

Therefore,  using the alternating sums X,Y and Z introduced above  in the decimal case,  we see that the number whose divisibility by  M  is being checked differs by a multiple of  M  from:

X  +  BY  +  (B - 1) Z     =     B (Y+Z) + X - Z       QED

In the octal system, that divisibility test  (based on the quantity X+8Y+7Z)  works for 3 and 19,  because 3 times 19 is 57 = 82-8+1.

Test of divisibility by 7,  for mental computations :

The above method is demonstrably the fastest for large numbers with pencil and paper.  For mental computation, however, the necessity of keeping track of several partial results is a major roadblock.  Also, that method itself is too complicated to memorize without practice,  unlike our next one.

If you're fluent in the language of congruences, the method below can be reconstructed mentally!  (You can also build similar methods  for divisors coprime with 10,  because those are invertible modulo 10.  With different divisors, only the coefficient applied to the last digit changes.)

Here are the instructions:  Split the number  N  into its last digit  y  and the number  x  formed by the other digits  (it can be very large).  Now, consider  2y  (twice the digit)  and x.  Subtract the smaller from the larger.  The result is divisible by 7 if and only if the original number was.  Repeat the procedure until the result is small enough for the divisibility to be obvious.

For example, to check that 224 is divisible by seven, subtract twice the last digit (8) from the leading digits (22).  You obtain 14.  If it's not obvious to you that 14 is divisible by 7, then do the procedure again; the difference between twice the last digit (8) and the leading digit is 7  (that's as low as it can get, the process always ends up with 0 or 7 for divisible numbers).

A bigger example:

67431   ->   6741   ->   672   ->   63   ->   0

Generalized divisibility tests,  for mental computations :

As advertised,  we may generalize the above mental test for divisibility by  7  to any modulus  M  coprime  with  10  (which is to say that the last digit of  M  is  1,3,7 or 9)  in which case  10  has a reciprocal  d  modulo M.

The number  d  is  easy to compute:  d = bezout(10,M)

As  M  and  d  are coprime  (by  Bézout's lemma)  M  divides 10x+y  if and only if it divides  d(10x+y)  or,  equivalently,  if and only if it divides  x+dy.

divides  10 x + y  if and only if it divides  x + d y
 M  d  M d M d  M d M d M d
1
3
7
9
11
13
17
19
0
1
-2
1
-1
4
-5
2
21
23
27
29
31
33
37
39
-2
7
-8
3
-3
10
-11
4
41
43
47
49
51
53
57
59
-4
13
-14
5
-5
16
-17
6
61
63
67
69
71
73
77
79
-6
19
-20
7
-7
22
-23
8
81
83
87
89
91
93
97
99
-8
25
-26
9
-9
28
-29
10
101
103
107
109
111
113
117
119
-10
31
-32
11
-11
34
-35
12

When a negative coefficent is called for  (e.g., -2 for divisibility by 7)  we may discard the sign of the result  (since x is divisible if and only if -x is)  or,  equivalently,  state that we'll always subtract the smaller number from the larger one,  as we did in the above  recipe  for divisibility by 7.

Those tests may end up either in a zero result  (which proves divisibility)  or a  cycle  with at least one element whose divisibility is deemed obvious  (e.g.,  when testing 224 for divisibility by 7,  we met the cycle 14,7,14,7...)

Divisibility Tricks  botched  by Tony Padilla   (Numberphile by Brady Haran, 2019-01-17).


(John of Middletown, NJ. 2000-10-14)   Lucky 7's
Any integer N>0 divides a number whose digits include only 7's and 0's.

Let P be the decimal period of the number  9N  (i.e., digits ultimately repeat with period P in the decimal expansion of 1/9N).  We have a relation of the form:

1 / 9N   =   K / 999...99000...00

Since the number 9N divides the number which consists of P nines followed by a certain number J of zeroes,  N divides the number consisting of P ones followed by J zeroes, and also the integer composed of P sevens followed by J zeroes.


 Simon Stevin 
 (1548-1620) (2010-01-25)   Recurring Decimals   (repeating decimals)
The decimals of  rational numbers  are ultimately periodic.

The key observation is that, in the process of a  long division  by the positive integer  D  (called  denominator  or  divisor )  you are eventually faced with  either  a zero remainder  or  a previously encountered nonzero remainder  (since there are only  D-1  of those, you can't encounter new ones forever).  In the latter case, the sequence of remainders is periodic from that point on...

Because the sequence of digits in the result depends only on the sequence of remainders, the sequence of digits is  ultimately periodic  as well.  Its period  P  is called the  decimal period  of  D.

The above shows that the period of  D  cannot exceed  D-1.  When that upper limit is reached,  D  is called a  long prime  to base ten.

Traditionally, the decimal expansion of a rational number whose  period  isn't too large is written out by putting a bar over the sequence of digits that repeat.  Usually, the overbar is not allowed to cover any digits to the left of the decimal point but this usage need not be respected.  Examples:

7526 / 165   =   45.612121212...   =   45.612

1 / 7   =   0.142857

100 / 7   =   14.28571428571428...   =   14.285714   =   14.2857

14   =   14.14   =   14.14141414141414...   =   1400 / 99

Ask Dr. Math :   Bar over a whole number?   by Sandy Taylor and Doctor Peterson


(2012-10-31)   Midy's Theorem   (Etienne Midy, 1835)
Properties of the period of  1/q  in radix-B numeration.

The period described above for decimal numeration generalizes to any numeration radix B.  If the period  P  of  q  in base  B  has length n, then we have  (assuming q is coprime with B):

1 / q   =   P / (Bn-1)

Therefore,   q P   =   Bn-1   =   (B-1) [ 1+B+B2+...+Bn-1 ]
So, if  (B-1)  is coprime with q, then it must divide P.  All told:

Midy's Lemma
B-1  divides the period in base  B  of any  q  coprime with  B(B-1).
(Equivalently,  B-1  divides the sum of the B-digits in such a period.)

For example, the decimal period of any integer not divisible by  2, 3 or 5 is necessarily divisible by 9.  This is to say that the sum of the digits in the decimal period of any such number is divisible by 9.

Midy's theorem  is either the above statement or, more often, one of the following spectacular corollaries  (especially the case k=2, which was the only one E. Midy ever bothered with).

A period of length  n = k.m  may also be construed as a period of length  k  in base  Bm.  Therefore,  Bm-1  divides the sum of the  k  slices of  m  digits that form the whole period of  q,  whenever  q  is coprime with  B(Bm-1).

That's what the French professor of mathematics  Etienne Midy  (from Nantes)  observed in 1835 for  k=2.  It took more than a sesquicentury for an undergraduate student at Yale  (Brian D. Ginsberg)  to make the same observation in 2003  (or 2001?) for  k = 3.  A few more years were needed to realize that  k  could be any divisor of n...

For example, the decimal period of  7  is  142857.  By viewing this as a period of length 2 in base 1000, we see that  142+857  must be divisible by  999.  If fact, it must be equal to  999  because the next multiple is too big  (we leave it to the reader to explain why the sum  999+999  cannot result from any decimal period of length 6).  This is Midy's original statement.

More than a sesquicentury later, Ginsberg would tell us that  14+28+57  must be a multiple of 99  (it's in fact equal to 99).

The smallest acceptable examples  (i.e., not divisible by 2,3 or 5)  that aren't prime are  49  and  77.  The latter is easy: 1/77  =  0.012987

012+987  =  999         01+29+87  =  99         0+1+2+9+8+7  =  3 . 9

49  is more interesting.  The period has a length of 42 and it can be divided into slices of  21, 14, 7, 6, 3, 2 or 1 digits:

1/49  =  0.020408163265306122448979591836734693877551

020408163265306122448 + 979591836734693877551   =   999999999999999999999
02040816326530 + 61224489795918 + 36734693877551   =   99999999999999
0204081 + 6326530 + 6122448 + 9795918 + 3673469 + 3877551   =   3 . 9999999
020408 + 163265 + 306122 + 448979 + 591836 + 734693 + 877551   =   3134854
020 + 408 + 163 + 265 + 306 + 122 + 448 + 979 + 591 + 836 + 734 + 693 + 877 + 551   =   7 . 999
02+04+08+16+32+65+30+61+22+44+89+79+59+18+36+73+46+93+87+75+51   =   10 . 99
0+2+0+4+0+8+1+6+3+2+6+5+3+0+6+1+2+2+4+4+8+9+7+9+5+9+1+8+3+6+7+3+4+6+9+3+8+7+7+5+5+1   =   21 . 9

So, what's wrong with the fourth decomposition?  Why doesn't it give a multiple of  999999 ?  Well, Midy's theorem would only apply if  q=49  and  (B-1) = 999999  were coprime and they're not  (both are divisible by 7).

To prevent such mishaps, the theorem is often stated only for prime values of  q.  I beg to differ:  It's good to know exactly what to look for when dealing with a composite value of  q.  This being said, it's true that a prime that doesn't divide B is always OK, since it cannot divide  Bm-1  for any submultiple m of the period n  (otherwise,  m  itself would be a smaller acceptable period).

Repeating decimal   |   Le théorène de Midy (1836)   |   Casting in Nines  by  John Kemeny
A Theorem on Repeating Decimals  by  William G. Leavitt, University of Nebraska - Lincoln  (1967).
"The Nearly Secret Theorem of E. Midy: An extension after 165 years"  by  Brian D. Ginsberg  (2003)
Generalizations of Midy's Theorem on Repeating Decimals  by  Harold W. Martin  (2006)


(2010-08-27)   Numbers with  two  decimal expansions...
1   =   1.000000000000000...   =   0.999999999999999...   =   0.9

It is only by convention that we do not normally use decimal expansions ending with infinitely many nines for numbers that have a  terminating  decimal expansion  (which could also be viewed as ending with infinitely many zeroes).

Indeed, positional numeration does not yield a one-to-one correspondence between the reals in the interval  [0,1]  and the infinite sequences of digits  (by appending such sequences to the  "0."  prefix).  A countable infinity of real numbers are assigned to  two  sequences of digits.  This fact may spoil the beauty of some mathematical proofs  (most notably  Cantor's diagonal argument)  but it's really a minor inconvenience which is easily dealt with.

As shown in countless Internet discussions, many beginners seem to have a hard time coming to grips with this particular idiosyncracy of positional numerations:  Different decimal expansions do not necessarily correspond to different numbers.  Any number is really the  limit  of truncated decimal expansions.  It so happens that some such limits can be obtained in two different ways.

Real numbers exist independently of the way we choose to represent them.  In decimal numeration, the number  1/7  has only one representation.  It has two representations in base  7.  Namely,  0.1  and  0.0666666...  Neither observation is relevant to the fact that the reciprocal of  7  is a unique well-defined point of the real number line.


(S.G. of San Marcos, TX. 2000-11-22)
How do I represent a floating-point number with hexadecimal normalization? I can't figure out how to convert exponent and mantissa, which should both be expressed in binary.
 
mrjohngribben (2001-08-10)
How would I write a fractional number in a base other than ten?
What is pi in hexadecimal (base sixteen)?

You can't "convert" mantissa and exponent separately. Look at the represented number itself and express it in binary.

What you want is probably "binary floating-point" (it's certainly possible to have "hexadecimal floating-point", but it's unused in practice). A binary floating-point number may be written out with hexadecimal digits for convenience but the exponent still refers to a power of 2 not 16 (again, pure hexadecimal is possible, it's just that we don't use it).

Take p = 3.14159265... for example. Its first two bits are 1 and 1 (the binary representation of 3), the next bit is the integral part of twice 0.1415926... namely 0.2831853... so it's 0. Repeat the process to get each successive bit by doubling the previous fractional part: You get 0 with 0.56637061..., 1 with 1.3127412..., 0 with 0.265482457... etc. All told, the (fixed-point) binary representation of p is

pi = 11.0010 0100 0011 1111 0110 1... 

You may write this in hexadecimal as 3.243F6... if you wish.

What's the binary floating-point representation of p ? Well, do just what you would do in decimal: Shift the pattern so there's just one nonzero digit before the "binary" point (resist the temptation to call it a "decimal" point) and record as "exponent" the length of the shift (that's a negative number if you had to shift the pattern to the left). For p, you shift the bit pattern only once to the right, so the exponent is +1 and the pattern is

pi = 1.1001 0010 0001 1111 1011 01... (two)^(+1)

That's the proper binary floating-point representation of p ("two" is spelled out to avoid using multiple bases of numeration in the same expression, even though "2" would not be ambiguous "16" would be in the discussion that follows).

The commonly used hexadecimal notation is simply a shorthand for the above, but the exponent still represents a power of two (so the first digit before the floating point is always a 1 and is therefore actually omitted from many/most/all internal representations used in computers):

pi = 1.921FA.. (two)^(+1)

What if you wanted everything to use base sixteen? Well, you'd have to shift the bit pattern by a multiple of 4 only (and count one unit of the exponent for each "nybble/nibble" of 4 bits so shifted). For p, this means no shift at all and we have the following purely hexadecimal representation of p (I won't repeat it enough, this is not the one used in computers):

pi = 3.243F6... (sixteen)^(0) 

What if you have to convert a large decimal floating point number?  Well, like it or not, what you have to do is basically work out the fixed-point representation and express it in binary (or hexadecimal) using a procedure similar to the above.  For example, to "convert"  1.965032919280624´107, just use the above (tedious) procedure to express  19560329.19280624  in binary.

 Leibniz Doodle


( T. D. of Fairbanks, AK. 2000-12-04)
How do I find square roots without the use of a calculator, especially when the square root will contain a decimal point?
( J. D. of Cape Coral, FL. 2000-12-07)
How do I extract the square root of a number?

It works a little bit like a long division with two basic differences:

  1. Instead of one digit at a time, you handle "slices" of two digits at a time  (the decimal point separates two such slices).
  2. You get each new digit by trying at each step to "extend" twice the previously found root with another digit so that the product of this extension by the (largest possible) new digit does not exceed the previously computed remainder.
To make this clear, let's just compute the square root of 2:
  1. Remainder is 2, Root is 0, DoubleRoot is 0.
    The largest digit "?" which is such that "0?" times "?" is no greater than 2 happens to be 1 (save this as the first digit in the square root). "01" times "1" is 1, which I subract from 2, the result is 1, which gets augmented by the "next slice" of unprocessed digits, namley "00". So, the new remainder is 100.
  2. Remainder is 100, Root is 1, DoubleRoot is 2.
    What's the largest digit such that "2?" times "?" does not exceed 100. Well it's 4 (save this as the second digit in the root). "24" times "4" is 96, which I subtract from 100 and augment with the next slice of "00" digits to get 400 as the new remainder.
  3. Remainder is 400, Root is 1.4, DoubleRoot is 28.
    The largest digit such that "28?" times "?" does not exceed 400 is 1 (which is thus our next digit). The new remainder is 400-281=119 augmented by the next "00"; 11900 is the new remainder.
  4. Remainder is 11900, Root is 1.41, DoubleRoot is 282.
    The next digit is 4 for which "282?" times "?" is 11296. 11900-11296 is 604; new remainder is thus 60400.
  5. Remainder is 60400, Root is 1.414, DoubleRoot is 2828.
    The next digit is 2 for which "2828?" times "?" is 56564. 60400-56564 is 3836; new remainder is thus 383600.
  6. Remainder is 383600, Root is 1.4142, DoubleRoot is 28284.
    The next digit is 1 for which "28284?" times "?" is 282841. 383600-282841 is 100759; new remainder is thus 10075900.
  7. Remainder is 10075900, Root is 1.41421, DoubleRoot is 282842.
    The next digit is 3 ... etc.

The square root of 2 is: 1.414213562373095048801688724209698...

Below is a binary version of the above algorithm, implemented (and optimized) in 68000 assembly language.  One aspect of it is simpler than the above:  At each step you only have two choices for what the next (binary) digit is going to be, instead of 10 such choices in the decimal case.  Thus, a simple test suffices (see the BLE instruction below) to make the proper decision...

Such an elementary implementation would allow a 12.66 MHz handheld calculator to extract over 16000 square roots per second...

; (c) 2007 - Gerard Michon
;
; SQRT takes a 31-bit integer (z) from register D3
; and returns the square root (y) and remainder (x)
; in D1 and D0 respectively.  Upon exit, x+y^2 = z :
; D0: 0000 XXXX = Remainder (x)
; D1: 0000 YYYY = Square root (y)
; D2: FFFF FFFF = -1
; D3: ZZZZ ZZZZ = Argument (z) unchanged
;
; BSR SQRT = 752 cycles + twice the count of '1' bits in y.
; Min=752, Max=784 (with 18 cycles for BSR instruction).
;
;                        Time: (in clock cycles)
;
7000 SQRT   MOVEQ  #0,D0     4: Clear x
7200        MOVEQ  #0,D1     4: Clear y
7400        MOVEQ  #0,D2     4: Two 16-bit counters

5E42 AGAIN  ADDQ.W #7,D2     4: Branch 7 times, for 8 loops
4843        SWAP   D3        4: Deal with upper 16 bits first
3003        MOVE.W D3,D0     4: Fetch 16-bit slice

EFC0 LOOP   ROL.L  #2,D0    12: Get 2 more radicand bits
D241        ADD.W  D1,D1     4: Shift root one bit
B041        CMP.W  D1,D0     4: OK to set root's new bit?
6F02        BLE    SKIP     10: No, leave 0 bit as is
5241        ADDQ.W #1,D1     2: Time = 4-2 (branch not taken)
51C2 SKIP   DBRA   D2,LOOP  10: Decrement counter (8 times)
FFF2                         4:
4842        SWAP   D2        4:
4A42        TST.W  D2        4: Already been here?
67E6        BEQ    AGAIN    10: No, do second half
4E75        RTS             14: Time = 16-2 (branch not taken)

Warning :   A Numericana reader couldn't make the above work...  Unfortunately, I no longer can test that program or even debug it step by step on paper  (having missplaced the proper Motorola documentation).


(2009-10-14)   Optimal Radix of Numeration ?
From odometers to  guessing cards  and automated phone help.

A mechanical radix-b odometer consists of  n  wheels, each engraved with  b  symbols  (representing the digits from 0 to b-1).  Such a device can encode  b n  different integers, thus conveying an amount of information equal to

n lg(b)

The unit of information we use here is the shannon  (symbol Sh )  which is the quantity of information conveyed by a single binary digit, or  bit.  The "lg" function is the binary logarithm:  lg(x) = Log(x)/Log(2).

Therefore, the amount of information  per engraved symbol  is  lg(b)/b.  If  b=2, this is  0.5 Sh  (a fancy way to say that there are two engraved symbols per bit in a binary odometer).  The lower quantity  lg(10)/10 = 0.33219... Sh  indicates that a decimal odometer is less efficient than a binary one according to a theoretical "cost" proportional to the total number of engraved symbols.  On the other hand, surprisingly, a  ternary  odometer  (b = 3)  is  5.66%  more  efficient than a binary one, since  lg(3)/3 = 0.52832... Sh.

That slight advantage of the ternary system of numeration was pondered at the beginning of the computer era.  However, the above analysis assumes that an element capable of encoding a  trit  (i.e., a ternary digit)  is only  50%  more costly than its binary counterpart.  If a ternary element is at least  58.49%  more costly than a binary one  (which is the case for all electronic solutions devised so far)  then the putative advantage is lost...  All modern computers are binary.

The above gave birth to the urban legend that ternary numeration was the "best" one since the integer 3  is "closest to the optimum"  [sic]  of  e = 2.718281828...  (which maximizes the aforementioned quantity  lg(b)/b).

Nevertheless, I argue that the marginal superiority of ternary numeration can be put to good use in at least one entertaining example:  A definite improvement on the popular "age card" guessing trick.

In his 2008 recreational book entitled  Group Theory in the Bedroom, Brian Hayes also mentions the design of the ubiquitous "menus" in automated telephone helplines:  Directing a phone customer to one of  many  final destinations is best accomplished by offering successive options in groups of 3  (assuming we just want to minimize the total number of choices presented to stranded callers).


(2012-12-18)   The  dozenal  (i.e., duodecimal)  system.
Counting in base  twelve.  Reviving ounces, dozens and grosses.

The  uncia  was the basic Roman fraction.  Twelve  unciae  per unit.  The roman ounce was one twelfth of a Roman pound.  Likewise 12 ozt  (i.e. twelve troy ounces)  used to make a  troy pound  (the lbt unit was made illegal for any trade in 1879 but the ozt remains a dominant unit of mass worldwide for precious metals).

There is, of course, no way any other positional system will ever replace the decimal system for general use  (our computers "think" in binary but communicate with people in decimal).  Yet, some people are having fun advocating the duodecimal  (radix twelve)  positional system of numeration and the new nomenclature that could accompagny its everyday use:

  • The name  dozenal  for the system itself.
  • Two extra digits  dek  (c)  &  el  (e)  for ten & eleven, respectively.
  • The abbeviations  dogro  mo  for the first powers of twelve.

Episode of "Numberphile" by Brady HaranBase 12  by James Grime  (2012-12-12).
Duodecimal (Wikipedia)   |   Dozenal Society of America (DSA)   |   Dozenal Society of Great-Britain (DSGB)


(2018-09-26)   Shortcomings of the Ancient  Sexagesimal  System.
Cuneiform numbers were ultimately upgraded with a  zero  placeholder.

Originally,  no cuneiform mark existed for the zero sexagesimal digit,  which was just represented by a blank space.  Spacing was also critical when a sexagesimal digit with only a symbol for tens was followed by a sexagesimal digit with no tens.  Thus,  there was a great risk of confusion between the sexagesimal numbers which we're now transliterating  (unambiguously)  as  56  and  50.06  (the ancient scribe who produced  Plimpton 322  made that very mistake on his second row).

The need for several kinds of zeros:

  • Stand-alone zero.  Nothing to count.  The Void.
  • Radix point and leading zeros.  Initial zeros.
  • Terminal cipher,  Trailing zeros.  Final zeros.
  • Medial Cipher.  Empty intermediate position.  Zero sexagesimal digit.
  • Lack of ones.  Completing the digits for 10, 20, 30, 40 and 50.

By 300 BC,  a double slanted line  (sometimes superscripted)  evolved into a true zero sexagesimal digit,  which could serve either as a medial or terminal cipher  (trailing zeros indicating multication into a power of sixty).

Reportedly,  an earlier usage of this symbol,  dating back to  1500 BC,  was simply to separate sexagesimal digits.

Apparently,  that cuneiform symbol was never used by itself historically.  The number zero was invented in India several centuries after cuneiform writing was utterly extinct.

 Come back later, we're
 still working on this one...

Babylonian numerals  by  Edmund F. Robertson  (MacTutor, Dec. 2000).
Sexagesimal zeros represented by blank spaces (ResearchGate).
What is the origin of zero?  by  Robert Kaplan  (Scientific American, 2001-10-04).
Symbols for Nothing  by  Dirk Schlimm & Katherine Skosnik  (McGill, Philosophy, 2010-09-10).
Ancient Babylonian Number System Had No Zero  by  Evelyn Lamb  (Scientific American, 2014-08-31).

border
border
visits since May 11, 2007
 (c) Copyright 2000-2021, Gerard P. Michon, Ph.D.