I speed up more extensively adda and multa in doing computation in base 10000 instead of 10. Here is code

global base set base 10000 # Add two numbers. proc adda {xs ys} { global base set rs {} set carry 0 if {[llength $xs]>[llength $ys]} { set len [llength $ys] set flag 0 } else { set len [llength $xs] set flag 1 } set pos 0 foreach x $xs y $ys { if {$pos>=$len} { if {$flag} {set x 0} else {set y 0} } set n [expr {$x+$y+$carry}] set carry [expr {$n / $base}] lappend rs [expr {$n % $base}] incr pos ;# who stole this line? restored 11/00 MM } if {$carry} {lappend rs $carry} return $rs } proc multi {xs a} { global base set rs {} #puts "multi : xs=$xs" if { $a == $base } { set rs $xs set rs [ linsert $rs 0 0 ] #puts "multi: rs=$rs" return $rs } set carry 0 foreach x $xs { set n [expr {$x*$a+$carry}] set carry [expr {$n / $base}] lappend rs [expr {$n % $base}] } if {$carry} {lappend rs $carry} return $rs } proc multa {xs ys} { global base set rs {} set d $ys foreach x $xs { set n [multi $d $x] set rs [adda $rs $n ] set d [multi $d $base ] } return $rs } # Convert an integer to a (list-formatted) number. proc tolist {n} { global base set rs {} if {[catch {incr n 0}]} { set k 0 set nn {} set rs {} set l [string length $n ] incr l -1 for { set i $l } { $i >= 0 } { incr i -1 } { set digit [ string index $n $i ] incr k set nn "$digit$nn" if { $k == 4} { set k 0 lappend rs $nn #puts -nonewline " $nn" set nn {} } } if { $nn != {} } { lappend rs $nn #puts -nonewline " $nn" } #puts "" } else { while {$n > 0} { lappend rs [expr {$n%$base}] set n [expr {$n/$base}] } } #puts "tolist rs= $rs" return $rs } # Convert a (list-formatted) number to a human-readable form. # Will be an integer (modulo type-shimmering) if representable. proc fromlist {xs} { set r {} foreach x $xs { if { $x == 0 } { set r "0000$r" } else { set r $x$r } } if {![string length $r]} {set r 0} return $r } # DEMO CODE: Factorial. Try calculating [fact 40] for a 48-digit number proc fact {n} { set this 1 for {set i 1} {$i <= $n} {incr i} { set this [multa $this [tolist $i]] } return [fromlist $this] } # DEMO CODE: Fibonacci Sequence. Doesn't grow anything like as fast as factorial (in fact, two-term recurrences such as Fibonacci grow at quadratic rates), # but still grows beyond 32-bit integers quite easily. proc fib {n} { set this 1 set last 0 for {set i 1} {$i<$n} {incr i} { set new [adda $this $last] set last $this set this $new } return [fromlist $this] }

** JJD **

Here are a few procedures I put together to perform arbitrary precision arithmetic. If you are using these a lot, perhaps you should consider the *mpexpr* extension [L1 ] instead.

The basic representation I use is a list of decimal digits (easy to convert to and from human-readable form) stored least-significant digit first (so the code handles the magnitude of the numbers implicitly.)

This all comes from a discussion I was having in email relating to some messages online about calculating factorials. I've decided to put the procs here so I can find them again. Feel free to optimise them, add in relevant links, more examples, other representations, etc.

**DKF**

**WHOA!** Donal, am I missing something here?

% tolist 75676576576576576567575 can't use floating-point value as operand of "%" %

-PSE

That's not an integer, is it? It's just a string of digits... Oh well, I've fixed the code below now, so your example should now work. - *DKF*

**HOW** is that not an integer?

inýý·teýý·ger (nt-jr) n. Mathematics 1.A member of the set of positive whole numbers (1, 2, 3, . . .), negative whole numbers (-1, -2, -3, . . .), and zero (0). 2.A complete unit or entity.

BTW, I fixed your missing bracket problem down there... things are quite spiffy now. How would we ever get along without our own knight-of-the-lambda-calculus? Thanks Donal! *-PSE*

Hah! Dictionary definitions are for wimps! It cannot be parsed by *Tcl_GetInt()*, so obviously it cannot be an integer. This is confirmed by the use of the **[string is integer 75676576576576576567575]** test, which naturally fails.

(And cheers for fixing any missing bracket problems.)

*DKF*

All of the words in the dictionary cannot express my gratitude that I do not have to sit across the table from you at the Monday morning status meeting... -**PSE**

My status meetings are usually on Friday afternoons, and I have the advantage of working with people with heavy admin and/or teaching loads, so any work I choose to do is definitely appreciated. And I drink coffee that is substantially stronger than Starbucks makes theirs...

Now, I've got a compiler spec. that I really ought to get written for as soon as possible. So I do hope you'll forgive me if I leave this pleasant little discussion for now and get on with a little work. -*DKF*

So should I, but I like this place ;-) how 'bout

proc string_is_dictionary_integer {s} {regexp {^-?[0-9]+$} $s} ;#RS

proc K {x y} {set x};# For a speedup # Add two numbers. proc adda {xs ys} { set rs {} set carry 0 if {[llength $xs]>[llength $ys]} { set len [llength $ys] set flag 0 } else { set len [llength $xs] set flag 1 } set pos 0 foreach x $xs y $ys { if {$pos>=$len} { if {$flag} {set x 0} else {set y 0} } set n [expr {$x+$y+$carry}] set carry [expr {$n / 10}] lappend rs [expr {$n % 10}] incr pos ;# who stole this line? restored 11/00 MM } if {$carry} {lappend rs $carry} return $rs } # Multiply two numbers. proc multa {xs ys} { set rs 0 foreach x $xs { for {} {$x>0} {incr x -1} { set rs [adda [K $rs [set rs {}]] $ys] } set ys [linsert [K $ys [set ys {}]] 0 0] } return $rs } # Convert an integer to a (list-formatted) number. proc tolist {n} { set rs {} if {[catch {incr n 0}]} { foreach digit [split $n {}] { set rs [linsert [K $rs [set rs {}]] 0 $digit] } } else { while {$n > 0} { lappend rs [expr {$n%10}] set n [expr {$n/10}] } } return $rs } # Convert a (list-formatted) number to a human-readable form. # Will be an integer (modulo type-shimmering) if representable. proc fromlist {xs} { set r {} foreach x $xs { set r $x$r } if {![string length $r]} {set r 0} return $r } # DEMO CODE: Factorial. Try calculating [fact 40] for a 48-digit number proc fact {n} { set this 1 for {set i 1} {$i <= $n} {incr i} { set this [multa [K $this [set this {}]] [tolist $i]] } return [fromlist $this] } # DEMO CODE: Fibonacci Sequence. Doesn't grow anything like as fast as factorial, # but still grows beyond 32-bit integers quite easily. proc fib {n} { set this 1 set last 0 for {set i 1} {$i<$n} {incr i} { set new [adda $this $last] set last $this set this $new } return [fromlist $this] }

Another link: http://homepages.ihug.co.nz/~webscool/integer.html - RS

See math::bignum from tcllib. It is pure-Tcl. And in Tcl 8.5, *default* integers are now Bignums as described in TIP #237.

See mkTulip at http://mkextensions.sourceforge.net/ .

Also perhaps checkout Decimal Arithmetic Package for tcl 8.5

Check out Bignums Fast and Dirty and arbint and mpexpr.

[Maybe write here a bit about arithmetic based on Schönhage and Strassen, and also Priest's '91 paper on "Algorithms for Arbitrary Precision Floating Point Arithmetic". Is this the right place?]

- Also Cody's
**Software for the Elementary Function** - R. P. Brent. Fast multiple-precision evaluation of elementary functions. Journal of the Association for Computing Machinery, 23(2):242-251, April 1976.
- R.P. Brent. A FORTRAN multiple-precision arithmetic package ACM Trans. on Math. Software, 4, no 1, 57-70, 1978.
- Douglas M. Priest, "Algorithms for arbitrary precision floating point arithmetic," 10th IEEE Symposium on Computer Arithmetic, 1991, pp. 132-143
- D. M. Smith, "A FORTRAN package for floating-point multiple-precision arithmetic," ACM transactions on mathematical software 17 (2) (Jun. 1991) 273-283.
- David H. Bailey, "Multiprecision Translation and Execution of Fortran Programs", ACM Transactions on Mathematical Software, vol. 19, no. 3 (Sept. 1993), pg. 288--319
- Smith, D.M. 1998. Multiple Precision Complex Arithmetic and Functions. ACM Trans. Math. Softw. 24, 4 (December), 359--367
- http://www.netlib.org