Version 11 of Googol magnitude

Updated 2005-02-05 10:05:05 by suchenwi

ABU ... I'd like Tcl could reach the same power of Python in arithmetics !

Currently, Tcl is rather limited in arithmetic ; astonishingly Python has integers with unlimited precision !.

A funny benchmark is playing with the most famous big-number : googol (10**100)

Here is googol (in Python)

 >>> 10**100
 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

As you can see below, all 100 digits are 'true' (I mean it is not an approximation): let's take a look at googol more or less one ...

 >>> 10**100-1
 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

 >>> 10**100+1
 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

But, how long (in bits) is googol ?

 number_of_bits = ceil(log2(googol)) = 333

Thus we need 333 bits in order to store googol.

Do you want to see these 333 bits ? Here is a Python function:

 #  print a (decimal) number in binary representation

 import sys

 def dec2bin ( N ):
   h2b = {}
   h2b['0'] = '0000'
   h2b['1'] = '0001'
   h2b['2'] = '0010'
   h2b['3'] = '0011'
   h2b['4'] = '0100'
   h2b['5'] = '0101'
   h2b['6'] = '0110'
   h2b['7'] = '0111'
   h2b['8'] = '1000'
   h2b['9'] = '1001'
   h2b['A'] = '1010'
   h2b['B'] = '1011'
   h2b['C'] = '1100'
   h2b['D'] = '1101'
   h2b['E'] = '1110'
   h2b['F'] = '1111'
   #
   for i in ('%X' % N) :
      sys.stdout.write(h2b[i])
   sys.stdout.write('\n')


 >>> dec2bin( 10**100 )
 00010010010010011010110100100101100101001100001101111100111010110000101100100111
 10000100110001001100111000001011111100111000101011001110010000001000111000100001
 00011010011111001010101010110010010000110000100010101000001011101000111100010000
 00000000000000000000000000000000000000000000000000000000000000000000000000000000
 0000000000000000

( we printed 336 bits (84 groups of 4 bits) but the first 3 bits are zero, thus 333 bits )

Funny Uh! how many trailing zeros ... exactly 100 zeros ! Could it be wrong ? let's try printing 'googol-1' ; we expect a lot of trailing 1's ...

 >>> dec2bin(10**100 -1)
 00010010010010011010110100100101100101001100001101111100111010110000101100100111
 10000100110001001100111000001011111100111000101011001110010000001000111000100001
 00011010011111001010101010110010010000110000100010101000001011101000111100001111
 11111111111111111111111111111111111111111111111111111111111111111111111111111111
 1111111111111111

Now a further question : What's bigger than googol ?

googolplex !

googolplex is : 10**googol i.e. 1 followed by googol (10**100) zeros

Could we print it ?

I doubt we could have googolplex particles in the universe ... Never mind; let's try ...

a printed page can hold 100 rows of 100 chars. 10**4 characters Let's suppose we a a billion (10**9) of printers, each one printing a billion of pages each second ...

Then, after one year we could have printed 10**4 * 10**9 * 10**9 * 365*24*60*60 = 10*22 * 31536000 ~= 3.2 * 10*29 digits

This is an infinitesimal fraction of a googleplex. So infinitesimal we could not express it ! Even after one billion year of printing, we'll have about 3.2 * 10**38 digits (still an infinitesimal fraction)

Remember:

  • a googol is 1 followed by 100 zeros
  • a googolplex is 1 followed by 'googol zeros ...

Amusing links:


AM (3 february 2005) Your wish has been heard: work is in progress to incorporate "big integers" in the Tcl 8.5 core. In the meantime, you might want to try any of the arbitrary-precision extensions, like mpexpr or the Tcllib bignum package.


RS Even before having bignum at hand, here's how to generate the string rep in Tcl :^)

 % set googol 1[string repeat 0 100]
 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

ABU Your trick is not valid ! Try to add 1 to $googol ...

AM Well, RS only promised to get the string representation :). But you are right: plain old Tcl will have trouble doing that and come up with the exact answer.

RS can't resist but code this (works only for positive increment so far):

 proc sincr {istring {increment 1}} {
    if {$increment==0} {return $istring}
    set sum [expr [string index $istring end]+$increment]
    set digit [expr $sum%10]
    set carry [expr $sum/10]
    return [sincr [string range $istring 0 end-1] $carry]$digit
 }

#-- Testing:

 % sincr 999 1
 1000
 % set googol 1[string repeat 0 100]
 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
 % sincr $googol 1
 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

In a nutshell, that's how all pure-Tcl bignum math works: split to smaller strings, do math, recompose string.

Lars H: Can't resist giving my own increment variant

 proc sincr1 {varname} {
    upvar 1 $varname var
    regexp {^(.*?)(.)(9*)$} $var "" l i r
    set var $l[incr i][string repeat 0 [string length $r]]
 }

This only increments by 1, but it has the advantage of not being recursive.

And as for conversion to binary, here is a Tcl one that does all the arithmetic (by repeated halfing) and is shorter than the above Python version:

 proc dec2bin {num} {
    while {[regexp {[0-9]} $num]} {
       set num\
         [string map {o0 0 o1 1 o2 2 o3 3 o4 4 i0 5 i1 6 i2 7 i3 8 i4 9 0 ""}\
           [string map {0 0o 1 0i 2 1o 3 1i 4 2o 5 2i 6 3o 7 3i 8 4o 9 4i} $num]]
    }
    string map {i 1 o 0} $num
 }

 % string length [dec2bin 1[string repeat 0 100]]
 333
 % dec2bin 32003
 111110100000011

RS: Wow - very fascinating code! To understand how it works, I made me this "educational version":

 proc dec2bin {num} {
    while {[regexp {[0-9]} $num]} {
       set num [string map {0 0o 1 0i 2 1o 3 1i 4 2o 5 2i 6 3o 7 3i 8 4o 9 4i} $num]
       puts a:$num
       set num [string map {o0 0 o1 1 o2 2 o3 3 o4 4 i0 5 i1 6 i2 7 i3 8 i4 9 0 ""} $num]
       puts b:$num
    }
    string map {i 1 o 0} $num
 }

The outputs shows how binary digits (o,i) collect on the right, while the decimal number on the left is successively "decimated" by halving... Is this maybe related to Markov algorithms?

 % dec2bin 123
 a:0i1o1i 
 b:61i
 a:3o0ii
 b:30ii
 a:1i0oii
 b:15oii
 a:0i2ioii
 b:7ioii
 a:3iioii
 b:3iioii
 a:1iiioii
 b:1iiioii
 a:0iiiioii
 b:iiiioii
 1111011

Category Mathematics