Re: [math-fun] decimal expansions of P/Q in radix R and their uses

30 Jan 2012

      The continued-fraction approximations method ("Euclid's" [1]) seems
appealing [2], but it is no guarantee.

Suppose I use continued fractions to find A/B=0.001004009016025036... How
do I know that the fraction continues as I want it to? I could look at 100
digits, but what if it fails just beyond the last digit I checked?

- Robert

[1] See http://en.wikipedia.org/wiki/Euclidean_algorithm#Continued_fractions

[2] An example, in the Unix tool bc. The answer is probably the one just
before the big jump in size:

cfrac(0.010409162536496481)
1 / 0
0 / 1
1 / 96
14 / 1345
29 / 2786
130 / 12489
289 / 27764
708 / 68017
997 / 95781
2702 / 259579
3699 / 355360
6401 / 614939
10100 / 970299
10598007101 / 1018142147732
74186059807 / 7126996004423

The source code for "cfrac" is:

define cfraccore(x,m) {
  auto xi,n,d,n1,d1,n2,d2,s;

  if (x<0) {
    x = -x
  }
  if (x==0) {
    return(0)
  }
  s=10^scale

  n=1
  d=0
  n1=0
  d1=1
  i=0
  while((n+d)*(n+d)<s) {
    if (m==0) {
      print n, " / ", d, "\n"
    }
    xi=floor(x)
    x=x-xi
    x=1/x
    n2=n1
    n1=n
    d2=d1
    d1=d
    n=n1*xi+n2
    d=d1*xi+d2
    if ((m==1) && (n+d<s)) {
      if (i>1) {
        print ", ";
      } else if (i>0) {
        print "; ";
      }
      print xi;
    }
    i=i+1
  }
  if (m==1) {
    print "\n"
  }
  return(1)
}

print "  cfrac(x) prints successive continued-fraction approximations to x"
print "\n"
define cfrac(x) {
  auto ignore
  ignore=cfraccore(x,0)
}

print "  cfseq(x) prints terms of simple continued fraction for x"
print "\n"
define cfseq(x) {
  auto ignore
  ignore=cfraccore(x,1)
}

On Sun, Jan 29, 2012 at 09:19, Warren Smith <warren.wds@gmail.com> wrote:
...
[...]
The idea that we can identify numbers like 1.004009016025036... by use
...
of "generating functions" is silly in comparison with the much better and
simpler idea that you can find the optimum rational approximations to ANY
decimal X by use of (Euclid's) continued fraction expansion of X:
1.004009016025036049064081100 = [1, 249, 2, 3, 1, 1, 14, 7, 4, 2, 4,
...
7, 7, 1, large]
then
 1 +
1/(249+1/(2+1/(3+1/(1+1/(1+1/(14+1/(7+1/(4+1/(2+1/(4+1/(7+1/(7+1))))))))))));
=
1001000000 / 997002999
=
1.004009016025036049064081100121144169196225256289324361...
[...]
-- 
  Robert Munafo  --  mrob.com
  Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 -
mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com