[Cryptography] floating point

Sun Dec 28 01:52:06 EST 2014

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 12/27/2014 01:06 PM, Ray Dillinger wrote:
> The IEEE floats are, mathematically speaking, are a set of
> numeric values which approximate (though not very closely)
> a logarithmic distribution.
> 
> This has always annoyed me somewhat.  If you're going to
> approximate a logarithmic distribution, why not just make it
> BE a logarithmic distribution?  Define your numeric value as
> the result of raising some root to the power of the bit
> representation, and you get a logarithmic distribution that
> minimizes relative error better than the system IEEE is using
> now.  Further, you get efficient and accurate(!) FP
> multiplication and division using the same hardware you use
> for integer addition and subtraction.
> 
> Of course you'd still have inaccurate addition and subtraction,
> but heck, you've got that now.  You could at least get
> multiplication and subtraction right, which is better than
> IEEE does.
> 
> You still need an analogue of "denormalized" floats right around
> zero because it breaks down there for the same reasons the IEEE
> mantissa+exponent system does - but you need fixedpoint
> representation anyway! You've got to have it for things like
> modeling software and accounting, etc. where you're trying to
> minimize or eliminate absolute error rather than relative error,
> so using it for numbers near zero doesn't really increase
> overall requirements.

Note that if you want a logarithmic representation you can
have it.  Just take logarithms at an early stage and proceed
from there.  For example, scientists and engineers spend 
a lot of time doing "least squares" fits.  The quantity 
being minimized is actually the /log/ probability, and the
sum of squares represents the product of the probabilities.
Things get weird if you ever need to add probabilities, but
as long as you are just multiplying them, the logarithmic
representation works fine.  It is so convenient that folks
do it without even thinking about it.

Floating point is *not* trying to approximate a logarithmic
distribution.  Just look at the bit-counts:  In IEEE double 
precision, there are 53+1 bits of signed fixed point, plus 
10 bits of exponent.  Mostly it's just fixed point.

Also note: Plain old fixed point is still a thing.  There
is a lot you can do with plain old fixed point.  64-bit
fixed point has a great deal of dynamic range.  You can
convert an integer math processor to fixed point by waving
a feathered stick over it and declaring where you want the 
implicit radix point to be.

Fixed point has a lot of advantages.  Unless there is overflow,
 ++ addition is associative
 ++ multiplication distributes over addition
 ++ addition, subtraction, and multiplication are exact

Each of those things is only approximately (not exactly)
true for floating point.  Also:  If you want to do a lot
of fixed-point stuff, you can use a DSP or MMX/SSE.

Maybe you choose to care only about relative error, but 
there are lots of people who choose differently ... which 
is kinda where this conversation started.  There are a lot
of people who make use of the 2^54 integers that can be
represented in IEEE floating point, represented exactly,
with no relative error, absolute error, or any other 
kind of error.

It's not helpful to think of FP as a logarithmic representation
with a little bit of fixed point pasted on;  mostly it's just
fixed point, with a few bells and whistles to help you keep
track of where the radix point is.

There are some things that floating point can represent
exactly, and some things it can't.  For example, IEEE
double precision cannot represent 0.1 or 0.01 exactly.
However, you can sometimes work around this by combining
floating point with fixed point techniques.  For example,
by computing in cents rather than dollars, FP can represent
$.01 exactly.

Usually, IEEE floating point gives you multiplicative inverses
only approximately, so usually division will be inexact.
(17/10) * (10/17) - 1. = 1.19209e-07 in single precision.
Fixed point doesn't solve the problem.  A logarithmic
representation would give you exact inverses and exact
division, but only at the cost of making addition and
subtraction much messier.  For 99.99% of the customers,
well-behaved addition and subtraction are more important 
than exact division.  Besides, there are other ways of
getting exact division, notably by using /two/ of something
to represent (or approximate) rationals:  Two floats, two
ints, two bignums, or something like that.  This doesn't
solve all the world's problems, but it solves some of
them.  Software packages that deal with rationals have
been around for decades.