Hacker News Reader

Comment by hakmem | Hacker News Reader

There are a lot of pearls in this - I would call it lab book.

A while ago, I made a slow Clojure implementation of a generalized version of Bill Gospers continued fraction arithmetics from the HAKMEM

http://github.com/timrichardt/stern-brocot-tree

View on HN

Ten years ago, I implemented Gosper's continued fraction arithmetics in Python: http://sun.aei.polsl.pl/~mciura/software/cf.py My module can also compute exp() and log() as well as trigonometric and inverse trigonometric functions. Here are slides from my presentation about it: http://sun.aei.polsl.pl/~mciura/cf.pdf

Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?

Yes. The key to that is approximating reals by the second Ostrogradsky series (or, more properly, Ostrogradsky-Sierpiński series): x = ⎣x⎦ + 1/q₁ − 1/q₂ + 1/q₃ - 1/q₄ + ⋯, where the denominators qₖ are greedily chosen as the largest possible. The following formulas are true: exp(1/q) = [1; q−1, 1, 1, 3q−1, 1, 1, 5q-1,…], exp(x + y) = exp(x)exp(y), and exp(x - y) = exp(x)/exp(y). The algorithm keeps two most recent partial sums of the O-S series: sₖ₋₁ and sₖ. As long as the partial quotients of exp(sₖ₋₁) and exp(sₖ) are equal, it emits them; otherwise, it computes the next partial sum sₖ₊₁. Similar formulas work for tan(x).

try the continuous logarithms now! they are very beautiful and more natural to implement in modern computers

Could you point me to a reference?

this is actually the sole appendix of HAKMEM, (and one of my favorite text files ever)

https://perl.plover.com/classes/cftalk/INFO/gosper.txt

Guessed it but you wrote "continuous" instead of "continued" :) I was excited about something new ;)

And yes, this text is gold. Bill Gosper is the Hunter S. Thompson of science.

yes, of course I meant "continued" (this is a common error by speakers of latin languages since we use the same word for both things)

Yeah, this is Hacker News.

Reply on news.ycombinator.com