|
(found via comp.lang.scheme)
This paper (you have to scroll down a bit) shows how and why to use continuted fractions for doing exact arithmetic on irrationals.
Why use algorithms that are at least twice as hard as the usual
algorithms on numbers in positional notation (e.g. decimal or
binary)? One answer is that many numbers, such as pi and e, can be
represented exactly, using little programs (coroutines) to provide
indefinitely many continued fraction terms on demand.
But the algorithms for sum, product, etc. of two such numbers have
this same property, for they produce their output as they read their
input. Thus we can cascade several of these routines so as to
evaluate arithmetic expressions in such a way that output stream
begins almost immediately, and yet can continue almost indefinitely.
The user is freed from having to decide in advance just how much
precision is necessary and yet not wasteful.
Quite a lot of math, so if that's not to your liking just skip this one. However those into numerical computation should enjoy it.
Notice that to use these techniques in a programming language, support for infinite streams or coroutines is needed.
Posted to general by Ehud Lamm on 2/9/01; 1:46:05 PM
|
Continued Fraction Arithmetic - Bill Gosper
