Hacker News Reader

Comment by lisper | Hacker News Reader

A similar library with even more capabilities:

https://www.ginac.de/CLN/

Includes not only infinite-precision [correction: arbitrary-precision] floats (not sure about the correct rounding part) but also integers (so subsumes GMP), rationals, complex numbers, and polynomials.

View on HN

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...

> 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.

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.

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.

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?

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.

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.

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.

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.

>When reproducibility doesn't matter,

If it doesn't matter, then high precision rarely matters either. Once you have results with unknown noise in them, and you do a few operations on those, the noise compounds, at approximately sqrt(N) bits for N steps of computation (rough estimate, it certainly depends on algorithm selection, compiler nuances, stability of problem, etc.). So high precision degrades quickly when doing any work without using a reproducible and understood rounding mode.

>correct rounding is that it is the easiest mechanism to unlock reproducibility

Any rounding method works works for reproducibility - truncate, round to zero, Bankers rounding, etc., all (roughly) equivalently hard/easy to implement. However, pretty much none of these are possible without the ability to do correcting rounding first as a result of the Table Makers' Dilemma.

For example, Banker's rounding is generally better for doing computation than the usual correctly rounded. Knuth has some papers on this somewhere which are fascinating.

Also note most of the non-reproducible issues in numerical computation are compiler added - compile code with GCC version X, get one result, compile with later version, and results may change. Or across compilers. Negative 0, denormals, rounding modes, all need carefully dealt with. It can be done, but is not trivial. Keeping floating point solid is very, very tricky over compilers and time.

Note that bankers rounding is a subset of correct rounding since bankers rounding only affects ties.

> If it doesn't matter, then high precision rarely matters either. Once you have results with unknown noise in them, and you do a few operations on those, the noise compounds, at approximately sqrt(N) bits for N steps of computation (rough estimate, it certainly depends on algorithm selection, compiler nuances, stability of problem, etc.). So high precision degrades quickly when doing any work without using a reproducible and understood rounding mode.

This isn't really true for any of the numerous numerical algorithms that satisfy backwards error bounds; there you would always prefer to have a well-rounded arithmetic at higher precision, if reproducibility is not required.

> Any rounding method works works for reproducibility

Only if you round _correctly_ in that direction.

> Banker's rounding is generally better for doing computation than the usual correctly rounded.

Banker's rounding _is_ the default IEEE 754 rounding mode.

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.

If you are interested and like this stuff - ask some questions and I'll post places you can learn what you want.

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.

>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 [2] http://ftp.demec.ufpr.br/CFD/bibliografia/Higham_2002_Accura...

I like and assign the Goldberg paper. I haven't spent much time with the Higham book; thank you for for full text link.

In my class, FP computation is something I try to teach the students to be mindful of, but it is hardly the focus of the class (about certain kinds of data visualization). FP computation arises in lots of different places in many different functions, often in the context of a larger data processing pipeline that actually starts and ends with 16-bit integers (e.g. medical imaging data). So I'm not sure how I'd thoroughly exercise the FP-related code in the way that you describe. Hence my current use of something I can easily control at the outset of the whole pipeline (the direction of rounding).

Do you have any ideas on injecting randomized rounding mode changes prior to FP ops in the assembly, or something functionally equivalent for characterizing C code (ideally without code changes)? I just found [1] which seems extremely related, but I'll have to look into whether the code still works.

[1] http://www.iboview.org/random_rounding/

At the risk of just talking to myself, I'll note that a google scholar search on the [1] above led me to this phd [2] which in turn led me to two newer tools, Verrou [3] and Verificarlo [4] which involve Valgrind and Docker, respectively, though I'd have to understand what exactly is being contained by Docker for Verrou. But it makes me appreciate more the minimalist approach of Knizia et al. in [1], which does involve recompilation of modified assembly, but that's something I'm doing multiple times with student code already.

[2] https://tel.archives-ouvertes.fr/tel-03110553/document

[3] https://github.com/edf-hpc/verrou

[4] https://github.com/verificarlo/verificarlo

MPFR has some timing comparison on its page.

https://www.mpfr.org/mpfr-4.0.1/timings.html

Also, MPFR depends on GMP which has integers and rationals. Then there is MPC which in turn depends on MPFR and provides complex numbers.

https://www.multiprecision.org/mpc/

IMO, this highlights that you should pretty much always use Arb instead of MPFR if you have a choice.

Arb depends on MPFR, so it is not exactly "instead of".

https://arblib.org/setup.html#dependencies

Reply on news.ycombinator.com