lambdaway :: rationals

6 | list | login |load

| |

{center rationals | [[rationals2]] | [[fractions]] | [[fractions2]] | [[habiter]]}

;;_img http://villemin.gerard.free.fr/Wwwgvmm/Nombre/Rac2Val_fichiers/image052.jpg

_h1 rationals

_p A rational number is a couple of integers, numerator and denominator, {b n/d}. When {b n} and {b d} have a common divisor, they are reduced to the simplest form, for instance {b 2/3} remains {b 2/3} but {code 3/6} becomes {b 1/2}. When the denominator is {b 1}, the rational number is displayed as a simple integer, for instance {b 6/3} is b as {b 2}. When the product {b n*d} is negative it is displayed as {b -abs(n)/abs(n)}

_h2 1) algebra

_p This is some algebra on rationals:

{pre
n1/d1 + n2/d2 = (n1*d2 + n2*d1)/(d1*d2)
n1/d1 - n2/d2 = (n1*d2 - n2*d1)/(d1*d2)
n1/d1 * n2/d2 = (n1*n2)/(d1*d2)
n1/d1 / n2/d2 = (n1*d2)/(d1*n2)
n1/d1 = n2/d2 is true if n1*d2 = n2*d1 else false
}

_h2 2) main operators
_p We build the first operators using the 3 primitives {b cons, car, cdr}.

{pre
'{def Q.new
 {def Q.pgcd        // faster if defined as a primitive
  {lambda {:a :b} 
   {if {= :b 0}
    then :a
    else {Q.pgcd :b {% :a :b}}}}}
 {lambda {:n :d} 
  {{lambda {:n :d :g} 
    {cons {/ :n :g} {/ :d :g}}} :n :d {Q.pgcd :n :d}}}}
-> {def Q.new
 {def Q.pgcd
  {lambda {:a :b} 
   {if {= :b 0}
    then :a
    else {Q.pgcd :b {% :a :b}}}}}
 {lambda {:n :d} 
  {{lambda {:n :d :g} 
    {cons {/ :n :g} {/ :d :g}}} :n :d {Q.pgcd :n :d}}}}

'{def Q.disp
 {lambda {:r} 
  {if {< {* {car :r} {cdr :r}} 0}
   then - 
   else}{if {= {abs {cdr :r}} 1}
         then {abs {car :r}}
         else {abs {car :r}}/{abs {cdr :r}}}}}
-> {def Q.disp
 {lambda {:r} 
  {if {< {* {car :r} {cdr :r}} 0}
   then - 
   else}{if {= {abs {cdr :r}} 1}
         then {abs {car :r}}
         else {abs {car :r}}/{abs {cdr :r}}}}}

'{def Q.n {lambda {:r} {car :r}}}
-> {def Q.n {lambda {:r} {car :r}}}

'{def Q.d {lambda {:r} {cdr :r}}}
-> {def Q.d {lambda {:r} {cdr :r}}}

'{def Q.2real
 {lambda {:r}
  {/ {car :r} {car :d}}}}
-> {def Q.2real
 {lambda {:r}
  {/ {car :r} {cdr :r}}}}

'{def Q.=
 {lambda {:r1 :r2}
  {= {* {car :r1} {cdr :r2}}
     {* {car :r2} {cdr :r1}}}}}
-> {def Q.=
 {lambda {:r1 :r2}
  {= {* {car :r1} {cdr :r2}}
     {* {car :r2} {cdr :r1}}}}}

'{def Q.+
 {lambda {:r1 :r2}
  {Q.new {+ {* {car :r1} {cdr :r2}} 
            {* {car :r2} {cdr :r1}}}
         {* {cdr :r1} {cdr :r2}}}}}
-> {def Q.+
 {lambda {:r1 :r2}
  {Q.new {+ {* {car :r1} {cdr :r2}} 
            {* {car :r2} {cdr :r1}}}
         {* {cdr :r1} {cdr :r2}}}}}

'{def Q.-
 {lambda {:r1 :r2}
  {R.new {- {* {car :r1} {cdr :r2}} 
            {* {car :r2} {cdr :r1}}}
         {* {cdr :r1} {cdr :r2}}}}}
-> {def Q.-
 {lambda {:r1 :r2}
  {Q.new {- {* {car :r1} {cdr :r2}} 
            {* {car :r2} {cdr :r1}}}
         {* {cdr :r1} {cdr :r2}}}}}

'{def Q.*
 {lambda {:r1 :r2}
  {Q.new {* {car :r1} {car :r2}}
         {* {cdr :r1} {cdr :r2}}}}}
-> {def Q.*
 {lambda {:r1 :r2}
  {Q.new {* {car :r1} {car :r2}}
         {* {cdr :r1} {cdr :r2}}}}}

'{def Q./
 {lambda {:r1 :r2}
  {Q.new {* {car :r1} {cdr :r2}}
         {* {cdr :r1} {car :r2}}}}}
-> {def Q./
 {lambda {:r1 :r2}
  {Q.new {* {car :r1} {cdr :r2}}
         {* {cdr :r1} {car :r2}}}}}
}

_h2 3) testing

{pre
'{Q.disp {Q.new 3 4}}   -> {Q.disp {Q.new 3 4}}
'{Q.disp {Q.new 6 3}}   -> {Q.disp {Q.new 6 3}}
'{Q.disp {Q.new 6 -3}}  -> {Q.disp {Q.new 6 -3}}

'{Q.disp {Q.new 3 2}}   -> {Q.disp {Q.new 3 2}}
'{Q.disp {Q.new 3 -2}}  -> {Q.disp {Q.new 3 -2}}
'{Q.disp {Q.new -3 2}}  -> {Q.disp {Q.new -3 2}}
'{Q.disp {Q.new -3 -2}} -> {Q.disp {Q.new -3 -2}}

'{Q.2real {Q.new 3 2}}  -> {Q.2real {Q.new 3 2}} 
'{Q.2real {Q.new 4 2}}  -> {Q.2real {Q.new 4 2}} 
'{Q.2real {Q.new 1 0}}  -> {Q.2real {Q.new 1 0}}

'{Q.= {Q.new 3 1} {Q.new 6 2}} -> {Q.= {Q.new 3 1} {Q.new 6 2}}
'{Q.= {Q.new 3 2} {Q.new 6 2}} -> {Q.= {Q.new 3 2} {Q.new 6 2}}

'{Q.disp {Q.+ {Q.new 3 4} {Q.new 6 3}}} -> {Q.disp {Q.+ {Q.new 3 4} {Q.new 6 3}}}     
'{Q.disp {Q.- {Q.new 3 4} {Q.new 6 3}}} -> {Q.disp {Q.- {Q.new 3 4} {Q.new 6 3}}}   
'{Q.disp {Q.* {Q.new 3 4} {Q.new 6 3}}} -> {Q.disp {Q.* {Q.new 3 4} {Q.new 6 3}}}  
'{Q.disp {Q./ {Q.new 3 4} {Q.new 6 3}}} -> {Q.disp {Q./ {Q.new 3 4} {Q.new 6 3}}}  
}

_h2 4) application to continued [[fractions]]

_img https://wikimedia.org/api/rest_v1/media/math/render/svg/247535cef4b9b94eabeb16908cf72436cd01d0c9 
 
_h3 definition

{pre

F = [a{sub 0};a{sub 1},a{sub 2},...,a{sub n}]
  = a{sub 0} + 1
         {{bt}a{sub 1} + 1}
              {{bt}a{sub 2} + 1}
                   {{bt} ... 1}
                       {{bt}a{sub n}} 
}

_h3 computing the convergents

_p Given {b [a{sub 0};a{sub 1},a{sub 2},...,a{sub n}]} we compute the rational value and its real equivalent.

{pre
'{def convergent

{def convergent.rec
  {lambda {:a :i :r}
   {if {= :i 0}
    then {Q.+ {Q.new {A.get 0 :a} 1} :r}           // a[0]+rm
    else {convergent.rec :a
                         {- :i 1}                       
                         {Q./ {Q.new 1 1}          // 1/
                              {Q.+ {Q.new {A.get :i :a} 1}
                                   :r}}}}}}        // a[i]+r
 {lambda {:s}
  {let { {:c {convergent.rec {A.new :s}            // a <- s
                             {- {S.length :s} 1}   // i = n-1
                             {Q.new 1 1}}}         // r = 1
       } :c = {/ {car :c} {cdr :c}}}}}             // -> c & n/d
-> {def convergent
 {def convergent.rec
  {lambda {:a :i :r}
   {if {= :i 0}
    then {Q.+ {Q.new {A.get 0 :a} 1} :r}
    else {convergent.rec :a
                         {- :i 1}                     
                         {Q./ {Q.new 1 1}
                              {Q.+ {Q.new {A.get :i :a} 1} :r}}}}}}
 {lambda {:s}
  {let { {:c {convergent.rec {A.new :s}
                             {- {S.length :s} 1} 
                             {Q.new 1 1}}}
       } :c = {/ {car :c} {cdr :c}}}}}
}

_h2 computing φ, √2, e, π

{pre
'{convergent 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1}   
-> {convergent 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1}
                           {/ {+ 1 {sqrt 5}} 2}       = φ

'{convergent 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2} 
-> {convergent 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2}
                           {sqrt 2}     = √2

'{convergent 2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 14 1}
-> {convergent 2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1 14 1}
                           {E}      = e

'{convergent 3 7 15 1 292 1 1 1 2 1 3 1 14 2 1}
-> {convergent 3 7 15 1 292 1 1 1 2 1 3 1 14 2 1}
                           {PI}      = π
}

_p Note the decrasing number of terms from {b φ} to {b π} to reach the digits given by javascript, the convergence of {b 1}s in {b φ} is slow and the presence of big terms in {b π} makes it quicker. Note also that the sequence of terms in π does not show any obvious pattern.

_p {i alain marty | 2022/04/17}

_h2 references
_ul [[SICP|https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.1]]
_ul [[http://villemin.gerard.free.fr/aJeux1/Arithmet/Maison.htm%5D%5D|http://villemin.gerard.free.fr/aJeux1/Arithmet/Maison.htm%5D%5D]]

{{hide}
{def bt span {@ style="border-top:1px solid;"}}
}