lambdaway :: egyptian

3 | list | login |load

| |

_h1 egyptian division [[1|?view=egyptian_division]] | 2

_p Following and mixing [[Phix|https://rosettacode.org/wiki/Egyptian_division]] and  [[Python|https://rosettacode.org/wiki/Egyptian_division]].

{pre

'{def doublings
 {def doublings.loop
  {lambda {:a :d0 :d1}
   {if {> {A.last :d1} :a}
    then {A.new :d0 :d1}
    else {doublings.loop
           :a 
           {A.addlast! {+ {A.get 0 {A.last :d0}}
                          {A.get 0 {A.last :d0}} } :d0}
           {A.addlast! {+ {A.get 1 {A.last :d1}}
                          {A.get 1 {A.last :d1}} } :d1} } }}}
 {lambda {:a :b}  
  {doublings.loop :a {A.new 1 2} {A.new :b :b}} }} 
-> {def doublings
 {def doublings.loop
  {lambda {:a :d0 :d1}
   {if {> {A.last :d1} :a}
    then {A.new :d0 :d1}
    else {doublings.loop
           :a 
           {A.addlast! {+ {A.get 0 {A.last :d0}}
                          {A.get 0 {A.last :d0}} } :d0}
           {A.addlast! {+ {A.get 1 {A.last :d1}}
                          {A.get 1 {A.last :d1}} } :d1} } }}} 
 {lambda {:a :b}  
  {doublings.loop :a {A.new 1 2} {A.new :b :b}} }}

;; {doublings 580 34}

'{def divide
 {def divide.loop
  {lambda {:a :b :d0 :d1 :q :c :i}
   {if {> :i 0}
    then {divide.loop :a :b :d0 :d1
                       {if {<= {+ :c {A.get :i       :d1}} :a}  
                        then   {+ :q {A.get {- :i 1} :d0}}
                               {+ :c {A.get :i       :d1}}
                        else :q :c}
                      {- :i 1}}
    else :a = :b*:q+{abs {- :c :a}} }}}
 {lambda {:a :b}
  {let { {:a :a} {:b :b}
         {:d {doublings :a :b}}
       } {divide.loop :a :b {A.get 0 :d} {A.get 1 :d} 
                      0 0 {A.length {A.get 0 :d}} } }}} 
-> {def divide
 {def divide.loop
  {lambda {:a :b :d0 :d1 :q :c :i}
   {if {> :i 0}
    then {divide.loop :a :b :d0 :d1
                       {if {<= {+ :c {A.get :i       :d1}} :a}  
                        then   {+ :q {A.get {- :i 1} :d0}}
                               {+ :c {A.get :i       :d1}}
                        else :q :c}
                      {- :i 1}}
    else :a = :b*:q+{abs {- :c :a}} }}}
 {lambda {:a :b}
  {let { {:a :a} {:b :b}
         {:d {doublings :a :b}}
       } {divide.loop :a :b {A.get 0 :d} {A.get 1 :d} 0 0 {A.length {A.get 0 :d}} } }}}

} 
_h2 tests

{pre
{def ediv 
 {lambda {:a :b}
  :a = :b*{floor {/ :a :b}}+{% :a :b}}}

'{divide 580 34}  -> {divide 580 34}
'{divide 578 34}  -> {divide 580 34}
'{divide 10 5}    -> {divide 10 5}
'{divide 100 5}   -> {divide 100 5}
'{divide 1000 5}  -> {divide 1000 5}

'{divide 123456789 123}
-> {divide 123456789 123} 
  ({ediv 123456789 123}) by standard euclidean division

'{divide 7532795332300578 235117}
-> {divide 7532795332300578 235117}
  ({ediv 7532795332300578 235117})
}

_p {i alain marty | 2023/02/04}