3 ms·

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 contin

by hakmem 9y ago

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 http://github.com/timrichardt/stern-brocot-tree

enriquto 9y ago
try the continuous logarithms now! they are very beautiful and more natural to implement in modern computers
- hakmem 9y ago
  Could you point me to a reference?
  - enriquto 9y ago
    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 https://perl.plover.com/classes/cftalk/INFO/gosper.txt
    - hakmem 9y ago
      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.
      - enriquto 9y ago
        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)
        hakmem 9y ago
        Yeah, this is Hacker News.
mci 9y ago
Ten years ago, I implemented Gosper's continued fraction arithmetics in Python: http://sun.aei.polsl.pl/~mciura/software/cf.py 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 http://sun.aei.polsl.pl/~mciura/cf.pdf
- hakmem 9y ago
  Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?
  - mci 9y ago
    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).

by hakmem 9y ago

enriquto 9y ago

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

hakmem 9y ago
Could you point me to a reference?
- enriquto 9y ago
  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 https://perl.plover.com/classes/cftalk/INFO/gosper.txt
  - hakmem 9y ago
    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.
    - enriquto 9y ago
      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)
      - hakmem 9y ago
        Yeah, this is Hacker News.

mci 9y ago

Ten years ago, I implemented Gosper's continued fraction arithmetics in Python: http://sun.aei.polsl.pl/~mciura/software/cf.py 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 http://sun.aei.polsl.pl/~mciura/cf.pdf

hakmem 9y ago
Great, I will definitely have a look at it. Did you implement exp(x) for any continued fraction x?
- mci 9y ago
  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).