/usr/share/doc/axiom-doc/hypertex/numcontinuedfractions.xhtml

<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" 
      xmlns:xlink="http://www.w3.org/1999/xlink"
      xmlns:m="http://www.w3.org/1998/Math/MathML">
 <head>
  <meta http-equiv="Content-Type" content="text/html" charset="us-ascii"/>
  <title>Axiom Documentation</title>
  <style>

   html {
     background-color: #ECEA81;
   }

   body { 
     margin: 0px;
     padding: 0px;
   }

   div.command { 
     color:red;
   }

   div.center {
     color:blue;
   }

   div.reset {
     visibility:hidden;
   }

   div.mathml { 
     color:blue;
   }

   input.subbut {
     background-color:#ECEA81;
     border: 0;
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   input.noresult {
     background-color:#ECEA81;
     border: 0;
     color:black;
     font-family: "Courier New", Courier, monospace;
   }

   span.cmd { 
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   pre {
     font-family: "Courier New", Courier, monospace;
   }
  </style>
  <script type="text/javascript">
<![CDATA[
     // This is a hash table of the values we've evaluated.
     // This is indexed by a string argument. 
     // A value of 0 means we need to evaluate the expression
     // A value of 1 means we have evaluated the expression
   Evaled = new Array();
     // this says we should modify the page
   hiding = 'show';
     // and this is the id of the div tag to modify (defaulted)
   thediv = 'mathAns';
     // commandline will mark that its arg has been evaled so we don't repeat
   function commandline(arg) {
     Evaled[arg] = 0;  // remember that we have set this value
     thediv='ans'+arg; // mark where we should put the output
     var ans = document.getElementById(arg).value;
     return(ans);
   }
   // the function only modifies the page if when we're showing the
   // final result, otherwise it does nothing.
   function showanswer(mathString,indiv) {
     if (hiding == 'show') { // only do something useful if we're showing
       indiv = thediv;  // override the argument so we can change it
       var mystr = mathString.split("</div>");
       for (var i=0; i < mystr.length; i++) {
         if (mystr[i].indexOf("mathml") > 0) {
           var mymathstr = mystr[i].concat("</div>");
         }
       }
       // this turns the string into a dom fragment
       var mathRange = document.createRange();
       var mathBox=
               document.createElementNS('http://www.w3.org/1999/xhtml','div');
       mathRange.selectNodeContents(mathBox);
       var mymath = mathRange.createContextualFragment(mymathstr);
       mathBox.appendChild(mymath);
       // now we need to format it properly
       // and we stick the result into the requested div block as a child.
       var mathAns = document.getElementById(indiv);
       mathAns.removeChild(mathAns.firstChild);
       mathAns.appendChild(mathBox);
     }
   }
   // this function takes a list of expressions ids to evaluate
   // the list contains a list of "free" expression ids that need to
   // be evaluated before the last expression. 
   // For each expression id, if it has not yet been evaluated we
   // evaluate it "hidden" otherwise we can skip the expression.
   // Once we have evaluated all of the free expressions we can
   // evaluate the final expression and modify the page.
   function handleFree(arg) {
     var placename = arg.pop();      // last array val is real
     var mycnt = arg.length;         // remaining free vars
       // we handle all of the prerequired expressions quietly
     hiding = 'hide';
     for (var i=0; i<mycnt; i++) {   // for each of the free variables
       if (Evaled[arg[i]] == null) { // if we haven't evaled it
         Evaled[arg[i]] = 0;         // remember we evaled it
         makeRequest(arg[i]);        // initialize the free values
       }
     }
       // and now we start talking to the page again
     hiding = 'show';                // we want to show this
     thediv = 'ans'+placename;       // at this div id
     makeRequest(placename);         // and we eval and show it
   }
]]>
<![CDATA[
  function ignoreResponse() {}
  function resetvars() {
    http_request = new XMLHttpRequest();         
    http_request.open('POST', '127.0.0.1:8085', true);
    http_request.onreadystatechange = ignoreResponse;
    http_request.setRequestHeader('Content-Type', 'text/plain');
    http_request.send("command=)clear all");
    return(false);
  }
]]>
 function init() {
 }
 function makeRequest(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("command="+command);
   return(false);
 }
 function lispcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("lispcall="+command);
   return(false);
 }
 function showcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("showcall="+command);
   return(false);
 }
 function interpcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("interpcall="+command);
   return(false);
 }
 function handleResponse() {
  if (http_request.readyState == 4) {
   if (http_request.status == 200) {
    showanswer(http_request.responseText,'mathAns');
   } else
   {
     alert('There was a problem with the request.'+ http_request.statusText);
   }
  }
 }

  </script>
 </head>
 <body onload="resetvars();">
  <div align="center"><img align="middle" src="doctitle.png"/></div>
  <hr/>
  <div align="center">Continued Fractions</div>
  <hr/>
Continued fractions have been a fascinating and useful tool in mathematics
for well over three hundred years. Axiom implements continued fractions
for fractions of any Euclidean domain. In practice, this usually means
rational numbers. In this section we demonstrate some of the operations
available for manipulating both finite and infinite continued fractions.
It may be helpful if you review
<a href="db.xhtml?Stream">Stream</a> to remind yourself of some of the 
operations with streams.

The <a href="db.xhtml?ContinuedFraction">ContinuedFraction</a> domain is a
field and therefore you can add, subtract, multiply, and divide the
fractions. The 
<a href="dbopcontinuedfraction.xhtml">continuedFraction</a> operation 
converts its fractional argument to a continued fraction.
<ul>
 <li>
  <input type="submit" id="p1" class="subbut" onclick="makeRequest('p1');"
    value="c:=continuedFraction(314159/100000)" />
  <div id="ansp1"><div></div></div>
 </li>
</ul>
This display is the compact form of the bulkier
<pre>
  3 +             1
     ---------------------------
     7 +            1
         -----------------------
         15 +         1
              ------------------
              1 +        1
                  --------------
                  25 +     1
                       ---------
                       1 +   1
                           -----
                           7 + 1
                               -
                               4
</pre>
You can write any rational number in a similar form. The fraction will
be finite and you can always take the "numerators" to be 1. That is, any
rational number can be written as a simple, finite continued fraction of
the form
<pre>
a(1) +            1
     ---------------------------
  a(2) +            1
         -----------------------
       a(3) +         1
                        .
                         .
                          .
                           1

              -----------------
              a(n-1) +     1
                       ---------
                          a(n)
</pre>
The a(i) are called partial quotients and the operation
<a href="dboppartialquotients.xhtml">partialQuotients</a> creates a
stream of them.
<ul>
 <li>
  <input type="submit" id="p2" class="subbut" 
    onclick="handleFree(['p1','p2']);"
    value="partialQuotients c" />
  <div id="ansp2"><div></div></div>
 </li>
</ul>
By considering more and more of the fraction, you get the
<a href="dbopconvergents.xhtml">convergents</a>. For example, the
first convergent is a(1), the second is a(1)+1/a(2) and so on.
<ul>
 <li>
  <input type="submit" id="p3" class="subbut" 
    onclick="handleFree(['p1','p3']);"
    value="convergents c" />
  <div id="ansp3"><div></div></div>
 </li>
</ul>
Since this ia a finite continued fraction, the last convergent is the
original rational number, in reduced form. The result of
<a href="dbopapproximants.xhtml">approximants</a> is always an infinite
stream, though it may just repeat the "last" value.
<ul>
 <li>
  <input type="submit" id="p4" class="subbut" 
    onclick="handleFree(['p1','p4']);"
    value="approximants c" />
  <div id="ansp4"><div></div></div>
 </li>
</ul>
Inverting c only changes the partial quotients of its fraction by 
inserting a 0 at the beginning of the list.
<ul>
 <li>
  <input type="submit" id="p5" class="subbut" 
    onclick="handleFree(['p1','p5']);"
    value="pq:=partialQuotients(1/c)" />
  <div id="ansp5"><div></div></div>
 </li>
</ul>
Do this to recover the original continued fraction from this list of
partial quotients. The three argument form of the 
<a href="dbopcontinuedfraction.xhtml">continuedFraction</a> operation takes
an element which is the whole part of the fraction, a stream of elements
which are the denominators of the fraction.
<ul>
 <li>
  <input type="submit" id="p6" class="subbut"
    onclick="handleFree(['p1','p5','p6']);"
    value="continuedFraction(first pq,repeating [1],rest pq)" />
  <div id="ansp6"><div></div></div>
 </li>
</ul>
The streams need not be finite for 
<a href="dbopcontinuedfraction.xhtml">continuedFraction</a>. Can you guess
which irrational number has the following continued fraction? See the end
of this section for the answer.
<ul>
 <li>
  <input type="submit" id="p7" class="subbut" onclick="makeRequest('p7');"
    value="z:=continuedFraction(3,repeating [1],repeating [3,6])" />
  <div id="ansp7"><div></div></div>
 </li>
</ul>
In 1737 Euler discovered the infinite continued fraction expansion
<pre>
 e - 1                 1
 ----- =  ---------------------------
p          2 +            1
              -----------------------
              6  +         1
                   ------------------
                  10 +        1
                       --------------
                       14 +  ... 
</pre>
We use this expansion to compute rational and floating point 
approximations of e. (For this and other interesting expansions,
see C. D. Olds, Continued Fractions, New Mathematical Library,
Random House, New York, 1963 pp.134-139).

By looking at the above expansion, we see that the whole part is 0
and the numerators are all equal to 1. This constructs the stream of
denominators.
<ul>
 <li>
  <input type="submit" id="p8" class="subbut" onclick="makeRequest('p8');"
    value="dens:Stream Integer:=cons(1,generate((x+->x+4),6))" />
  <div id="ansp8"><div></div></div>
 </li>
</ul>
Therefore this is the continued fraction expansion for (e-1)/2.
<ul>
 <li>
  <input type="submit" id="p9" class="subbut" 
    onclick="handleFree(['p8','p9']);"
    value="cf:=continuedFraction(0,repeating [1],dens)" />
  <div id="ansp9"><div></div></div>
 </li>
</ul>
These are the rational number convergents.
<ul>
 <li>
  <input type="submit" id="p10" class="subbut"
    onclick="handleFree(['p8','p9','p10']);"
    value="ccf:=convergents cf" />
  <div id="ansp10"><div></div></div>
 </li>
</ul>
You can get rational convergents for e by multiplying by 2 and adding 1.
<ul>
 <li>
  <input type="submit" id="p11" class="subbut" 
    onclick="handleFree(['p8','p9','p10','p11']);"
    value="eConvergents:=[2*e+1 for e in ccf]" />
  <div id="ansp11"><div></div></div>
 </li>
</ul>
You can also compute the floating point approximations to these convergents.
<ul>
 <li>
  <input type="submit" id="p12" class="subbut"
    onclick="handleFree(['p8','p9','p10','p11','p12']);"
    value="eConvergents::Stream Float" />
  <div id="ansp12"><div></div></div>
 </li>
</ul>
Compare this to the value of e computed by the 
<a href="dbopexp.xhtml">exp</a> operation in 
<a href="db.xhtml?Float">Float</a>.
<ul>
 <li>
  <input type="submit" id="p13" class="subbut" onclick="makeRequest('p13');"
    value="exp 1.0" />
  <div id="ansp13"><div></div></div>
 </li>
</ul>
In about 1658, Lord Brouncker established the following expansion for 4/pi.
<pre>
  1 +             1
     ---------------------------
     2 +            9
         -----------------------
         2  +         25
              ------------------
              2 +        49
                  --------------
                  2  +     81
                       ---------
                       2 +   ...
</pre>
Let's use this expansion to compute rational and floating point 
approximations for pi.
<ul>
 <li>
  <input type="submit" id="p14" class="subbut" onclick="makeRequest('p14');"
    value="cf:=continuedFraction(1,[(2*i+1)^2 for i in 0..],repeating [2])" />
  <div id="ansp14"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p15" class="subbut" 
    onclick="handleFree(['p14','p15']);"
    value="ccf:=convergents cf" />
  <div id="ansp15"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p16" class="subbut" 
    onclick="handleFree(['p14','p15','p16']);"
    value="piConvergents:=[4/p for p in ccf]" />
  <div id="ansp16"><div></div></div>
 </li>
</ul>
As you can see, the values are converging to 
<pre>
  pi = 3.14159265358979323846..., but not very quickly.
</pre>
<ul>
 <li>
  <input type="submit" id="p17" class="subbut" 
    onclick="handleFree(['p14','p15','p16','p17']);"
    value="piConvergents::Stream Float" />
  <div id="ansp17"><div></div></div>
 </li>
</ul>
You need not restrict yourself to continued fractions of integers. Here is
an expansion for a quotient of Gaussian integers.
<ul>
 <li>
  <input type="submit" id="p18" class="subbut" onclick="makeRequest('p18');"
    value="continuedFraction((-122+597*%i)/(4-4*%i))" />
  <div id="ansp18"><div></div></div>
 </li>
</ul>
This is an expansion for a quotient of polynomials in one variable with
rational number coefficients.
<ul>
 <li>
  <input type="submit" id="p19" class="subbut" onclick="makeRequest('p19');"
    value="r:Fraction UnivariatePolynomial(x,Fraction Integer)" />
  <div id="ansp19"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p20" class="subbut" 
    onclick="handleFree(['p19','p20']);"
    value="r:=((x-1)*(x-2))/((x-3)*(x-4))" />
  <div id="ansp20"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p21" class="subbut" 
    onclick="handleFree(['p19','p20','p21']);"
    value="continuedFraction r" />
  <div id="ansp21"><div></div></div>
 </li>
</ul>
To conclude this section, we give you evidence that
<pre>
  z =  3 +             1
          ---------------------------
          3 +            1
              -----------------------
              6 +          1
                  -------------------
                   3 +        1
                       --------------
                       6  +     1
                            ---------
                            3 + ...
</pre>
is the expansion of the square root of 11.
<ul>
 <li>
  <input type="submit" id="p22" class="subbut" 
    onclick="handleFree(['p7','p22']);"
    value="[i*i for i in convergents(z)]::Stream Float" />
  <div id="ansp22"><div></div></div>
 </li>
</ul>
 </body>
</html>
axiom-hypertex-data 20120501-8 / usr / share / doc / axiom-doc / hypertex / numcontinuedfractions.xhtml
