[Cryptography] floating point

[Jerry Leichter]

On Dec 26, 2014, at 12:55 AM, John Denker <jsd at av8n.com> wrote:
Executive summary:
> *) There are things you an do with floating point, and things you can't.
> *) Recognizing the distinction does not make you an "alleged programmer".
> *) Name-calling is not an acceptable substitute for facts or logic.
> *) Name-dropping allusions to famous scientists is not an acceptable
>  substitute for facts or logic.
...long and worthwhile article about the subtleties, oddities, and "non-mathematical nature" of (mainly IEEE) floating point omitted.

I spent my early years as a mathematician, and "bad" properties like "equality" that isn't an equality relation still bother me intuitively.  But I've spent many more years writing software, and I've come to a somewhat more nuanced view.  Ultimately, what matters isn't mathematical purity - it's usefulness, which is much harder to pin down and much more multi-faceted.  (BTW, this applies to mathematics as well.  The criteria for "usefulness" are different - mainly, "leads to elegant theorems" - but the underlying drive is the same.)

*There is no such thing as a mathematically reasonable fix-precision floating point model*.  The floats are not the rationals, and they are certainly not the reals.  Fixed-length integers aren't the integers either, but at least if properly designed they match the integers mod some value - though those aren't ordered, which leads to all kinds of traps for the unwary when "overflows" occur.  But floats don't really correspond to any well-understood, pre-existing mathematical model.

There are a variety of properties of the rationals (or the reals) you'd like an FP system to have, but you can't have them all at once.  So you have to pick and choose what you keep and what you toss.  Many years ago, APL\360 defined a consistent notion of arithmetic in which two FP values were considered equal if they were within a (configurable) epsilon of each other.  This has all kinds of interesting implications - such as that a (small enough) FP value was considered to be an integer and treated as such - if it's within epsilon of an integer.  So A[1.000001] - or A[1/3 + 1/3 + 1/3] - might be silently treated as A[1].  

Mathematically, this is a horrible system - equality isn't even transitive, for a start.  For most day-to-day computations, however, it turns out to be very useful, giving "intuitive" results.  Tons of calculations - engineering, financial, and other - were done using this system over the years, and people were reasonably happy with the results.  (One could argue that the computations it replaced were previously done on slide rules or on calculators with a fixed number of decimal positions - both of which would, informally, implement a related arithmetic.)

IEEE FP was designed partially in reaction to a variety of earlier FP systems that had really bad properties.  Most of the earlier systems were designed by computer engineers who didn't understand FP but did understand how to get high performance.  (The FP on the old CDC supercomputers was a case in point.)  IEEE FP was designed by numerical analysts.  Except ... it was a subset of numerical analysts, mainly those interested in linear algebra.  They designed a system with properties that were good for one class of problems, perhaps not so good for others.  (Numerical analysts working in other fields have criticized the IEEE design.)

IEEE representations have one enormous advantage:  They come in hardware, so have much higher performance than any software alternative.  (I haven't looked at the FP that comes with graphics cards; I suspect it's mainly a return to the "make it fast" philosophy of the early days, especially since the uses for which they are primarily aimed - computing stuff to put on the screen - isn't sensitive to fine details.  It'll be interesting to see how it evolves as graphics cards are increasingly used as highly-parallel compute engines for other purposes entirely.)  Those who are unhappy with the properties of IEEE arithmetic spend their efforts in building better - more appropriate for their purpose - systems with IEEE as the primitives.

Henry Baker described a standard for geometrical description of objects that will be 3D-printed based on triples of IEEE floats.  A moment's thought reveals how inappropriate that representation is.  In fact, the use of floats *at all* is inappropriate.  Why?  Because floats are entirely about relative error, while the construction of objects in the physical world is about absolute error.  This representation guarantees that you'll be fighting the basic design every step of the way - and, indeed, Baker comments that to determine geometrical properties, you need to ensure that certain values are bitwise identical.  That breaks the entire abstraction that the FP representation gave you.  (Java made that mistake early on, and had to adjust - viz. "fpstrict".)  This (and the related desire for completely reproducible results) is why TeX doesn't use FP any place that "matters".  (It's only used when printing to log files and in similar situations; all computation that affects the typeset output file is done using rational arithmetic.)

Does that mean the standard Baker refers to is "wrong"?  From an elegance/correctness point of view, sure.  From a "usefulness" point of view, probably not.  IEEE FP support is cheap and fast and everywhere.  Any other representation would be more difficult to support widely - though one could well argue that Knuth dealt with exactly this issue in two dimensions in TeX, and one should just use his design and code, which is freely available.  (TeX positioning errors are given in absolute terms and are well under the wavelength of light - certainly good enough for typesetting, good enough for 3D fabrication unless you're building metamaterials.)

                                                        -- Jerry