Task

Explicitly implement   long multiplication.

This is one possible approach to arbitrary-precision integer algebra.



For output, display the result of    264 * 264.

Optionally, verify your result against builtin arbitrary precision support.

The decimal representation of    264    is:

18,446,744,073,709,551,616

The output of    264 * 264    is    2128,    and is:

340,282,366,920,938,463,463,374,607,431,768,211,456



 
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 
 