+
1
|
skin
|
login
|
edit
{λ way}
::
bignums
user:anonymous
_h3 big numbers | [[bignum]] _p The way the {b javascript Math object} is implemented puts the limit of natural numbers to {b {code 2{sup 54}}}. Beyond this limit last digits can be rounded to zeroes - the four last digits of 2{sup 64} = '{pow 2 64} = {pow 2 64} are rounded to 2000 - and beyond {b {code 2{sup 69}}} natural numbers are replaced by float numbers with a maximum of 15 valid digits. {pre '{pow 2 8} -> {pow 2 8} // valid result '{pow 2 16} -> {pow 2 16} // valid result '{pow 2 32} -> {pow 2 32} // valid result ... '{pow 2 54} -> {pow 2 54} // last valid number '{pow 2 55} -> {pow 2 55} // the last zero is false ... '{pow 2 64} -> {pow 2 64} // 2000 should be 1616 ... '{pow 2 69} -> {pow 2 69} // the last zeroes are false '{pow 2 70} -> {pow 2 70} // it's float number ... '{pow 2 128} -> {pow 2 128} // it's a float number ... '{pow 2 256} -> {pow 2 256} // it's a float number } _p Let's come back to the definition of a natural number: {i A natural number {code a{sub 0}a{sub 1}...a{sub n}} is the value of a polynomial {code Σ{sub i=0}{sup n}a{sub i}x{sup i}} for {code x=10}}. For instance {code 12345 = 1*10{sup 4}+2*10{sup 3}+3*10{sup 2}+4*10{sup 1}+5*10{sup 0}}. '{lambda talk} knows {code lists}, we represent a natural number as a list on which we define a set of functions: {code [pk, p+, p*, normalize, pol2bignum, bignum2pol]}. {pre {def BN.bignum2pol {def BN.bignum2pol.rec {lambda {:n :p :i} {if {< :i 0} then :p else {BN.bignum2pol.rec :n {cons {charAt :i :n} :p} {- :i 1}} }}} {lambda {:n} {BN.bignum2pol.rec :n nil {- {chars :n} 1}} }} {def BN.pol2bignum {def BN.pol2bignum.rec {lambda {:p :n} {if {equal? :p nil} then :n else {BN.pol2bignum.rec {cdr :p} {car :p}:n} }}} {lambda {:p} {let { {:q {list.reverse :p}} } {BN.pol2bignum.rec {cdr :q} {car :q}}} }} {def BN.simplify {def BN.simplify.rec {lambda {:p :q :r} {if {and {equal? :p nil} {= :r 0}} then :q else {if {equal? :p nil} then {cons :r :q} else {BN.simplify.rec {cdr :p} {cons {+ {% {car :p} 10} :r} :q} {floor {/ {car :p} 10}} }} }}} {lambda {:p} {BN.simplify.rec {list.reverse :p} nil 0} }} {def BN.normalize {lambda {:p :n} {if {< :n 1} then :p else {BN.normalize {BN.simplify :p} {- :n 1}} }}} {def BN.pk {lambda {:k :p} {if {equal? :p nil} then nil else {cons {* :k {car :p}} {BN.pk :k {cdr :p} }} }}} {def BN.p+ {lambda {:p1 :p2} {if {and {equal? :p1 nil} {equal? :p2 nil}} then nil else {if {equal? :p1 nil} then :p2 else {if {equal? :p2 nil} then :p1 else {cons {+ {car :p1} {car :p2}} {BN.p+ {cdr :p1} {cdr :p2} }}}} }}} {def BN.p* {lambda {:p1 :p2} {if {or {equal? :p1 nil} {equal? :p2 nil}} then nil else {if {not {cons? :p1}} then {BN.pk :p1 :p2} else {BN.p+ {BN.pk {car :p1} :p2} {cons 0 {BN.p* {cdr :p1} :p2}}}} }}} } _h3 2{sup 64}, 2{sup 128}, 2{sup 256} _p We can now compute 2{sup 64}, 2{sup 128}, 2{sup 256} using a decimal representation. We begin with the valid representation of {code {code 2{sup 32}} = {pow 2 32}} given by the Javascript Math Object. Then we define {code {code 2{sup 64}} = 2{sup 32}*2{sup 32}}, where p* is the polynomial multiplication, and so on: {pre '{def 2q32 {BN.bignum2pol {pow 2 32}}} '{BN.pol2bignum {2q32}} 4294967296 '{def 2q64 {BN.normalize {BN.p* {2q32} {2q32}} 2}} '{BN.pol2bignum {2q64}} 1844674310736109551616 '{def 2q128 {BN.normalize {BN.p* {2q64} {2q64}} 3}} '{BN.pol2bignum {2q128}} 340282366920938463463374607431768211456 '{def 2q256 {BN.normalize {BN.p* {2q128} {2q128}} 4}} '{BN.pol2bignum {2q256}} 115792089237316195423570985008687907853269984665640564039457584007913129639936 } _h3 21!, 22!, 30!, 50! {pre '{def bigfac {lambda {:n} {if {< :n 1} then {BN.bignum2pol 1} else {p* {BN.bignum2pol :n} {bigfac {- :n 1}}} }}} -> {def bigfac {lambda {:n} {if {< :n 1} then {BN.bignum2pol 1} else {BN.p* {BN.bignum2pol :n} {bigfac {- :n 1}}} }}} {def ibigfac {def ibigfac.r {lambda {:n :p} {if {< :n 1} then :p else {ibigfac.r {- :n 1} {BN.p* {BN.bignum2pol :n} :p}} }}} {lambda {:n} {ibigfac.r :n {BN.bignum2pol 1}} }} } {pre 6! = '{BN.pol2bignum {BN.normalize {bigfac 6} 1}} 720 21! = '{BN.pol2bignum {BN.normalize {bigfac 21} 13}} 51090942171709440000 22! = '{BN.pol2bignum {BN.normalize {bigfac 22} 15}} 1124000727777607680000 30! = '{BN.pol2bignum {BN.normalize {bigfac 30} 30}} 265252859812191060836068652000000 50! = '{BN.pol2bignum {BN.normalize {bigfac 50} 50}} 30414093201713380398385728867859900744706627746248466026044200000 } {pre PYTHON: 22! = 1124000727777607680000 30! = 265252859812191058636308480000000 50! = 30414093201713378043612608166064768844377641568960512000000000000 }