Big integer routines

Richard Suchenwirth 2002-12-31 - Using plain strings of digits, unsigned integers of arbitrarily large size can be represented in Tcl. In KISS I showed my versions of addition and multiplication; here now comes division (a big int divided by a regular int, may be 64 bits wide). The aim of such studies is of course factorisation of large integers...

 proc bigint'div {dividend divisor} {#
    set carry ""
    set res ""
    foreach digit [split $dividend ""] {
       set carry [scan [append carry  $digit] %d]
       append res [expr {$carry / $divisor}]
       set carry  [expr {$carry % $divisor}]
    }
    list [string trimleft $res 0] $carry
 }

 proc bigint'hex bigint {
   set res ""
   while {$bigint != ""} {
       foreach {bigint carry} [bigint'div $bigint 256] break
       set res [format %02x $carry]$res
   }
   if {$res eq ""} {set res 00} else {set res}
 }

Category Mathematics