[Edu-sig] Re: [Tutor] Need more precise digits

[Kirby Urner]

In tutor@python.org, "dman" <dsh8290@rit.edu> wrote:

>Checking equality with floats is bad because of the
>approximations that happen.

Oh so true.

    def lazyrange(start,stop,inc):
         if (start<stop and inc<0) or \
            (start>stop and inc>0):
            raise ValueError,"Illegal parameters"
         while start<stop:
            yield start
            start += inc
         return

Didn't have *that* problem at least.

By the way, another application of the generator feature
came up for me on another list recently.  I was chatting
with a community college prof about continued fractions,
which have the standard form:

            q0 +    1
                 --------
                  q1 +  1
                       ----
                        q2 + ....

Where q0, q1... are positive integers.  I had this recursive
way of doing it which amounted to a right to left evaluation,
but he showed me a way of going left to right.  That was cool,
because one thing I wanted to see was how some continued
fractions gradually converge to a key constant.  For example,
the simplest of all continued fractions is just:

            1  +    1
                 --------
                  1  +  1
                       ----
                        1 + ....

and so on.

The professor had written his algorithm for the TI calculator,
but I adapted with hardly any modifications to Python, and
now it looks like this:

     from __future__ import generators

     def conv(cf):
        """
        Generate partial fractions from partial quotients
        of a continued fraction, with thanks to:
        RWW Taylor
        National Technical Institute for the Deaf
        Rochester Institute of Technology
        Rochester NY 14623
        """
        cfsize = len(cf)
        n = [0 for i in range(cfsize+2)]  # all 0s
        d = n[:]                          # copy of n
        n[1] = d[0] = 1
        for i in range(cfsize):
          n[i+2] = n[i] + cf[i] * n[i + 1]
          d[i+2] = d[i] + cf[i] * d[i + 1]
          yield str(n[i])+"/"+str(d[i]) # interim result
        return

So if I feed this a list like [1,1,1,1,1,1,1,1,1,1,1,1,1],
it'll yield an approximation with each iteration, because
I wrote it as a generator.

For example:

  >>> genphi = conv([1,1,1,1,1,1,1,1,1,1,1,1,1])
  >>> for fraction in genphi: print fraction

  0/1
  1/0
  1/1
  2/1
  3/2
  5/3
  8/5
  13/8
  21/13
  34/21
  55/34
  89/55
  144/89

Of course a 'print' statement in place of yield would accomplish
the same thing in this context (that's what a yield is like,
a print).  But I can imagine an application where I'd want
to return the partial fraction, then maybe ask for more
precision later on, and conv() would be there, ready to pick
up right where it left off.

I've written class definitions like this for square roots --
you ask for 30 digits of precision, then come back later and
ask for 100 digits, and it doesn't have to start over from
the beginning, just goes out from 30, and so on.

BTW, as some might already know, the constant we're
approaching with this simplest of continued fractions is
phi = (sqrt(5)+1)/2 = golden ratio = approx.
1.6180339887498949

   >>> 144/89.
   1.6179775280898876

Not so close yet.  But let's go out to 50 iterations:

   >>> genphi = conv([1 for i in range(50)])
   >>> for fraction in genphi:  result = fraction

   >>> result
   '7778742049/4807526976'
   >>> 7778742049/4807526976.
   1.6180339887498949

Better.

This is where we could write a loop that continues until the
difference between the fraction and the floating point goes
below some very small value, like 1E-12.  Just modify conv()
to never stop on its own, and keep looping until you hit the
break condition, which should *not* involve an ==, for the
reason you mention.

Kirby