lambdaspeech :: numbers8

1 | list | login |load

| |

_h1 long mult rosetta test

_ul [[http://www.rosettacode.org/wiki/Long_multiplication|http://www.rosettacode.org/wiki/Long_multiplication]]

_p Natural positive numbers are defined as strings, for instance 123 -> "123". '{lambda talk} has a small set of primitives working on strings, {code [equal?, empty?, chars, charAt, substring]}.

{prewrap

1) 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}}}
}}  
-> {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}}}
}}

2) 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}}}
-> {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}}}

3) 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}}}}}

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{sup 32} = '{def p32 {pow 2 32}} -> {def p32 {pow 2 32}} = {p32}
2{sup 64} = '{def p64 {mul {p32} {p32}}} -> {def p64 {mul {p32} {p32}}} = {p64}
2{sup 128} = '{def p128 {mul {p64} {p64}}} -> {def p128 {mul {p64} {p64}}} = {p128}

}