Moved README to website.
authorBen Lynn <benlynn@gmail.com>
Fri, 19 Sep 2008 07:53:28 +0000 (19 00:53 -0700)
committerBen Lynn <benlynn@gmail.com>
Fri, 19 Sep 2008 07:53:28 +0000 (19 00:53 -0700)
Add snapshot target to Makefile.

Makefile
README

index d363ac5..a181fb1 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,4 @@
-.PHONY: test target clean
+.PHONY: test target clean snapshot
 
 CF_OBJS:=cf.o mobius.o famous.o bihom.o taylor.o test.o newton.o tee.o
 TESTS:=bihom_test cf_test famous_test mobius_test newton_test tee_test
@@ -19,5 +19,9 @@ libfrac.a : $(CF_OBJS)
 
 test: $(TESTS)
 
+snapshot:
+       git-diff  # Ideally should do nothing.
+       git-archive --format=tar --prefix=frac-snapshot/ HEAD | gzip > frac-snapshot.tar.gz
+
 clean:
        -rm *.o $(TESTS) $(BINS) libfrac.a
diff --git a/README b/README
dissimilarity index 85%
index 4e0aa36..562a0e2 100644 (file)
--- a/README
+++ b/README
-= Continued Fraction Library =
-Ben Lynn, September 2008
-
-Frac is a C library for computing with continued fractions.
-
-== Continued Fractions ==
-
-The binary representation of 1/3 is infinite. Floating-point numbers, our
-standard tool for working with reals, cannot even handle numbers a young child
-could understand.
-
-In contrast, every rational can be uniquely and exactly represented by a finite
-continued fraction (provided we forbid those with last term 1). Continued
-fractions are immune from oddities such as 1/3 = 0.333... and 1 = 0.999...,
-living in a realm free from the tyranny of binary, or any other base.
-
-Every irrational number can also be uniquely expressed as an infinite continued
-fraction. Many frequently encountered algebraic and transcendental numbers have
-easily computable continued fraction expansions which can be truncated to yield
-approximations with built-in error bounds, unlike floating-point
-approximations, which must be accompanied at all times with their error bounds.
-
-Furthermore, suppose we use floating-point to compute some answer to 100
-decimal places. What if we now want 200 decimal places? Even if we possess the
-first 100 digits and carefully preserve the program state, we must start from
-scratch and redo all our arithmetic with 200 digit precision. If we had used
-continued fractions, we could arbitrarily increase the precision of our answer
-without redoing any work, and without any tedious error analysis.
-
-But we must pay a price for these advantages. We have a representation from
-which we can instantly infer error bounds. A representation for which we may
-arbitrarily increase precision without repeating any calculations. A
-representation which in some sense is the closest we can hope to get to an
-exact number using rationals. Is it any wonder therefore that binary operations
-on continued fractions, whose output must also uphold these high standards, are
-clumsy and convoluted?
-
-These drawbacks are almost certainly why these fascinating creatures remain
-obscure. Yet surely there are some problems that scream for continued
-fractions. How about a screen saver that computes more and more digits of pi,
-each time picking up where it left off?  Or imagine a real-time application
-where all continued fractions simply output the last computed convergent on a
-timer interrupt. Under heavy system load, approximations are coarser but the
-show goes on.
-
-== Installation ==
-
-The GMP library is required. Type:
-  $ make
-
-to compile. Try "pi 2000" to generate 2000 digits of pi using a continued
-fraction. It takes longer than I had hoped, but it's faster than
-
-  $ echo "scale = 2000; 4*a(1)" | bc -l
-
-There's no API documentation; see the source.
-
-== Design ==
-
-Threads are the future, if not already the present. Multicore systems are
-already commonplace, and as time passes, the number of cores per system will
-steadily march upward. Happily, this suits continued fractions.
-
-Inspired by Doug McIlroy's "Squinting at Power Series" (search for it), we
-spawn at least one thread per continued fraction, and also per operation on
-continued fractions. The threads communicate via crude demand channels, each
-providing a few output terms upon each request.
-
-This scheme allows us to quickly write code for generating continued fraction
-expansions or operating on them. For example, consider the code for generating
-'e' = 2.71828...
-
-..............................................................................
-// e = [2; 1, 2, 1, 1, 4, 1, ...]
-static void *e_expansion(cf_t cf) {
-  int even = 2;
-  cf_put_int(cf, even);
-
-  while(cf_wait(cf)) {
-    cf_put_int(cf, 1);
-    cf_put_int(cf, even);
-    even += 2;
-    cf_put_int(cf, 1);
-  }
-
-  return NULL;
-}
-..............................................................................
-
-The function +cf_put+ places a term on the output channel, and +cf_wait+ is our
-implementation of demand channels, a sort of cooperative multitasking. Without
-it, not only would we have to destroy and clean up after the thread ourselves,
-but more seriously, the thread might consume vast amounts of resources
-computing unwanted terms. The +cf_wait+ functions instructs the thread to stay
-idle. Our threads call this function often, and if it returns zero, our threads
-clean themselves up and exit.
-
-== Bugs and other issues ==
-
-I intend to devote time to projects that operate on real numbers rather than
-study real numbers for its own sake. But perhaps then I'll find a perfect
-application for continued fractions, which will push me to fix deficiencies in
-this code:
-
-- The API could use cosmetic surgery.
-
-- I want to replace the condition variable with a semaphore to silence Helgrind
-  (whose documentation states that condition variables almost unconditionally
-  and invariably raise false alarms).
-
-- The Makefile is fragile and annoying to maintain and use.
-
-- The testing infrastructure needs upgrading.
-
-- Much more, e.g. see TODOs sprinkled throughout the code.
-
-=== Disclaimer ===
-
-Lest my salesmanship backfire, let me temper my anti-floating-point rhetoric.
-Increasing the precision of floating-point operations without redoing work is
-in fact possible for many common cases. For example, Newton's method is
-self-correcting, meaning we may use low precision at first, and increase it for
-future iterations. Even pi enjoys such methods: there exists a formula
-revealing any hexadecimal digit of pi without computing any previous digits,
-though it requires about the same amount of work.
-
-Moreover, several floating-point algorithms converge quadratically or faster,
-thus good implementations will asymptotically outperform continued fractions
-as these converge only linearly.
-
-Nonetheless, for lower accuracies, the smaller overhead may give continued
-fractions the edge in certain problems such as finding the square root of 2.
-Additionally, precision decisions are automatic, for example, one simply needs
-enough bits to hold the last computed convergents. Built-in error analysis
-simplifies and hence accelerates development.
+== Installation ==
+
+The GMP library is required. Type:
+  $ make
+
+to compile.
+
+Then try "pi 2000" to generate 2000 digits of pi using a continued
+fraction. It takes longer than I had hoped, but it's faster than
+
+  $ echo "scale = 2000; 4*a(1)" | bc -l
+
+Also try "hakmem 1000" to compute 1000 digits of the example continued fraction
+constant from HAKMEM, which compares favourably with:
+
+  $ echo "scale=1000
+          pi=4*a(1)
+          x=2*sqrt(5)
+          (sqrt(3/pi^2+e(1)))/((e(x)-1)/(e(x)+1)-s(69))" | bc -l
+
+Unlike frac, bc can only output the final answer in one go after all
+calculations are complete.
+
+There's no API documentation; see the source.
+
+== Bugs and other issues ==
+
+I intend to devote time to projects that operate on real numbers rather than
+study real numbers for its own sake. But perhaps then I'll find a perfect
+application for continued fractions, which will push me to fix deficiencies in
+this code:
+
+- I want to replace the condition variable with a semaphore to silence Helgrind
+  (whose documentation states that condition variables almost unconditionally
+  and invariably raise false alarms).
+
+- Computing the continued fraction expansion of pi from the Chudnovsky
+  brothers' Ramanujan formula would be much faster. More constants could
+  benefit from using efficiently computable sequences of narrower intervals
+  for their continued fraction expansions.
+
+- The API could use cosmetic surgery.
+
+- The Makefile is fragile and annoying to maintain and use.
+
+- The testing infrastructure needs upgrading.
+
+- Much more, e.g. see TODOs sprinkled throughout the code.