[Cryptography] floating point

John Denker jsd at av8n.com
Fri Dec 26 00:55:12 EST 2014

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.

Here is a /partial/ list of issues and non-issues:

1) There is a distinction between /numbers/ and /numerals/.  It
 is quite common to have multiple representations for the same
 number, such as seventeen, 17, XVII, 0x11, 17.0000, and literally
 infinitely many others.  This is something that people were 
 supposed to learn in third grade.

 The fact that IEEE floating point has two numerals that represent
 the number zero is not a serious problem.  It is a third-grade
 problem.  It is manageable with minimal effort.

2) IEEE floating point is not the only game in town.  Forsooth,
 it seems likely that most of the floating point done in the
 world today is /not/ IEEE compliant.  Hint:  GPUs.

 If you want IEEE floating point behavior, and it is not 
 supported in the hardware, it is painful to implement it
 in software.

3) There are many different equivalence relationships in the
 world.  A blue triangle is shapewise_equivalent to a red 
 triangle.  A blue triangle is colorwise_equivalent to a 
 blue square.  Take your pick.

 In the computer, we have arithmetical comparison as well as
 bitwise comparison, stringwise comparison, et cetera.  Take
 your pick.  Different ones are good for different purposes.

4) Restricting attention now to IEEE floating point default
 behavior, there are three types of entities to consider:
  -- rfloat: regular floating point numbers, representing a 
    subset of the rational numbers.
  -- xfloat:  all the above, extended to include +inf and -inf.
    I don't care whether you consider infinity to be a "number"
    or not.
  -- xxfloat: all of the above, extended to include NaN, which
    (as it says on the tin) is /not/ a number.  Even though it
    is not a number, it is an xxfloat entity.

 So, to answer a question that was previously asked:  In the
 domain of xxfloats, the arithmetic == operator is definitely
 /not/ an equivalence relation, because it fails the "reflexive"
 requirement.  Specifically, (NaN == NaN) is false.  If we 
 don't have a viable notion of equality, we can't even ask
 the question about whether something is a function or not.

 In the xxfloat domain, arithmetical == does not imply bitwise
 equality ... or vice versa:
  -- 0.0 == -0.0 but the representations are bitwise different.
  -- NaN != NaN but the representations are bitwise the same.

 Do not ask me to explain why NaN != NaN returns true.  I am 
 quite aware of the traditional and historical explanations.
 They just don't make any sense.

 If we focus attention on the xfloat domain, narrowly speaking,
 then arithmetic == is an equivalence relation as far as I can
 tell.  In particular, let 
        a = 0.0 
        b = -0.0
 Then a is == to b, and any xfloat that is equal a is also == 
 to b.

 On the other hand, if we mix ints and xfloats, then arithmetic
 == is not an equivalence relation, because if fails the 
 "transitive" requirement.  Specifically, due to a peculiar 
 notion of /promotion to float/ you can have p == q and q == r 
 but p != r.  I have code that demonstrates this.

 On the third hand, if p == 0 and 0 == r then p == r, so 
 the example that provoked this discussion is still not a 
 good example.

5) Within the xfloat domain, atan2 is /not/ a function, but 
 that's overkill;  there are plenty of simpler examples, not 
 involving transcendental functions.  Indeed, xfloat divide 
 is not a function, because (a == b) is true whereas (1/a == 1/b)
 is false.  Recall that
        a = 0.0 
        b = -0.0
 Also the usual decimal formatting is not an injective mapping,
 because b is arithmetically == to a, but str(b) is not stringwise
 equal to str(a).  That is, "-0" is not stringwise equal to "0".

6) Even within IEEE floating point, default behavior is not
 the only allowed behavior.  If you are writing a low-level
 library, with no control over the big picture, it is difficult
 to find /any/ floating point operations that are safe.  Even
 simple operations such as add, subtract, multiply, and divide
 could trap out and die.

 Conversely, some things that you might want to trap out or
 return NaN -- such as atan2(0,0) -- do not.  OTOH you could
 write wrappers for such things.

7) Looking at the standards won't tell you what happens in the
 real world.
  -- Chez moi clang++ will not trap on floating divide by zero,
   no matter how politely you ask, even though other traps
   behave as expected.
  -- Chez moi g++ labels every FP trap as "divide by zero", even
   when something else (e.g. underflow) actually happened.
  -- et cetera.

8) The things I am calling FP "traps" are commonly called exceptions,
 but they are not to be confused with C++ exceptions.  With a bit
 of work you can convert an FP trap into a C++ exception.

More information about the cryptography mailing list