77 lines
2.1 KiB
Text
77 lines
2.1 KiB
Text
Natural positive numbers are defined as strings, for instance 123 -> "123".
|
|
{lambda talk} has a small set of primitives working on strings, [equal?, empty?, chars, charAt, substring]
|
|
|
|
1) helper functions
|
|
|
|
{def lastchar
|
|
{lambda {:w}
|
|
{charAt {- {chars :w} 1} :w}
|
|
}}
|
|
{def butlast
|
|
{lambda {:w}
|
|
{substring 0 {- {chars :w} 1} :w}
|
|
}}
|
|
{def zeros
|
|
{lambda {:n}
|
|
{if {< :n 1}
|
|
then
|
|
else 0{zeros {- :n 1}}
|
|
}}}
|
|
|
|
2) add function
|
|
|
|
{def add
|
|
{def add.r
|
|
{lambda {:a :b :c :d}
|
|
{if {equal? :a #}
|
|
then {if {equal? :d 1} then 1 else}{butlast :c}
|
|
else {let { {:a :a} {:b :b} {:c :c}
|
|
{:d {+ :d {lastchar :a} {lastchar :b} }} }
|
|
{add.r {butlast :a} {butlast :b} {lastchar :d}:c
|
|
{if {equal? {chars :d} 1} then 0 else 1}}
|
|
}}}}
|
|
{lambda {:a :b}
|
|
{{lambda {:a :b :n}
|
|
{add.r #{zeros {- :n {chars :a}}}:a
|
|
#{zeros {- :n {chars :b}}}:b # 0}
|
|
} :a :b {max {chars :a} {chars :b}}}
|
|
}}
|
|
|
|
3) mul function
|
|
|
|
{def mul
|
|
{def muln
|
|
{lambda {:a :b :n}
|
|
{if {< :n 1}
|
|
then :b
|
|
else {muln :a {add :a :b} {- :n 1}}
|
|
}}}
|
|
{def mul.r
|
|
{lambda {:a :b :c :n}
|
|
{if {equal? :b #}
|
|
then :c
|
|
else {mul.r :a {butlast :b}
|
|
{add {muln :a 0 {lastchar :b}}{zeros :n} :c} {+ :n 1}}
|
|
}}}
|
|
{lambda {:a :b}
|
|
{mul.r :a #:b 0 0}
|
|
}}
|
|
|
|
4) applying to the task
|
|
|
|
Due to JS numbers limits, we compute first 2^32 using the JS pow function, then 2^64 and 2^128 using the mul function.
|
|
|
|
2^32 = '{def p32 {pow 2 32}} -> '{p32} = 4294967296
|
|
2^64 = '{def p64 {mul {p32} {p32}}} -> '{p64} = 18446744073709551616
|
|
2^128 = '{def p128 {mul {p64} {p64}}} -> '{p128} = 340282366920938463463374607431768211456
|
|
|
|
5) a more effective implementation
|
|
|
|
Lambdatalk can be helped by the lib_BN javascript library from Jonas Raoni Soares Silva
|
|
and stored in a wiki page called by a {require lib_BN} command, computing becomes fast:
|
|
|
|
2^32 = {def p32 {BN.pow 2 32}} -> {p32} = 4294967296
|
|
2^64 = {def p64 {BN.* {p32} {p32}}} -> {p64} = 18446744073709551616
|
|
2^128 = {def p128 {BN.* {p64} {p64}}} -> {p128} = 340282366920938463463374607431768211456
|
|
|
|
This can be tested in http://lambdaway.free.fr/lambdaspeech/?view=numbers8
|