5 ms·

Rendering floating point numbers is hard

38 points by dons 15y ago

iwwr 15y ago
Are logarithmic number systems a better alternative to floats?
- deleted 15y ago
  [deleted]
- sp332 15y ago
  Sometimes. :) They are faster to multiply, divide, exponentiate, and take roots of. But they are a lot harder to add and subtract, and of course it is somewhat less accurate.
nemoniac 15y ago
"Grisu3 works on 99.49% of random IEEE doubles." What a curious benchmark! It makes you wonder all kinds of things like how many IEEE doubles there are; how you sample from them randomly; what kind of coverage of the reals you get; and how relevant it all is.
- JoachimSchipper 15y ago
  IEEE doubles are just 64-bit words; so there are 2^64 and you sample randomly by picking a random 64-bit word. (There are some subtleties: a "random 64-bit word interpreted as a double" is clearly not uniformly distributed over the reals; x86/amd64 uses 80-bit doubles for intermediate results, except when it doesn't; there are things like subnormals ("really small numbers"), Not-a-Number, Infinity, -Infinity, -0; but the above should give you the right general idea)
  - nemoniac 15y ago
    Sure, but to take an extreme example, suppose you have a division operator that fails to check for division-by-zero. Then your operator works in 100 * (1 - 2^63)% of all cases. That gives you 18 nines and sounds pretty convincing but it's hardly the point. In the same way I'm wondering how meaningful it is to say that an algorithm works for 99.49% of all doubles, sampled uniformly. In other words, how could I use that benchmark to make a judgement about using grisu3?
chrisjsmith 15y ago
Keeping everything in rational form would be nice, and easy to present.
- asciilifeform 15y ago
  Let's start with Pi.
  - ianterrell 15y ago
    I'm sure you mean Tau.
  - GregBuchholz 15y ago
    355/113 is good enough for Chuck Moore (the Forth guy). http://www.colorforth.com/pi.htm http://www.colorforth.com/pi.htm [edited to correct blatant error. Thanks Florin]
    - Florin_Andrei 15y ago
      You mean 355/113
      - chrisjsmith 15y ago
        Spot on! Either that or pi is a symbol and we use symbolic algebra. Just convert to the result in floating point at the last minute. Ironically my calculator quite happily manages rational form including PI as a constant: http://h41111.www4.hp.com/calculators/uk/en/scientific/smartcalc300s.html http://h41111.www4.hp.com/calculators/uk/en/scientific/smart...
  - eru 15y ago
    Needs lazy evaluation. Just don't try to look at the whole number at once.
    - sp332 15y ago
      Here you go: http://crd.lbl.gov/~dhbailey/pi/pi-alg http://crd.lbl.gov/~dhbailey/pi/pi-alg Now you can calculate any individual digit of pi without having to find any of the others! Unfortunately, it only works in base 16 or base 2, not base 10.
japaget 15y ago
Link appears to be down. No joy with Google or Corel cache. Google search turned up a PDF at http://0-dl.acm.org.millennium.lib.cyut.edu.tw/ft_gateway.cfm?id=1806623&type=pdf http://0-dl.acm.org.millennium.lib.cyut.edu.tw/ft_gateway.cf...
- mukyu 15y ago
  http://webcache.googleusercontent.com/search?aq=f&sourceid=chrome&ie=UTF-8&q=cache%3Ahttp%3A%2F%2Fwww.serpentine.com%2Fblog%2F2011%2F06%2F29%2Fhere-be-dragons-advances-in-problems-you-didnt-even-know-you-had%2F http://webcache.googleusercontent.com/search?aq=f&source... worked for me, but it appears to be completely back up now
sc68cal 15y ago
the Grisu family acts as the default rendering algorithms in both the V8 and Mozilla Javascript engines (replacing David Gay's 17-year-old dtoa code) Hmm. I think maybe a weekend hack is in order. Perhaps dtoa in Python can be replaced in a similar fashion, since Python maintains David Gay's algorithm as an upstream source. http://hg.python.org/cpython/file/fc831c49216d/Python/dtoa.c http://hg.python.org/cpython/file/fc831c49216d/Python/dtoa.c EDIT: Looks like there has already been some gripes about the quality of David Gay's implementation. http://bugs.python.org/issue9009 http://bugs.python.org/issue9009

38 points by dons 15y ago

iwwr 15y ago

Are logarithmic number systems a better alternative to floats?

deleted 15y ago
[deleted]
sp332 15y ago
Sometimes. :) They are faster to multiply, divide, exponentiate, and take roots of. But they are a lot harder to add and subtract, and of course it is somewhat less accurate.

nemoniac 15y ago

"Grisu3 works on 99.49% of random IEEE doubles." What a curious benchmark! It makes you wonder all kinds of things like how many IEEE doubles there are; how you sample from them randomly; what kind of coverage of the reals you get; and how relevant it all is.

JoachimSchipper 15y ago
IEEE doubles are just 64-bit words; so there are 2^64 and you sample randomly by picking a random 64-bit word. (There are some subtleties: a "random 64-bit word interpreted as a double" is clearly not uniformly distributed over the reals; x86/amd64 uses 80-bit doubles for intermediate results, except when it doesn't; there are things like subnormals ("really small numbers"), Not-a-Number, Infinity, -Infinity, -0; but the above should give you the right general idea)
- nemoniac 15y ago
  Sure, but to take an extreme example, suppose you have a division operator that fails to check for division-by-zero. Then your operator works in 100 * (1 - 2^63)% of all cases. That gives you 18 nines and sounds pretty convincing but it's hardly the point. In the same way I'm wondering how meaningful it is to say that an algorithm works for 99.49% of all doubles, sampled uniformly. In other words, how could I use that benchmark to make a judgement about using grisu3?

chrisjsmith 15y ago

Keeping everything in rational form would be nice, and easy to present.

asciilifeform 15y ago
Let's start with Pi.
- ianterrell 15y ago
  I'm sure you mean Tau.
- GregBuchholz 15y ago
  355/113 is good enough for Chuck Moore (the Forth guy). http://www.colorforth.com/pi.htm http://www.colorforth.com/pi.htm [edited to correct blatant error. Thanks Florin]
  - Florin_Andrei 15y ago
    You mean 355/113
    - chrisjsmith 15y ago
      Spot on! Either that or pi is a symbol and we use symbolic algebra. Just convert to the result in floating point at the last minute. Ironically my calculator quite happily manages rational form including PI as a constant: http://h41111.www4.hp.com/calculators/uk/en/scientific/smartcalc300s.html http://h41111.www4.hp.com/calculators/uk/en/scientific/smart...
- eru 15y ago
  Needs lazy evaluation. Just don't try to look at the whole number at once.
  - sp332 15y ago
    Here you go: http://crd.lbl.gov/~dhbailey/pi/pi-alg http://crd.lbl.gov/~dhbailey/pi/pi-alg Now you can calculate any individual digit of pi without having to find any of the others! Unfortunately, it only works in base 16 or base 2, not base 10.

japaget 15y ago

Link appears to be down. No joy with Google or Corel cache. Google search turned up a PDF at http://0-dl.acm.org.millennium.lib.cyut.edu.tw/ft_gateway.cfm?id=1806623&type=pdf http://0-dl.acm.org.millennium.lib.cyut.edu.tw/ft_gateway.cf...

mukyu 15y ago
http://webcache.googleusercontent.com/search?aq=f&sourceid=chrome&ie=UTF-8&q=cache%3Ahttp%3A%2F%2Fwww.serpentine.com%2Fblog%2F2011%2F06%2F29%2Fhere-be-dragons-advances-in-problems-you-didnt-even-know-you-had%2F http://webcache.googleusercontent.com/search?aq=f&source... worked for me, but it appears to be completely back up now

sc68cal 15y ago

the Grisu family acts as the default rendering algorithms in both the V8 and Mozilla Javascript engines (replacing David Gay's 17-year-old dtoa code) Hmm. I think maybe a weekend hack is in order. Perhaps dtoa in Python can be replaced in a similar fashion, since Python maintains David Gay's algorithm as an upstream source. http://hg.python.org/cpython/file/fc831c49216d/Python/dtoa.c http://hg.python.org/cpython/file/fc831c49216d/Python/dtoa.c EDIT: Looks like there has already been some gripes about the quality of David Gay's implementation. http://bugs.python.org/issue9009 http://bugs.python.org/issue9009