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 !.
Tcl 8.5 now provides unlimited precision integer.
expr 10**100+1 ; # a googol plus one
gives the correct (not approximated) result
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
111110100000011RS: 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
Lars H: Well, the way it works is simply that it halves every digit in place, writing o and i for 0/2 and 1/2 respectively. Then it combines these fractional parts with the integer part (digit) in the next position, where i is worth 5 instead. It probably could be expressed as a Markov algorithm, but I'm not sure if one could do it without introducing some "cursor symbol" to have the strings processed in the right order.
The string repeat way to produce powers of 10 can be wrapped pretty cutely:
% interp alias {} E {} string repeat 0
E
% set x 1[E 3]
1000