lambdaway :: rationals2

2 | list | login |load

| |

{center [[rationals]] | rationals2 | [[fractions]] | [[fractions2]] | [[habiter]] | [[φ & π|?view=rationals4]]}

_h1 generalized continued fractions

_p A number {b x} may be represented as a continued fraction as follows:

{pre {@ style="font-size:2.0em;"}
x = [a{sub 0} (a{sub 1},b{sub 1}) (a{sub 2},b{sub 1}) ...]        
  = a{sub 0} + b{sub 1}
         {{bt}a{sub 1} + b{sub 2}}
              {{bt}a{sub 2} + b{sub 3}}
                   {{bt}a{sub 3} + b{sub 4}}
                        {{bt}a{sub 4} + ...}  
}

_p The task is to write a program which generates such a number and prints it in its rational expression and its real representation.

_h2 1) algorithm

{pre 
a = [b{sub 0} (a{sub 1},b{sub 1}) (a{sub 2},b{sub 1}) ...] 
u(0) = a{sub 0}
u(n) = b{sub n} / (a{sub n} + u(n-1))
}

_h2  2) lambdatalk code

{pre
'{def GCF

{def GCF.rec
  {lambda {:f :n :r}
   {if {< :n 1}
    then {Q.+ {:f 0} :r}
    else {GCF.rec :f {- :n 1}
                  {let { {:ab {:f :n}} {:r :r}
                       } {Q./ {cons {cdr :ab} 1}
                              {Q.+ {cons {car :ab} 1} :r}}}}}}}

{lambda {:f :n}
  {let { {:r {GCF.rec :f :n {cons 0 1}}}
       } :r {br}-> {/ {car :r} {cdr :r}}}}} 
-> {def GCF
 {def GCF.rec
  {lambda {:f :n :r}
   {if {< :n 1}
    then {Q.+ {:f 0} :r}
    else {GCF.rec :f
                   {- :n 1}
                   {let { {:ab {:f :n}}
                          {:r :r}
                        } {Q./ {cons {cdr :ab} 1}
                          {Q.+ {cons {car :ab} 1} :r}}
 }}}}}
 {lambda {:f :n}
  {let { {:r {GCF.rec :f :n {cons 0 1}}}
       } :r <br>-> {/ {car :r} {cdr :r}}}}}

called this way

'{GCF {lambda {:n} {cons a(:n) b(:n)}} precision}
-> (n d)  // rational expression
-> n/d    // decimal expression
}

_p {b Q.+} & {b Q./} used to add and divide rational numbers belong to the {b Q_lib} library.

_h2 3) application

_h2 φ

_p For the golden number a{sub n} is always 1.

{pre
φ = [1 1 1 1 1 ...]
  = 1 + 1
        {{bt}1 + 1}
            {{bt}1 + 1}
                {{bt}1 + 1}
                    {{bt}1 + ...} 
}

{pre
'{GCF {lambda {:n} {cons 1 1}} 50}
-> {GCF {lambda {:n} {cons 1 1}} 50}  
   {/ {+ 1 {sqrt 5}} 2} = φ  
}

_h3 √2

_p For the square root of 2, use a{sub 0}=1 then a{sub n}=2. b{sub n} is always 1.

{pre
√2 = [1 2 2 2 2 ...]
   = 1 + 1
         {{bt}2 + 1}
             {{bt}2 + 1}
                 {{bt}2 + 1}
                     {{bt}2 + ...}
}

{pre
'{GCF {lambda {:n} {cons {if {> :n 0} then 2 else 1} 1}} 25}
-> {GCF {lambda {:n}
  {cons {if {> :n 0} then 2 else 1} 1}} 25} 
   {sqrt 2} = √2
}

_h2 e

_p For Napier's Constant, use a{sub 0}=2, then a{sub n}=n. b{sub 1}=1 then b{sub n}=n−1.

{pre
e = 2 + 1
        {{bt}1 + 1}
            {{bt}2 + 2}
                {{bt}3 + 3}
                    {{bt}4 + 4}
                        {{bt}5 + 5} 
                            {{bt}6 + ...}
}

{pre

'{GCF {lambda {:n}
  {cons {if {> :n 0} then :n else 2} 
         {if {> :n 1} then {- :n 1} else 1} }} 20}
-> {GCF {lambda {:n}
  {cons {if {> :n 0} then :n else 2} 
         {if {> :n 1} then {- :n 1} else 1} }} 20}   
   {E} = e
}

_h2 π

_p For π use a{sub 0}=3 then a{sub n}=6. b{sub n}=(2*n−1){sup 2}.

{pre
π = 3 + 1{sup 2}
        {{bt}6 + 1{sup 2}}
            {{bt}6 + 3{sup 2}}
                 {{bt}6 + 5{sup 2}}
                     {{bt}6 + ...}
}

{pre
'{GCF {lambda {:n}
  {cons {if {> :n 0} then 6 else 3}
        {pow {- {* 2 :n} 1} 2} }} 500}
-> {GCF {lambda {:n}
  {cons {if {> :n 0} then 6 else 3}
        {pow {- {* 2 :n} 1} 2} }} 500}
   {u 3.14159265}3589793 ≈ π, only 8 exact decimals for 500 iterations
}

_p A beautiful expression for π but a very very slow convergence. Here is a version without any obvious pattern

{pre
π = 3 + 1
        {{bt}7 + 1}
            {{bt}15 + 1}
                 {{bt}1 + 1}
                     {{bt}292 + 1}
                         {{bt}1 + 1}
                             {{bt}1 + ...}
}

{pre
'{def fpi {A.new 3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1}} 
-> {def fpi {A.new 3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1}}

'{S.map {lambda {:i}
               {br}:i: {GCF {lambda {:n}
                                    {cons {A.get :n {fpi}} 1}} :i}} 
       {S.serie 1 13}}

-> 
{S.map {lambda {:i} {br}{+ :i 1}: {GCF {lambda {:n} {cons {A.get :n {fpi}} 1}} :i}} {S.serie 0 13}}
   {PI} = π 
  
}

_p Much faster!. Note the two well known approximations {b 22/7} and {b 355/113} and that π has 15 exact decimals after 14 iterations.

_h2 lib_Q

_p Some arithmetic on rational numbers are done using the following set of user defined functions and the {b pgcd} primtive added to the dictionary.

{pre
{def Q.new
{lambda {:n :d} 
  {{lambda {:n :d :g} 
    {cons {/ :n :g} {/ :d :g}}} :n :d {pgcd :n :d}}}}    // used in this page
{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.d {lambda {:r} {cdr :r}}}
{def Q.2real
 {lambda {:r}
  {/ {car :r} {car :d}}}}
{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}}}}}     // used in this page
{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} {car :r2}}
         {* {cdr :r1} {cdr :r2}}}}}
{def Q./
 {lambda {:r1 :r2}
  {Q.new {* {car :r1} {cdr :r2}}
         {* {cdr :r1} {car :r2}}}}}     // used in this page
}

_p This page is computed in about 100ms on a MacBook Air and an iPad Pro.

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

_h2 references
 
_ul [[https://pi.math.cornell.edu/~gautam/ContinuedFractions.pdf|https://pi.math.cornell.edu/~gautam/ContinuedFractions.pdf]] 
_ul [[https://rosettacode.org/wiki/Continued_fraction|https://rosettacode.org/wiki/Continued_fraction]]
_ul  [[Lord Brouncker & Wallis|https://dainoequinoziale.github.io/resources/sassolini/picontinuedfraction.pdf]]
_ul [[http://villemin.gerard.free.fr/Wwwgvmm/Nombre/FCvaleur.htm|http://villemin.gerard.free.fr/Wwwgvmm/Nombre/FCvaleur.htm]]
_ul ...

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

{script 
// used by Q.new
LAMBDATALK.DICT['pgcd'] = function() {  // {pgcd 12 3}
  var pgcd = function(a,b) {
    return (b == 0) ? a : pgcd( b,a%b )
  };
  var args = LAMBDATALK.supertrim( arguments[0] ).split(' ');
    return pgcd( Number(args[0]), Number(args[1]) )
};
}

{style 
pre {box-shadow:0 0 8px #000; padding:5px; }
}