Arithmetic with Continued Fractions

Length: 60 minutes


Multiprecision arithmetic algorithms usually represent real numbers as decimals, or perhaps as their base-2n analogues. But this representation has some puzzling properties. For example, there is no exact representation of even as simple a number as one-third. Continued fractions are a practical but little-known alternative.

Continued fractions are a representation of the real numbers that are in many ways more mathematically natural than the usual decimal or binary representations. All rational numbers have simple representations, and so do many irrational numbers, such as sqrt(2) and e1. One reason that continued fractions are not often used, however, is that it's not clear how to involve them in basic operations like addition and multiplication. This was an unsolved problem until 1972, when Bill Gosper found practical algorithms for continued fraction arithmetic.

In this talk, I explain what continued fractions are and why they are interesting, how to represent them in computer programs, and how to calculate with them.

Complete Slides

  1. Arithmetic with Continued Fractions
  2. What we'll do
  3. How do we represent real numbers for calculation?
  4. Decimal representation
  5. Decimal arithmetic
  6. Continued Fractions
  7. Truncation
  8. Irrational numbers
  9. Continued fractions
  10. Change of stance
  11. Why not continued fractions?
  12. The catch
  13. Continued fraction objects
  14. Input
  15. Output
  16. When to output?
  17. An example
  18. Let's ask for a term from _z_
  19. Aha!
  20. [I[ex1+2-11-7]I]
  21. Details
  22. This time with feeling
  23. Continued fraction arithmetic
  24. When to output?
  25. Arithmetic
  26. Implementation
  27. Thank you
  28. Bonus slides and deleted material
  29. Important properties of continued fractions
  30. Comparing continued fractions is easy
  31. Truncation

Complete slides and illustrations for the talk.

Additional Materials

A small implementation of the Gosper algorithm in C.

Gosper's HAKMEM notes, his longer monograph, and some other papers and materials.

Return to: Universe of Discourse main page | Perl Paraphernalia | Other Classes and Talks