lambdaway :: binaries

6 | list | login |load

| |

_h1 binaries I|O

_p In this study the goal is to build a set of arithmetic operators, {b ADD, SUB, MUL, POW, DIV, ...}, dealing with {b big binary numbers} implemented as words made of bits, "{code I}" and "{code O}", extending the javascript arithmetic limited to integers below {b 2{sup 32}}.

_h2 1) addition
 
_h3 1.1) adding two 1-bits

{pre 
'{def ADD.bit
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}{XOR :x {XOR :a :b}} }} 
-> {def ADD.bit
 {lambda {:x :a :b}
  {OR {AND :a :b}
      {OR {AND :x :a}
          {AND :x :b}}}{XOR :x {XOR :a :b}} }}

'{ADD.bit O O O} -> {ADD.bit O O O}
'{ADD.bit O O I} -> {ADD.bit O O I}
'{ADD.bit O I O} -> {ADD.bit O I O}
'{ADD.bit O I I} -> {ADD.bit O I I}
}

_h3 1.2) adding two n-bits

{pre
'{def ADD

{def ADD.pad
  {lambda {:n}
   {if {= :n 0}
    then
    else O{ADD.pad {- :n 1}} }}}

{def ADD.rec
  {lambda {:a :b :x :i}
   {if {< :i 0}
    then {if {W.equal? {W.first :x} O} 
          then {W.rest :x}
          else :x}         
    else {let { {:a :a} 
                {:b :b}
                {:x {ADD.bit :x {W.get :i :a} {W.get :i :b}}}
                {:i :i}
              } {ADD.rec :a :b {W.first :x} {- :i 1} }{W.last :x} }}}}

{lambda {:a :b}
  {let { {:a :a} 
         {:b :b}
         {:l {max {W.length :a} {W.length :b}}}
       } {ADD.rec {ADD.pad {- :l {W.length :a}}}:a 
                  {ADD.pad {- :l {W.length :b}}}:b
                  O 
                  {- :l 1}} }}}
-> {def ADD

{def ADD.pad
  {lambda {:n}
   {if {= :n 0}
    then
    else O{ADD.pad {- :n 1}}}}}

{def ADD.rec
  {lambda {:a :b :x :i}
   {if {< :i 0}
    then {if {W.equal? {W.first :x} O} then {W.rest :x} else :x}         
    else {let { {:x {ADD.bit :x {W.get :i :a} {W.get :i :b}}}
                {:a :a} {:b :b} {:i :i}
              } {ADD.rec :a :b {W.first :x} {- :i 1} }{W.last :x} }}}}

{lambda {:a :b}
  {let { {:a :a} {:b :b}
         {:l {max {W.length :a} {W.length :b}}}
       } {ADD.rec {ADD.pad {- :l {W.length :a}}}:a 
                  {ADD.pad {- :l {W.length :b}}}:b
                  O 
                  {- :l 1}} }}}

'{ADD O O}   
-> {ADD O O}
'{ADD I I}   
-> {ADD I I}  
'{ADD II I}  
-> {ADD II I}
'{ADD III I} 
-> {ADD III I} 
'{ADD IIIIIIIIIIIIIIIIIIII I} 
 -> {ADD IIIIIIIIIIIIIIIIIIII I}
}

{prewrap

'{b2d {ADD {d2b 99999999999999999999999999999999999999999} {d2b 1}}}
->            {b2d {ADD {d2b 99999999999999999999999999999999999999999} {d2b 1}}}
}

_h2 2) subtraction

_h3 2.1) useful functions
_p Subtracting two numbers will be done by adding to the first the two's complement of the second. The two's complement is calculated by inverting the bits and adding one.
{pre
'{def INV
 {lambda {:x}
  {S.replace 0 by O in 
  {S.replace 1 by I in 
  {S.replace I by 0 in 
  {S.replace O by 1 in :x}}}}}}
-> {def INV
 {lambda {:x}
  {S.replace 0 by O in 
  {S.replace 1 by I in 
  {S.replace I by 0 in 
  {S.replace O by 1 in :x}}}}}}

'{INV O} -> {INV O}
'{INV I} -> {INV I}
'{INV IOI}  -> {INV IOI}
'{INV IOOO} -> {INV IOOO}
}

_p It will be useful to test if all bits of a number are {b O}.

{pre
'{def ZERO?
 {lambda {:n}
  {if {W.equal? :n O}
   then true
   else {if {W.equal? {W.first :n} I}
   then false
   else {ZERO? {W.rest :n}}}}}}
-> {def ZERO?
 {lambda {:n}
  {if {W.equal? :n O}
   then true
   else {if {W.equal? {W.first :n} I}
   then false
   else {ZERO? {W.rest :n}}}}}}

'{ZERO? O} -> {ZERO? O}
'{ZERO? I} -> {ZERO? I}
'{ZERO? OOOO} -> {ZERO? OOOO}
'{ZERO? OOIO} -> {ZERO? OOIO}

}

_h3 2.2) the {b SUB} function

{pre
'{def SUB
 {def SUB.in
  {lambda {:a :b}
   {ADD :a {ADD {INV :b} I}}}}
 {lambda {:a :b}
  {let { {:a :a} {:b :b}
         {:l {max {W.length :a} {W.length :b}} }
       } {W.slice 1 {+ :l 1} 
          {SUB.in {ADD.pad {- :l {W.length :a}}}:a
                  {ADD.pad {- :l {W.length :b}}}:b} }}}}
-> {def SUB
 {def SUB.in
  {lambda {:a :b}
   {ADD :a {ADD {INV :b} I}}}}
 {lambda {:a :b}
  {let { {:a :a} {:b :b}
         {:l {max {W.length :a} {W.length :b}} }
       } {W.slice 1 {+ :l 1} 
          {SUB.in {ADD.pad {- :l {W.length :a}}}:a
                  {ADD.pad {- :l {W.length :b}}}:b} }}}}

'{b2d {SUB {d2b 123} {d2b 13}}}
-> {b2d {SUB {d2b 123} {d2b 13}}}
'{b2d {SUB {d2b 1000} {d2b 1}}}
-> {b2d {SUB {d2b 1000} {d2b 1}}}
'{b2d {SUB {d2b 100000000000000000000000000000000} {d2b 1}}}
->              {b2d {SUB {d2b 100000000000000000000000000000000} {d2b 1}}}
}

_h3 2.3) {b fibonacci}

{pre
'{def FIB
 {lambda {:a :b :n}
  {if {ZERO? :n}
   then :a
   else {FIB {ADD :a :b} :a {SUB :n I}}}}}
-> {def FIB
 {lambda {:a :b :n}
  {if {ZERO? :n}
   then :a
   else {FIB {ADD :a :b} :a {SUB :n I}}}}}

'{b2d {FIB O I {d2b 10}}}
-> {b2d {FIB O I {d2b 10}}}

'{b2d {FIB O I {d2b 100}}}   // 230ms
-> 354224848179261915075

'{S.map {lambda {:c} {b2d {FIB O I {d2b :c}}}} {S.serie 0 20}}
-> 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
}

_h2 3) multiplication

_h3 3.1) shift functions

{pre
'{def shiftl {lambda {:n} :nO}}
-> {def shiftl {lambda {:n} :nO}}

'{def shiftr 
 {lambda {:n}
  {if {or {W.equal? :n O} {W.equal? :n I}}
   then O
   else {W.slice 0 {- {W.length :n} 1} :n}}}}
-> {def shiftr 
 {lambda {:n}
  {if {or {W.equal? :n O} {W.equal? :n I}}
   then O
   else {W.slice 0 {- {W.length :n} 1} :n}}}}

'{shiftl IOOO} -> {shiftl IOOO}
'{shiftr IOOO} -> {shiftr IOOO}
'{shiftr O}    -> {shiftr O}
'{shiftr I}    -> {shiftr I}
}

_h3 3.2) the MUL function

{pre
'{def MUL

{def MUL.rec
  {lambda {:a :b :c }
   {if {W.equal? :a O}
    then :c
    else
     {MUL.rec {shiftr :a}
              {shiftl :b}
              {if {W.equal? {W.last :a} I} then {ADD :c :b} else :c}} }}}

{lambda {:a :b}
  {MUL.rec :a :b O}}}
-> {def MUL
 {def MUL.rec
  {lambda {:a :b :c }
   {if {W.equal? :a O}
    then :c
    else
     {MUL.rec {shiftr :a}
              {shiftl :b}
              {if {W.equal? {W.last :a} I} then {ADD :c :b} else :c}} }}}

{lambda {:a :b}
  {MUL.rec :a :b O}}}

'{MUL IIII III}    // 15*7 = 1111*111 = 11O1OO1 = {* 15 7}
-> {MUL IIII III}

'{b2d {MUL {d2b 18446744073709551616}
          {d2b 18446744073709551616}}} 
-> {b2d {MUL {d2b 18446744073709551616}
             {d2b 18446744073709551616}}}
}

_h3 3.3) the factorial

{pre
'{def FAC
 {lambda {:n}
  {if {ZERO? :n}
   then I
   else {MUL :n {FAC {SUB :n I}}}}}}
-> {def FAC
 {lambda {:n}
  {if {ZERO? :n}
   then I
   else {MUL :n {FAC {SUB :n I}}}}}}

'{b2d {FAC {d2b 6}}}
-> {b2d {FAC {d2b 6}}}

'{b2d {FAC {d2b 50}}}  // 740ms
-> 30414093201713378043612608166064768844377641568960512000000000000 
}

_h2 4) the euclidean division

_p first algorithm

{pre
a//b -> (q,r)

'{/ 7 2} = 3.5 
'{// 7 2} = (3,1)

a  b  q  x
==========
7  2  1  2        < 7
7  2  2  2+2 = 4  < 7
7  2  3  2+4 = 6  < 7 -> q=3, r=7-2*3 -> (3,1)
7  2  4  2+6 = 8  > 7 -> oops!

'{def divmod   
 {def divmod.rec                       
  {lambda {:a :b :q :x}
   {if {> :x :a}            
    then {cons {- :q 1} {- :a {* :b {- :q 1}}}} 
    else {divmod.rec :a :b {+ :q 1} {+ :b :x}} }}}
 {lambda {:a :b}
  {divmod.rec :a :b 1 :b}}} 
-> {def divmod   
 {def divmod.rec                       
  {lambda {:a :b :q :x}
   {if {> :x :a}            
    then {cons {- :q 1} {- :a {* :b {- :q 1}}}} 
    else {divmod.rec :a :b {+ :q 1} {+ :b :x}} }}}
 {lambda {:a :b}
  {divmod.rec :a :b 1 :b}}}

'{divmod 7 2}   -> {divmod 7 2}
'{divmod 218 6} -> {divmod 218 6} // '{+ {* 36 6} 2}
}

_p Using shifts

{pre
'{def euclide
 {def euclide.init
  {lambda {:a :x :n}
   {if {<= :x :a}
    then {euclide.init :a {* :x 2} {+ :n 1}}
    else {cons :n :x}}}}
 {def euclide.loop
  {lambda {:n :x :q :r}
   {if {> :n 0}
    then {let { {:n {- :n 1}}
                {:x {floor {/ :x 2}}}
                {:q {* :q 2}}
                {:r :r}
              } {euclide.loop :n :x {if {>= :r :x} 
                                     then {+ :q 1} {- :r :x} 
                                     else :q :r}} }
    else {cons :q :r}
 }}}
 {lambda {:a :b}
  {let { {:xn {euclide.init :a :b 0}}
         {:q 0}                  
         {:r :a}
       } {euclide.loop {car :xn} {cdr :xn} :q :r}
}}} 
-> {def euclide
 {def euclide.init
  {lambda {:a :x :n}
   {if {<= :x :a}
    then {euclide.init :a {* :x 2} {+ :n 1}}
    else {cons :n :x}}}}
 {def euclide.loop
  {lambda {:n :x :q :r}
   {if {> :n 0}
    then {let { {:n {- :n 1}}
                {:x {floor {/ :x 2}}}
                {:q {* :q 2}}
                {:r :r}
              } {euclide.loop :n :x {if {>= :r :x} 
                                     then {+ :q 1} {- :r :x} 
                                     else :q :r}} }
    else {cons :q :r}
 }}}
 {lambda {:a :b}
  {let { {:xn {euclide.init :a :b 0}}
         {:q 0}                  
         {:r :a}
       } {euclide.loop {car :xn} {cdr :xn} :q :r}
}}}

'{euclide 7 2}              -> {euclide 7 2} 
'{euclide 8 2}              -> {euclide 8 2}
'{euclide 218 6}            -> {euclide 218 6} 
'{euclide 123456789 123456} -> {euclide 123456789 123456}
}

_h2 5) primitives and functions used in this page

_ul 5.1) Lambdatalk comes with a set of primitives acting on words:
{prewrap
{W.lib}
}

_ul 5.2) Lambdatalk has a set of boolean primitives {b not, and, or} returning {b true} or {b false}. We add a set of boolean primitives returning {b O} or {b I} choosen in this page as booleans.
{pre
{quote 
NOT: {NOT I} {NOT O}
AND: {AND I I} {AND I O} {AND O I} {AND O O}
OR:  {OR I I} {OR I O} {OR O I} {OR O O}
XOR: {XOR I I} {XOR I O} {XOR O I} {XOR O O}}
-> 
NOT: {NOT I} {NOT O}
AND: {AND I I} {AND I O} {AND O I} {AND O O}
OR:  {OR I I} {OR I O} {OR O I} {OR O O}
XOR: {XOR I I} {XOR I O} {XOR O I} {XOR O O}
}

_ul 5.3) Finally we add the {b d2b} & {b b2d} primitives to [[convert large numbers|https://stackoverflow.com/questions/39334494/converting-large-numbers-from-binary-to-decimal-and-back-in-javascript]] between binaries and decimals.

{pre
'{d2b 7} -> {d2b 7}
'{b2d III} -> {b2d III}

'{d2b {pow 2 32}} -> {d2b {pow 2 32}}
'{b2d IOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO} -> {b2d IOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO}
}
 
_p {i alain marty | 2022/03/27}

{script 
LAMBDATALK.DICT['NOT'] = function() {
  var args = arguments[0].trim(),
       res = !(args==='I');
  return (res)? 'I' : 'O'
};
LAMBDATALK.DICT['AND'] = function() {
  var args = arguments[0].trim().split(' '),
       res = (args[0]==='I') && (args[1]==='I');
  return (res)? 'I' : 'O'
};
LAMBDATALK.DICT['OR'] = function() {
  var args = arguments[0].trim().split(' '),
       res = (args[0]==='I') || (args[1]==='I');
  return (res)? 'I' : 'O'
};
LAMBDATALK.DICT['XOR'] = function() {
  var args = arguments[0].trim().split(' '),
         a = (args[0]==='I'),
         b = (args[1]==='I'),
       res = ( a || b ) && !( a && b );
  return (res)? 'I' : 'O'
};

// https:/ /stackoverflow.com/questions/39334494/converting-large-numbers-from-binary-to-decimal-and-back-in-javascript
// https:/ /www.codegrepper.com/code-examples/javascript/frameworks/ember/large+binary+number+to+decimal+javascript

LAMBDATALK.DICT['b2d'] = function() {  // {b2d IOO} -> 4
  var args = arguments[0].trim().replace(/I/g, '1').replace(/O/g, '0');
  return BigInt('0b' + args) 
};
LAMBDATALK.DICT['d2b'] = function() {  // {d2b 4} -> IOO
  var args = arguments[0].trim();
  return BigInt(args).toString(2).replace(/1/g, 'I').replace(/0/g, 'O')
};

LAMBDATALK.DICT['zero?'] = function() {  // {zero? OOIO} -> false
  var args = arguments[0].trim();
  return (args.match( 'I' ) === null)
}

}