rebol [ Library: [ level: 'intermediate platform: 'all type: tool domain: [math] tested-under: none support: none license: none see-also: none ] History: [ [1.0 22-mar-2007 "First version"] ] Title: "Bignumbers.r" File: %bignumbers.r Owner: "Alban Gabillon" Version: 1.0 Date: 22-Mar-2007 Purpose: { This script allows you to apply the four classical operations (add, subtract divide, multiply) on very big positive integers. Size of the integers is only limited by the size of a rebol string since numbers are represented as strings. When using this script, keep in mind that the operations manipulate "string numbers" in reverse order (see example at the end of the script)}] add: func [ {add two big numbers written in reverse order - output is also written in reverse order} n1 [string!] n2 [string!] /local mem plus n result][ mem: 0 result: copy "" if (length? n1) < (length? n2) [n: n1 n1: n2 n2: n] while [not tail? n2][ plus: to-string ((to-integer to-string n1/1) + (to-integer to-string n2/1) + mem) either (length? plus) = 1 [mem: 0 result: insert result plus/1][mem: 1 result: insert result plus/2] n1: next n1 n2: next n2] while [all[mem = 1 not tail? n1]][ plus: to-string ((to-integer to-string n1/1) + mem) either (length? plus) = 1 [mem: 0 result: insert result plus/1][mem: 1 result: insert result plus/2] n1: next n1] either mem = 1 [insert result #"1"][insert result copy n1] result: head result] multiply: func [ {multiply two big numbers written in reverse order - output is also written in reverse order} n1 [string!] n2 [string!] /local count i longueur result temp n][ if (length? n1) < (length? n2) [n: n1 n1: n2 n2: n] longueur: length? n2 result: copy "0" for count 1 longueur 1 [ temp: copy "0" for i 1 (to-integer to-string n2/:count) 1 [ temp: add temp n1] insert/dup temp #"0" (count - 1) result: add result temp] result] greater: func [ {compare two bignumbers written in reverse order - return none if they are equal} n1 [string!] n2 [string!]][ either (length? n1) <> (length? n2) [(length? n1) > (length? n2)][ either equal? n1 n2 [none][ n1: back tail n1 n2: back tail n2 while [n1/1 = n2/1][n1: back n1 n2: back n2] n1/1 > n2/1] ] ] sub: func [ {substract the smallest big number from the largest one - both numbers are written in reverse order - output is also written in reverse order} n1 [string!] n2 [string!] /local mem minus n result][ mem: 0 result: copy "" if greater n2 n1 [n: n1 n1: n2 n2: n] while [not tail? n2][ minus: to-string (((to-integer to-string n1/1) - mem) + (10 - (to-integer to-string n2/1))) either (length? minus) = 1 [mem: 1 result: insert result minus/1][mem: 0 result: insert result minus/2] n1: next n1 n2: next n2] while [all[mem = 1 not tail? n1]][ minus: to-string ((to-integer to-string n1/1) + (10 - mem)) either (length? minus) = 1 [mem: 1 result: insert result minus/1][mem: 0 result: insert result minus/2] n1: next n1] insert result copy n1 result: back tail result while [all [result/1 = #"0" not head? result]][result: back result] clear next result result: head result] divide: func [ {divide two big numbers written in reverse order - output is a block of two numbers [quotient remainder] also written in reverse order} n1 [string!] n2 [string!] /local count i result temp quotient diff][ if greater n2 n1 [return reduce ["0" n1]] if equal? n1 n2 [return reduce ["1" "0"]] diff: (length? n1) - (length? n2) insert/dup n2 #"0" diff if greater n2 n1 [remove n2 diff: diff - 1] quotient: copy "" for i 1 diff 1 [ temp: copy n2 count: 0 until [switch greater n1 temp reduce [ none [ insert quotient to-string (count + 1) insert/dup quotient #"0" (diff - i + 1) return reduce [quotient "0"]] false [ insert quotient to-string count n1: sub n1 (sub temp n2) remove n2 true] true [ count: count + 1 temp: add temp n2 false] ] ] ] temp: copy n2 count: 0 until [switch greater n1 temp reduce [ none [ insert quotient to-string (count + 1) return reduce [quotient "0"]] true [count: count + 1 temp: add temp n2 false] false [insert quotient to-string count n1: sub n1 (sub temp n2) return reduce [quotient n1]] ] ] ] p: {102639592829741105772054196573991675900716567808038066803341933521790711307779} q: {106603488380168454820927220360012878679207958575989291522270608237193062808643} rsa-155: {10941738641570527421809707322040357612003732945449205990913842131476349984288934784717997257891267332497625752899781833797076537244027146743531593354333897} probe p print "*" probe q print "=" reverse p reverse q probe reverse multiply p q print "" print "" probe rsa-155 print "/" probe reverse p reverse p print "=" reverse rsa-155 r: divide rsa-155 p probe reduce [reverse r/1 reverse r/2] ask "Press Enter to quit"