From 03e029676c6f4fa3d76524368d81861448c86b51 Mon Sep 17 00:00:00 2001 From: Ben Lynn Date: Fri, 19 Sep 2008 00:53:28 -0700 Subject: [PATCH] Moved README to website. Add snapshot target to Makefile. --- Makefile | 6 ++- README | 185 +++++++++++++++++---------------------------------------------- 2 files changed, 54 insertions(+), 137 deletions(-) rewrite README (85%) diff --git a/Makefile b/Makefile index d363ac5..a181fb1 100644 --- 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 --- a/README +++ b/README @@ -1,136 +1,49 @@ -= 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. -- 2.11.4.GIT