lambdaspeech :: numbers6

1 | list | login |load

| |

_h1 big add & mul

_p In this page we add and multiply positive natural decimal numbers of any size. We use nothing but 3 '{lambda talk} primitives [{b equal?, chars, charAt}] working on words and currently JS arithmetic reduced to the {b +} operator applied to numbers in range [{b 0,18+1}]. JS arithmetic could be finally avoided, see notes at the end.

{{hide} °°

LAMBDATALK.DICT['lastchar'] = function() {
  var w = arguments[0].trim();
  return w.charAt(w.length-1)
};
LAMBDATALK.DICT['butlast'] = function() {
  var w = arguments[0].trim();
  return w.slice(0, w.length-1)
};
LAMBDATALK.DICT['zeroes'] = function() {
  var n = arguments[0].trim();
  for (var s='', i=0; i<n; i++)
    s += '0'
  return s
};

°°}

_h3 1) helper functions

{prewrap
'{def lastchar                     // {lastchar abcdef} -> f
 {lambda {:w}
  {charAt {- {chars :w} 1} :w}}}     
-> {def lastchar
 {lambda {:w}
  {charAt {- {chars :w} 1} :w}}}

'{def butlast                      // {butlast abcdef} -> abcde
 {lambda {:w}
  {substring 0 {- {chars :w} 1} :w}}} 
-> {def butlast
 {lambda {:w}
  {substring 0 {- {chars :w} 1} :w}}}

'{def zeroes                       // {zeroes 3} -> 000
 {lambda {:n}
  {if {< :n 1}
   then 
   else 0{zeroes {- :n 1}}}}}
-> {def zeroes
 {lambda {:n}
  {if {< :n 1}
   then 
   else 0{zeroes {- :n 1}}}}}
}

_p Note that adding as primitives to the dictionary these 3 helper functions could divide by 2 the computing time. See [[numbers7]].

_h3 2) addition

{pre
9876 + 543 = {+ 9876 543}

a       b       x + y + d    dz    d z    c
=================================================
'9876'  '0543'          0                 ''
'9876'  '0543'  6 + 3 + 0 -> 09 -> 0 9 -> '9' 
'987'   '054'   7 + 4 + 0 -> 11 -> 1 1 -> '19'
'98'    '05'    8 + 5 + 1 -> 14 -> 1 4 -> '419'
'9'     '0'     9 + 0 + 1 -> 10 -> 1 0 -> '0419'
''      ''      .   .   1 -> 1  -> 1 . -> '10419'
=================================================
}

{pre
'{def add

{def add.r
  {lambda {:a :b :c :d}                         ; #:a #:b accum carry
   {if {equal? :a #}                            ; word #:a reduced to #
    then {if {equal? :d 1} then 1 else}{butlast :c}  ; 1 added to accum or not
    else {let { {:a :a} {:b :b} {:c :c}         ; no free vars -> manual closure
                {:d {+ :d {lastchar :a} {lastchar :b}}} }  ; d + x + y
     {add.r {butlast :a}                        ; #:a minus last char
            {butlast :b}                        ; #:b minus last char
            {lastchar :d}:c                     ; last char of :d added to accum
            {if {equal? {chars :d} 1} then 0 else 1}} }}}}  ; :d = 0 or 1

{lambda {:a :b}
  {{lambda {:a :b :n}                           ; :a :b and max length
    {add.r #{zeroes :a {- :n {chars :a}}}       ; add # and zeros to :a
           #{zeroes :b {- :n {chars :b}}}       ; add # and zeros to :b
           #                                    ; accumulator = '#'
           0}                                   ; carry = 0
   } :a :b {max {chars :a} {chars :b}}} }}      ; compute max length of :a and :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 #{zeroes {- :n {chars :a}}}:a
           #{zeroes {- :n {chars :b}}}:b  # 0}
  } :a :b {max {chars :a} {chars :b}}}
}}
}

_h3 3) multiplication

{pre
9876 * 543 = {* 9876 543}

9876 * 3 = {* 9876 3}    ->   {* 9876 3}
+ 9876 * 4 = {* 9876 4} 0  ->  {* 9876 4}0
+ 9876 * 5 = {* 9876 5} 00 -> {* 9876 5}00
=                        {* 9876 543}
}

{pre
'{def muln              // {muln 9876 3} -> 29628
 {def muln.r
  {lambda {:a :b :n}
   {if {< :n 1}
    then :b
    else {muln.r :a {add :a :b} {- :n 1}}}}}
 {lambda {:a :n} 
  {muln.r :a 0 :n}}}
-> {def muln
 {def muln.r
  {lambda {:a :b :n}
   {if {< :n 1}
    then :b
    else {muln.r :a {add :a :b} {- :n 1}}}}}
 {lambda {:a :n} 
  {muln.r :a 0 :n}}}

'{def mul               //  {mul 9876 543} -> 5362668
 {def mul.r
  {lambda {:a :b :c :n}
   {if {equal? :b #}
    then :c
    else {mul.r :a {butlast :b}
         {add {muln :a {lastchar :b}}{zeroes :n} :c} {+ :n 1}}}}}
 {lambda {:a :b}
  {mul.r :a #:b 0 0}}}
-> {def mul
 {def mul.r
  {lambda {:a :b :c :n}
   {if {equal? :b #}
    then :c
    else {mul.r :a {butlast :b}
         {add {muln :a {lastchar :b}}{zeroes :n} :c} {+ :n 1}}}}}
 {lambda {:a :b}
  {mul.r :a #:b 0 0}}}
}

_h3 4) factorial

_p Let's build the factorial function built on {b +, -, *, <} and on {b add, -, mul, <}

{pre
'{def fac
 {lambda {:a :b}
  {if {< :b 1}
   then :a
   else {fac {* :a :b} {- :b 1}}}}}       // use *
-> {def fac
 {lambda {:a :b}
  {if {< :b 1}
   then :a
   else {fac {* :a :b} {- :b 1}}}}}

'{def bigfac
 {lambda {:a :b}
  {if {< :b 1}
   then :a
   else {bigfac {mul :a :b} {- :b 1}}}}}  // use mul
-> {def bigfac
 {lambda {:a :b}
  {if {< :b 1}
   then :a
   else {bigfac {mul :a :b} {- :b 1}}}}}
}

_h3 5) testing

_p We compare JS [{b + & *}] and '{lambda talk} [{b add & mul}]

{prewrap
'{+ 1000000000000000000000 2}
-> {+ 1000000000000000000000 2}

'{add 1000000000000000000000 2}
-> {add 1000000000000000000000 2}            (2ms)

'{* 1000000000000000000000 2}
-> {* 1000000000000000000000 2}

'{mul 1000000000000000000000 2}
-> {mul 1000000000000000000000 2}            (15ms)

'{fac 1 6}
-> {fac 1 6}

'{bigfac 1 6}
-> {bigfac 1 6}                               (13ms)

'{fac 1 50}
-> {fac 1 50}

'{bigfac 1 50}                        (600ms)
-> 30414093201713378043612608166064768844377641568960512000000000000

}

_h3 notes

_p With big numbers - over ~20 digits - {b + & *} return inexact values (false integers or float numbers) while {b add & mul} return exact values. For numbers below 15 digits time computing with {b add & mul} and {b + & *} stays comparable.

_p In order to avoid any JS arithmetic, the {b +} operator could be replaced by a small table.

{pre
.  1  2  3  4  5  6  7  8  9
1  2  3  4  5  6  7  8  9 10
2  3  4  5  6  7  8  9 10 11
3  4  5  6  7  8  9 10 11 12
4  5  6  7  8  9 10 11 12 13
5  6  7  8  9 10 11 12 13 14
6  7  8  9 10 11 12 13 14 15
7  8  9 10 11 12 13 14 15 16
8  9 10 11 12 13 14 15 16 17
9 10 11 12 13 14 15 16 17 18
}

_p Computing with nothing but 3 operators working on words, {b equal?, chars, charAt}, would lead close to the λ-calculus foundations with a rather efficient implementation of natural numbers, compared to the approach introduced in the page [[lambda zen|?view=PLR]] where numbers are built on lists.

_p {i This is a very satisfying result for the mind!}

_p {i Alain Marty 2018/11/18}