4 ms·

Arbitrary precision (the library claim) is not infinite-precision (your claim). The original library claim for correct rounding is very important for many task

Arbitrary precision (the library claim) is not infinite-precision (your claim). The original library claim for correct rounding is very important for many tasks, and is the entire reason for that library. I doubt your library does it, it it would claim it, since it's extremely hard to do and would be a great selling point. Here's [1] a slightly older paper with lots of details on the problems in getting such a library to work. There's massive literature on this [1] https://hal-ens-lyon.archives-ouvertes.fr/ensl-01529804/file/crlibm.pdf https://hal-ens-lyon.archives-ouvertes.fr/ensl-01529804/file...

lisper 4y ago
> Arbitrary precision (the library claim) is not infinite-precision True. I've edited my comment to reflect the error. > I doubt your library does it Just for the record, CLN is not mine. I'm just a (casual) user. And you're right, it probably does not do correct rounding. I was unaware of the significance of this. The above notwithstanding, I think CLN is pretty cool and deserves more attention than it gets.
- ChrisLomont 4y ago
  Oh sorry, didn't mean to imply the library was yours. Only that you posted it. Agreed - I think all such libraries are interesting. Knowing the pitfalls of them is also useful and not obvious.
stephencanon 4y ago
A clarification, since this is a thing that frequently confuses people: the importance of correct rounding is that it is the easiest mechanism to unlock reproducibility. If I use library A, and you use library B, but both are correctly rounded, then we know that we get the same result. When reproducibility doesn't matter, it's basically always better to use a not-necessarily-correctly-rounded implementation at somewhat higher precision, as this gets you smaller overall errors for less effort. But there are a lot of domains where reproducibility matters, and that's where correct rounding comes in.
- lisper 4y ago
  Wait, now I'm confused. If what you want is reproducibility, why does it matter that the rounding be correct? It seems to me that what matters in this case is that the rounding conform to some standard or specification. Why should it matter what that standard actually is?
  - MauranKilom 4y ago
    Sure, you could invent a different standard, but what are you going to write into it? "If you input 0.1 into atan, the result should round up when outputting 5 digits, down with 8 digits and up with 12 digits"? Also, "round up" is not any easier than "round correctly" if you require it to be consistent. Say you compute a result like 9.004 and want to round to two digits - if the exact result would have been 8.991, then rounding your computation as 9.01 is different from the standard-specified result of 9.00. So your standard would literally have to specify the desired output for every combination of operation, input, and output precision - obviously impossible.
  - jabl 4y ago
    One usecase, for instance, is if you're writing a compiler and you want to constant propagate floating point operations, and the compile host doesn't necessarily support the same FP formats the target hardware does. But you still want the results to be the same as if you compute it on the target HW at runtime (barring usage of a "damn-IEEE754-just-go-faster" compile option). This, FWIW, is what GCC uses MPFR for.
    - adgjlsfhk1 4y ago
      Note that GCC actually has a bunch of bugs related to this where it will give you different results depending on whether a value gets computed at compile time or runtime.
      - jabl 4y ago
        Been a while since I was actively involved in GCC development, but back then most issues like this AFAIR were due to math functions and not basic arithmetic. GCC doesn't control the target libm, and correctly rounded libm's are rare and much slower than ones which permit a bit more slop in the results.
an1sotropy 4y ago
Thank you for the link to this paper - it's amazing to see how much care and thought can go into analyzing FP computation, and good to be reminded of how much I still have to learn.
- ChrisLomont 4y ago
  If you are interested and like this stuff - ask some questions and I'll post places you can learn what you want.
  - an1sotropy 4y ago
    That's kind of you. I don't know how related it is, but my main interest now is a kind of empirical evaluation of numerical precision. I have some C code (actually students' C code), and one thing I do to characterize it is run it twice, once rounding towards negative infinity, and once towards positive infinity, and see how different they are. Increasing the crappiness of code tends to widen that window (between the two results), but not all crappy code generates a wide window. I would much rather, at a great computational expense that I'm happy to deal with, run the code many many times, each time randomizing the rounding direction just prior to any FP operation, so that I can get a sense of the distribution of numerical results over all possible roundings. I'm contemplating doing things like reading assembly code and injecting random rounding changes, and then compile and run that, but I'm also wondering if others have already done this, in the setting of vanilla C code. And in case its relevant, in this setting, students are only allowed to use single (32-bit) precision floats and operations.
    - ChrisLomont 4y ago
      >run it twice, once rounding towards negative infinity, and once towards positive infinity, and see how different they are That's actually a good method that lots of numerical analysts use. I think C99 has several rounding modes - I often have code that runs the same computation under each mode and look at what your doing. >not all crappy code generates a wide window True, often you need to find the values that make it puke. I think there was a paper recently on doing this automatically.... If I can refind it I'll post - it was cool stuff. >students are only allowed to use single (32-bit) precision floats and operations For stuff this small you can often brute force all values or at least all edge case values. I sometimes do the trick of converting 32 bit integers (watch out for weird C aliasing rules) to hit lots of numbers near precision edges and run them through, denormals, other edge cases, and pseudo-fuzz the results. This will sometimes turn up more. If you teach, and have not worked through some numerical analysis books that provide good background for this stuff, read Goldberg's paper "What Every Computer Scientist Should Know About Floating-Point Arithmetic" [1]. The next good thing to dig through is Higham's book "Accuracy and Stability of Numerical Algorithms" [2] Those will give you lots of places to look for issues, and the ability to analyze algorithms more concretely for floating point issues. [1] https://docs.oracle.com/cd/E19957-01/800-7895/800-7895.pdf https://docs.oracle.com/cd/E19957-01/800-7895/800-7895.pdf [2] http://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accuracy%20and%20Stability%20of%20Numerical%20Algorithms.pdf http://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accura...

lisper 4y ago

> Arbitrary precision (the library claim) is not infinite-precision True. I've edited my comment to reflect the error. > I doubt your library does it Just for the record, CLN is not mine. I'm just a (casual) user. And you're right, it probably does not do correct rounding. I was unaware of the significance of this. The above notwithstanding, I think CLN is pretty cool and deserves more attention than it gets.

ChrisLomont 4y ago
Oh sorry, didn't mean to imply the library was yours. Only that you posted it. Agreed - I think all such libraries are interesting. Knowing the pitfalls of them is also useful and not obvious.

stephencanon 4y ago

A clarification, since this is a thing that frequently confuses people: the importance of correct rounding is that it is the easiest mechanism to unlock reproducibility. If I use library A, and you use library B, but both are correctly rounded, then we know that we get the same result. When reproducibility doesn't matter, it's basically always better to use a not-necessarily-correctly-rounded implementation at somewhat higher precision, as this gets you smaller overall errors for less effort. But there are a lot of domains where reproducibility matters, and that's where correct rounding comes in.

lisper 4y ago
Wait, now I'm confused. If what you want is reproducibility, why does it matter that the rounding be correct? It seems to me that what matters in this case is that the rounding conform to some standard or specification. Why should it matter what that standard actually is?
- MauranKilom 4y ago
  Sure, you could invent a different standard, but what are you going to write into it? "If you input 0.1 into atan, the result should round up when outputting 5 digits, down with 8 digits and up with 12 digits"? Also, "round up" is not any easier than "round correctly" if you require it to be consistent. Say you compute a result like 9.004 and want to round to two digits - if the exact result would have been 8.991, then rounding your computation as 9.01 is different from the standard-specified result of 9.00. So your standard would literally have to specify the desired output for every combination of operation, input, and output precision - obviously impossible.
- jabl 4y ago
  One usecase, for instance, is if you're writing a compiler and you want to constant propagate floating point operations, and the compile host doesn't necessarily support the same FP formats the target hardware does. But you still want the results to be the same as if you compute it on the target HW at runtime (barring usage of a "damn-IEEE754-just-go-faster" compile option). This, FWIW, is what GCC uses MPFR for.
  - adgjlsfhk1 4y ago
    Note that GCC actually has a bunch of bugs related to this where it will give you different results depending on whether a value gets computed at compile time or runtime.
    - jabl 4y ago
      Been a while since I was actively involved in GCC development, but back then most issues like this AFAIR were due to math functions and not basic arithmetic. GCC doesn't control the target libm, and correctly rounded libm's are rare and much slower than ones which permit a bit more slop in the results.

an1sotropy 4y ago

Thank you for the link to this paper - it's amazing to see how much care and thought can go into analyzing FP computation, and good to be reminded of how much I still have to learn.

ChrisLomont 4y ago
If you are interested and like this stuff - ask some questions and I'll post places you can learn what you want.
- an1sotropy 4y ago
  That's kind of you. I don't know how related it is, but my main interest now is a kind of empirical evaluation of numerical precision. I have some C code (actually students' C code), and one thing I do to characterize it is run it twice, once rounding towards negative infinity, and once towards positive infinity, and see how different they are. Increasing the crappiness of code tends to widen that window (between the two results), but not all crappy code generates a wide window. I would much rather, at a great computational expense that I'm happy to deal with, run the code many many times, each time randomizing the rounding direction just prior to any FP operation, so that I can get a sense of the distribution of numerical results over all possible roundings. I'm contemplating doing things like reading assembly code and injecting random rounding changes, and then compile and run that, but I'm also wondering if others have already done this, in the setting of vanilla C code. And in case its relevant, in this setting, students are only allowed to use single (32-bit) precision floats and operations.
  - ChrisLomont 4y ago
    >run it twice, once rounding towards negative infinity, and once towards positive infinity, and see how different they are That's actually a good method that lots of numerical analysts use. I think C99 has several rounding modes - I often have code that runs the same computation under each mode and look at what your doing. >not all crappy code generates a wide window True, often you need to find the values that make it puke. I think there was a paper recently on doing this automatically.... If I can refind it I'll post - it was cool stuff. >students are only allowed to use single (32-bit) precision floats and operations For stuff this small you can often brute force all values or at least all edge case values. I sometimes do the trick of converting 32 bit integers (watch out for weird C aliasing rules) to hit lots of numbers near precision edges and run them through, denormals, other edge cases, and pseudo-fuzz the results. This will sometimes turn up more. If you teach, and have not worked through some numerical analysis books that provide good background for this stuff, read Goldberg's paper "What Every Computer Scientist Should Know About Floating-Point Arithmetic" [1]. The next good thing to dig through is Higham's book "Accuracy and Stability of Numerical Algorithms" [2] Those will give you lots of places to look for issues, and the ability to analyze algorithms more concretely for floating point issues. [1] https://docs.oracle.com/cd/E19957-01/800-7895/800-7895.pdf https://docs.oracle.com/cd/E19957-01/800-7895/800-7895.pdf [2] http://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accuracy%20and%20Stability%20of%20Numerical%20Algorithms.pdf http://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accura...