README

   1 = Continued Fraction Library =
   2 Ben Lynn, September 2008
   3
   4 Frac is a C library for computing with continued fractions.
   5
   6 == Continued Fractions ==
   7
   8 The binary representation of 1/3 is infinite. Floating-point numbers, our
   9 standard tool for working with reals, cannot even handle numbers a young child
  10 could understand.
  11
  12 In contrast, every rational can be uniquely and exactly represented by a finite
  13 continued fraction (provided we forbid those with last term 1). Continued
  14 fractions are immune from oddities such as 1/3 = 0.333... and 1 = 0.999...,
  15 living in a realm free from the tyranny of binary, or any other base.
  16
  17 Every irrational number can also be uniquely expressed as an infinite continued
  18 fraction. Many frequently encountered algebraic and transcendental numbers have
  19 easily computable continued fraction expansions which can be truncated to yield
  20 approximations with built-in error bounds, unlike floating-point
  21 approximations, which must be accompanied at all times with their error bounds.
  22
  23 Furthermore, suppose we use floating-point to compute some answer to 100
  24 decimal places. What if we now want 200 decimal places? Even if we possess the
  25 first 100 digits and carefully preserve the program state, we must start from
  26 scratch and redo all our arithmetic with 200 digit precision. If we had used
  27 continued fractions, we could arbitrarily increase the precision of our answer
  28 without redoing any work, and without any tedious error analysis.
  29
  30 But we must pay a price for these advantages. We have a representation from
  31 which we can instantly infer error bounds. A representation for which we may
  32 arbitrarily increase precision without repeating any calculations. A
  33 representation which in some sense is the closest we can hope to get to an
  34 exact number using rationals. Is it any wonder therefore that binary operations
  35 on continued fractions, whose output must also uphold these high standards, are
  36 clumsy and convoluted?
  37
  38 These drawbacks are almost certainly why these fascinating creatures remain
  39 obscure. Yet surely there are some problems that scream for continued
  40 fractions. How about a screen saver that computes more and more digits of pi,
  41 each time picking up where it left off?  Or imagine a real-time application
  42 where all continued fractions simply output the last computed convergent on a
  43 timer interrupt. Under heavy system load, approximations are coarser but the
  44 show goes on.
  45
  46 == Installation ==
  47
  48 The GMP library is required. Type:
  49
  50   $ make
  51
  52 to compile. Try "pi 2000" to generate 2000 digits of pi using a continued
  53 fraction. It takes longer than I had hoped, but it's faster than
  54
  55   $ echo "scale = 2000; 4*a(1)" | bc -l
  56
  57 There's no API documentation; see the source.
  58
  59 == Design ==
  60
  61 Threads are the future, if not already the present. Multicore systems are
  62 already commonplace, and as time passes, the number of cores per system will
  63 steadily march upward. Happily, this suits continued fractions.
  64
  65 Inspired by Doug McIlroy's "Squinting at Power Series" (search for it), we
  66 spawn at least one thread per continued fraction, and also per operation on
  67 continued fractions. The threads communicate via crude demand channels, each
  68 providing a few output terms upon each request.
  69
  70 This scheme allows us to quickly write code for generating continued fraction
  71 expansions or operating on them. For example, consider the code for generating
  72 'e' = 2.71828...
  73
  74 ..............................................................................
  75 // e = [2; 1, 2, 1, 1, 4, 1, ...]
  76 static void *e_expansion(cf_t cf) {
  77   int even = 2;
  78   cf_put_int(cf, even);
  79
  80   while(cf_wait(cf)) {
  81     cf_put_int(cf, 1);
  82     cf_put_int(cf, even);
  83     even += 2;
  84     cf_put_int(cf, 1);
  85   }
  86
  87   return NULL;
  88 }
  89 ..............................................................................
  90
  91 The function +cf_put+ places a term on the output channel, and +cf_wait+ is our
  92 implementation of demand channels, a sort of cooperative multitasking. Without
  93 it, not only would we have to destroy and clean up after the thread ourselves,
  94 but more seriously, the thread might consume vast amounts of resources
  95 computing unwanted terms. The +cf_wait+ functions instructs the thread to stay
  96 idle. Our threads call this function often, and if it returns zero, our threads
  97 clean themselves up and exit.
  98
  99 == Bugs and other issues ==
 100
 101 I intend to devote time to projects that operate on real numbers rather than
 102 study real numbers for its own sake. But perhaps then I'll find a perfect
 103 application for continued fractions, which will push me to fix deficiencies in
 104 this code:
 105
 106 - The API could use cosmetic surgery.
 107
 108 - I want to replace the condition variable with a semaphore to silence Helgrind
 109   (whose documentation states that condition variables almost unconditionally
 110   and invariably raise false alarms).
 111
 112 - The Makefile is fragile and annoying to maintain and use.
 113
 114 - The testing infrastructure needs upgrading.
 115
 116 - Much more, e.g. see TODOs sprinkled throughout the code.
 117
 118 === Disclaimer ===
 119
 120 Lest my salesmanship backfire, let me temper my anti-floating-point rhetoric.
 121 Increasing the precision of floating-point operations without redoing work is
 122 in fact possible for many common cases. For example, Newton's method is
 123 self-correcting, meaning we may use low precision at first, and increase it for
 124 future iterations. Even pi enjoys such methods: there exists a formula
 125 revealing any hexadecimal digit of pi without computing any previous digits,
 126 though it requires about the same amount of work.
 127
 128 Moreover, several floating-point algorithms converge quadratically or faster,
 129 thus good implementations will asymptotically outperform continued fractions
 130 as these converge only linearly.
 131
 132 Nonetheless, for lower accuracies, the smaller overhead may give continued
 133 fractions the edge in certain problems such as finding the square root of 2.
 134 Additionally, precision decisions are automatic, for example, one simply needs
 135 enough bits to hold the last computed convergents. Built-in error analysis
 136 simplifies and hence accelerates development.