lambdaway :: binary

5 | list | login |load

| |

_h1 binary addition {sup (with lists | [[array only|?view=binary_digit2]])}

{macro "(then|else) to <span style="color:#ff0">€1</span>}
{{block}

_h2 introduction

_p We compare three implementation of binary addition:

_ul 1) numbers as words of bits, for instance {b 10{sub 10} = 1010{sub 2}}
_ul 2) numbers as arrays of bits, for instance {b 10{sub 10} = [1,0,1,0]{sub 2}}
_ul 3) numbers as lists of booleans, for instance {b 10{sub 10} = (true false true false){sub 2}}

_p The addition algorithm is sketched in the following example, 7+1 = 8:

{pre
.        1)            2)           3)           4)
         <             < .          < . .        < . . .
         0             1            1            1
     1 1 1           1 1 1          1 1 1          1 1 1
+    0 0 1      +    0 0 1      +   0 0 1      +   0 0 1
=        0      =      0 0      =   0 0 0      = 1 0 0 0
}

_p We will have to translate numbers between decimal, binary and boolean representations.

_h3 a) dec2bin & bin2dec

_p The {b convert from to number} is already defined as a primitive translating numbers from a base to an another. The {b dec2bin} function waits for two values, the number of bits wanted for the binary representation and the decimal number. It's up to the user to choose a number of bits sufficient enough for the computations to be valid.
{pre
°°°
{def dec2bin
 {def zpadd
  {lambda {:n}
   {if {= :n 0}
    then
    else 0{zpadd {- :n 1}}}}}
 
 {def dec2bin.r
 {lambda {:dec}
  {if {= :dec 0}
   then 0
   else {if {< :dec 2}
         then 1
         else {dec2bin.r {floor {/ :dec 2}}}{% :dec 2} }}}}

{lambda {:n :dec}
  {let { {:n :n} {:b {dec2bin.r :dec}}
       } {zpadd {- :n {W.length :b}}}:b}}}

{def bin2dec
 {def bin2dec.r
  {lambda {:p :r}
   {if {A.empty? :p}
    then :r
    else {bin2dec.r {A.rest :p} {+ {A.first :p} {* 2 :r}}}}}}
 {lambda {:p} {bin2dec.r {A.split :p} 0}}}
°°°
'{def dec2bin
 {def zpadd
  {lambda {:n}
   {if {= :n 0}
    "then
    "else 0{zpadd {- :n 1}}}}}
 {lambda {:n :dec}
  {let { {:n :n} {:b {convert 10 2 :dec}}
       } {zpadd {- :n {W.length :b}}}:b}}}
-> {def dec2bin 
 {def zpadd
  {lambda {:n}
   {if {= :n 0}
    then
    else 0{zpadd {- :n 1}}}}}
 {lambda {:n :dec}
  {let { {:n :n} {:b {convert 10 2 :dec}}
       } {zpadd {- :n {W.length :b}}}:b}}}

'{def bin2dec {lambda {:n} {convert 2 10 :n}}}
-> {def bin2dec {lambda {:n} {convert 2 10 :n}}}

'{dec2bin 16 5}    -> {dec2bin 16 5}
'{dec2bin 16 50}   -> {dec2bin 16 50}
'{dec2bin 16 9000} -> {dec2bin 16 9000}

'{bin2dec 101}            -> {bin2dec 101}
'{bin2dec 110010}         -> {bin2dec 110010}
'{bin2dec 10001100101000} -> {bin2dec 10001100101000}
}

_h3 b) bin2bool & bool2bin

_p It's just a matter of replacing words made of {b [0,1]}, by lists of booleans, {b [false true]}, and vice-versa.
{pre
'{def bin2bool            
 {def bin2bool.r     
  {lambda {:s}
   {if {= {S.length :s} 1}
    "then {cons :s nil}
    "else {cons {S.first :s} {bin2bool.r {S.rest :s}}}} }}
 {lambda {:w}
  {bin2bool.r {S.replace _ by space in
              {S.replace 1 by true_ in 
              {S.replace 0 by false_ in :w}}}}}}
-> {def bin2bool            
 {def bin2bool.r     
  {lambda {:s}
   {if {= {S.length :s} 1}
    then {cons :s nil}
    else {cons {S.first :s} {bin2bool.r {S.rest :s}}}} }}
 {lambda {:w}
  {bin2bool.r {S.replace _ by space in
              {S.replace 1 by true_ in 
              {S.replace 0 by false_ in :w}}}}}}

'{def bool2bin            
 {lambda {:b}
  {S.replace \s by in
  {S.replace false by 0 in
  {S.replace true by 1 in {L.disp :b}}}}}}
-> {def bool2bin            
 {lambda {:b}
  {S.replace \s by in
  {S.replace false by 0 in
  {S.replace true by 1 in {L.disp :b}}}}}}

'{L.disp {bin2bool 0011}}
-> {L.disp {bin2bool 0011}}

'{bool2bin
 {cons false
 {cons true
 {cons true
 {cons true nil}}}}}
-> {bool2bin
 {cons false
 {cons true
 {cons true
 {cons true nil}}}}}
}

} ;; end block

{{block}

_h2 1) as bits

_p This representation uses javascript numbers, Math operators, and words and array structures.

_h3 1.1) stored as words

{pre
'{def W.add
 {def W.add.r
  {lambda {:a :b :s :c :i}
   {if {< :i 0}
    "then {if {= :c 1} then 1 else}:s
    "else {let { {:a :a} {:b :b} {:s :s} {:i :i} 
                {:d {+ {W.get :i :a} {W.get :i :b} :c}}
              } {W.add.r :a :b 
                         {if {> :d 1} "then {- :d 2} "else :d}:s
                         {if {> :d 1} "then 1 "else 0}
                         {- :i 1}}}}}}  
 {lambda {:a :b} 
   {S.replace # by in
    {W.add.r :a :b # 0 {- {W.length :a} 1}}}}} 
-> {def W.add
 {def W.add.r
  {lambda {:a :b :s :c :i}
   {if {< :i 0}
    then {if {= :c 1} then 1 else}:s
    else {let { {:a :a} {:b :b} {:s :s} {:i :i} 
                {:d {+ {W.get :i :a} {W.get :i :b} :c}}
              } {W.add.r :a :b 
                         {if {> :d 1} then {- :d 2} else :d}:s
                         {if {> :d 1} then 1 else 0}
                         {- :i 1}}}}}}  
 {lambda {:a :b} 
   {S.replace # by in
    {W.add.r :a :b # 0 {- {W.length :a} 1}}}}} 
}
_p Note that we use word lambdatalk primitives and a little bit of javascript maths.
_p Testing

{pre
'{W.add 111 001}
-> {W.add 111 001}

'{bin2dec
 {W.add {dec2bin 3 7}         // using 3 bits: 111
        {dec2bin 3 1}}}       // using 3 bits: 001
-> {bin2dec
 {W.add {dec2bin 3 7}
        {dec2bin 3 1}}}

'{bin2dec
 {W.add {dec2bin 32 {pow 2 31}}  // 2^31 = 2147483648
        {dec2bin 32  1}}}
-> {bin2dec
 {W.add {dec2bin 32 {pow 2 31}}
        {dec2bin 32  1}}}                    // 2^31 + 1
}

_h3 1.2) stored as arrays

{pre
'{def A.add
 {def A.add.r
  {lambda {:a :b :s :c :i}
   {if {< :i 0}
    then {if {= :c 0} then :s else {A.addfirst! 1 :s}}
    else {let { {:a :a} {:b :b} {:s :s} {:i :i} 
               {:d {+ {A.get :i :a} {A.get :i :b} :c}}
              } {A.add.r :a :b 
                         {A.addfirst! {if {= :d 2}
                                       then {- :d 2}
                                       else :d} :s}
                         {if {= :d 2} then 1 else 0}
                         {- :i 1}}}}}}   
 {lambda {:a :b}
  {A.join 
   {A.add.r {A.split :a}
          {A.split :b} 
          {A.new}
          0
          {- {W.length :a} 1}}}}}
-> {def A.add
 {def A.add.r
  {lambda {:a :b :s :c :i}
   {if {< :i 0}
    then {if {= :c 0} then :s else {A.addfirst! 1 :s}}
    else {let { {:a :a} {:b :b} {:s :s} {:i :i} 
               {:d {+ {A.get :i :a} {A.get :i :b} :c}}
              } {A.add.r :a :b 
                         {A.addfirst! {if {= :d 2} then {- :d 2} else :d} :s}
                         {if {= :d 2} then 1 else 0}
                         {- :i 1}}}}}}  
 {lambda {:a :b} 
  {A.join {A.add.r {A.split :a} {A.split :b} {A.new} 0 {- {W.length :a} 1}}}}}
}

_p {b Notes:} 
_ul 1) here also we use array lambdatalk primitives and a little bit of javascript maths,
_ul 2) there is a great similarity between the word and array approach, the later being probably lesser efficient.
_ul 3) the {i little bit} of javascript maths could be avoided with a reduced set of homemade arithmetic. This is left as an exercise...

_p Testing

{pre
'{A.add 1 1}  -> {A.add 1 1}

'{A.add 1111111111111111 
       0000000000000001}  
->  {A.add 1111111111111111 
       0000000000000001}

'{bin2dec
 {A.add {dec2bin 64 9223372036854776000}    // 2^63
        {dec2bin 64 9223372036854776000}}}  // 2^63
-> {bin2dec
 {A.add {dec2bin 64 9223372036854776000}
        {dec2bin 64 9223372036854776000}}} 
 = {pow 2 64} = 2^64

}
} ;; end block

{{block}

_h2 2) as booleans

_p This representation uses nothing but javascript booleans, no numbers, no Math operators, no array structure.

_h3 2.1) booleans

_p The {b or}, {b and} and {b not} operators are defined as primitives. We add the {b xor} user defined predicate.

{pre
'{def xor 
 {lambda {:a :b}
  {or {and :a {not :b}} {and :b {not :a}}}}}
-> {def xor 
 {lambda {:a :b}
  {or {and :a {not :b}} {and :b {not :a}}}}}
}

_h3 2.2) lists

{pre
'{def L.nil? {lambda {:l} {W.equal? :l nil}}}
-> {def L.nil? {lambda {:l} {W.equal? :l nil}}}

'{def L.disp
 {lambda {:l}
  {if {L.nil? :l}
   then
   else {car :l} {L.disp {cdr :l}}}}}
-> {def L.disp
 {lambda {:l}
  {if {L.nil? :l}
   then
   else {car :l} {L.disp {cdr :l}}}}}

'{def L.rev
 {def L.rev.r
  {lambda {:a :b}
   {if {L.nil? :a}
    then :b
    else {L.rev.r {cdr :a} {cons {car :a} :b}}}}}
 {lambda {:l}
  {L.rev.r :l nil}}}
-> {def L.rev
 {def L.rev.r
  {lambda {:a :b}
   {if {L.nil? :a}
    then :b
    else {L.rev.r {cdr :a} {cons {car :a} :b}}}}}
 {lambda {:l}
  {L.rev.r :l nil}}}
}

_p Testing

{pre
'{L.disp {cons false {cons true  {cons true  {cons true nil}}}}}
-> {L.disp {cons false {cons true  {cons true  {cons true nil}}}}}

'{L.disp {L.rev {cons false {cons true  {cons true  {cons true nil}}}}}}
-> {L.disp {L.rev {cons false {cons true  {cons true  {cons true nil}}}}}}
}

_h3 2.3) adding two 1-bit numbers

{pre
'{def B.add.bit.sum
 {lambda {:x :a :b}
  {xor :x {xor :a :b}}}}
-> {def B.add.bit.sum
 {lambda {:x :a :b}
  {xor :x {xor :a :b}}}}

'{def B.add.bit.carry 
 {lambda {:x :a :b}
  {or {and :a :b}
      {or {and :x :a}
          {and :x :b}}}}}
-> {def B.add.bit.carry
 {lambda {:x :a :b}
  {or {and :a :b}
      {or {and :x :a}
          {and :x :b}}}}}

'{def B.add.bit
 {lambda {:x :a :b}
  {cons {B.add.bit.sum :x :a :b}
        {B.add.bit.carry :x :a :b}}}}
-> {def B.add.bit
 {lambda {:x :a :b}
  {cons {B.add.bit.sum :x :a :b}
        {B.add.bit.carry :x :a :b}}}}
}

_p Testing

{pre
'{car {B.add.bit false false false}} '{cdr {B.add.bit false false false}}
'{car {B.add.bit false false true}}  '{cdr {B.add.bit false false true}}
'{car {B.add.bit false true false}}  '{cdr {B.add.bit false true false}}
'{car {B.add.bit FALSE true true}}   '{cdr {B.add.bit false true true}}
->
  s    x       a+b(x)    s(x)
FALSE FALSE // 0+0(0) -> 0(0)
TRUE FALSE  // 0+1(0) -> 1(0)
TRUE FALSE  // 1+0(0) -> 1(0)
FALSE TRUE  // 0+0(0) -> 0(1)
}

_h3 2.4) adding two n-bits numbers

{pre
'{def B.add
 {def B.add.rec
  {lambda {:x :a :b}
   {if {or {L.nil? :a} {L.nil? :b}} 
    then {{lambda {:x} {if {car :x} then :x else {cdr :x}}
          } {cons :x nil}}
    else {{lambda {:x :a :b}
           {cons {car :x} {B.add.rec {cdr :x} {cdr :a} {cdr :b}} } 
          } {B.add.bit :x {car :a} {car :b}} :a :b} }}}
 {lambda {:a :b}
  {L.rev {B.add.rec false {L.rev :a} {L.rev :b}}} }}
-> {def B.add
 {def B.add.rec
  {lambda {:x :a :b}
   {if {or {L.nil? :a} {L.nil? :b}} 
    then {{lambda {:x} {if {car :x} then :x else {cdr :x}}
              } {cons :x nil}}
    else {{lambda {:x :a :b}
           {cons {car :x} {B.add.rec {cdr :x} {cdr :a} {cdr :b}} } 
         } {B.add.bit :x {car :a} {car :b}} :a :b} }}}
 {lambda {:a :b}
  {L.rev {B.add.rec false {L.rev :a} {L.rev :b}}} }}
}

_p Testing

{pre
'{L.disp
 {B.add
  {cons false {cons true  {cons true  {cons true nil}}}}
  {cons false {cons false {cons false {cons true nil}}}} }} 
-> {L.disp
 {B.add
  {cons false {cons true  {cons true  {cons true nil}}}}
  {cons false {cons false {cons false {cons true nil}}}} }}

'{bool2bin
 {B.add {bin2bool 111}
        {bin2bool 001} }}
-> {bool2bin
 {B.add {bin2bool 111}
        {bin2bool 001} }}

'{bin2dec {bool2bin
 {B.add {bin2bool {dec2bin 64 {pow 2 63}}}
        {bin2bool {dec2bin 64 {pow 2 63}}}}}}
-> {bin2dec {bool2bin
 {B.add {bin2bool {dec2bin 64 {pow 2 63}}}
        {bin2bool {dec2bin 64 {pow 2 63}}}}}}
}

_p And it works with big numbers, for instance {b 2{sup 128}}

{prewrap
;;{W.length 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001}

'{def BIGN 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111} -> {def BIGN 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111} = {bin2dec {BIGN}}  // javascript approx

'{def BIG1 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001} -> {def BIG1 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001} = {bin2dec {BIG1}}

'{bool2bin
 {B.add {bin2bool {BIGN}}
        {bin2bool {BIG1}}}} 
-> {bool2bin
 {B.add {bin2bool {BIGN}}
        {bin2bool {BIG1}}}}

}

_p to be compared with the exact precision given by the {b long_add} primitive.

{prewrap
'{long_add 340282366920938463463374607431768211455 1}
-> {long_add 340282366920938463463374607431768211455 1}  // 2{sup 128}

'{dec2bin 129 340282366920938463463374607431768211455}
-> {dec2bin 129 340282366920938463463374607431768211455}
}

} ;; end block

{{block}

_h2 conclusion

_p The last implementation is very close to the implementation built in [[λ-calculus using binary numbers of variable length|?view=oops6]]. The difference lies in the presence of the special form {b if then else} and the existence of booleans, which are given as primitives thanks to lambdatalk, and must instead be constructed as lambda aexpressions in λ-calculus

_p {i alain marty | 2021/10/31}

} ;; end block

{{hide}
{def block 
  div {@ style="display:inline-block; width:600px; vertical-align:top; padding:5px; "}}
}

{script 
LAMBDATALK.DICT['convert'] = function() {
  var args = LAMBDATALK.supertrim( arguments[0] ).split(" "); 
  return parseInt(args[2],args[0]).toString(args[1])
};
}

{style 
body { background:#444; } 
#page_frame { border:0; background:#444; width:600px; margin-left:0; }
#page_content { background:transparent; color:#fff; border:0; width:2600px; box-shadow:0 0 0; font-family:papyrus, optima; }
.page_menu { background:transparent; color:#fff; }
a { color:#f80; }
pre { box-shadow:0 0 8px #000; padding:5px; background:#444; color:#fff; font:normal 1.0em courier; }
b { color:cyan; }
h1 { font-size:4.0em; margin-left:0; }
h2 { font-size:3.0em; }
h3 { font-size:1.5em; }
}