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:
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