Re: Odd Division By Zero Error

Jeffrey Cunningham <jeffrey <at> jkcunningham.com> writes:

> Isn't an "extra density of floats around 0" -- by definition -- a
> non-uniform distribution? 

Not in the sense that I mean.  Or possibly "yes", but welcome to the
world of floating point: because floating point numbers are a discrete
set, not a continuum, there's no such thing as a continuous uniform
distribution using floats, only particular approximations.

Briefly, a floating point number is represented by sign, mantissa and
exponent.  Sign is always +1 or -1.  What remains is the mantissa, which
is a representation of the bits after the decimal point in the binary
number 1.xxxxxxxxxxxxxx..., and the exponent, which indicates the power
to which 2 must be raised to get you the number you want.  (I am eliding
lots of details here; there are references where you can read them).

So for example, 0.5 is represented as the sign/mantissa/exponent triple
(1, 0, -1); 0.75 is (1, 10000000..._2, -1), 0.875 is (1, 11000000..._2,
-1), and so on.  The point here is that the density of representable
floating points /changes/ as the exponent changes: there are as many
machine floats between 0.25 and 0.5 as there are between 0.5 and 1, and
this isn't some kind of transfinite sleight of hand, this is a finite,
countable set.

So, near zero, there are more possible floats than there are near 1.
Obviously, the RNG compensates for that, by having the possible floats
near zero be generated with lower probability than those near one.  But
the point is that there is more than one way of performing that
compensation: the appropriate probability mass could be distributed
evenly over all possible floats within an evenly-spaced region, or a
single representative in a region could be selected as an archetype --
and if so, which representative?

SBCL's strategy for generating numbers between 0 and 1 isn't so utterly
stupid as you seem to think; it makes one particular choice, by
selecting floats between 1 and 2 (which does have a uniform density of
representable floats), and then subtracting 1.  This has the effect of
emphasizing the probability of generating 0 compared with the floating
point numbers which are in fact representable in the region of 0, but
that effect has potential virtues too (such as preserving the basic
symmetry of the region near 0 and near 1 in the conceptual uniform
distribution).

> I would think this is highly undesirable behavior in a uniform RNG and
> should be corrected.

Tell you what: please specify unambiguously, paying reference to the
hardware representations, the behaviour of the RNG when given a
single-float 1.0 argument, and justify why the specified behaviour is
better than all other behaviours in all circumstances.

Cheers,

Christophe

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/

Re: Odd Division By Zero Error

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/

_______________________________________________
Sbcl-help mailing list
Sbcl-help <at> lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/sbcl-help

Re: Odd Division By Zero Error

In article <E1SoKEb-000696-PN <at> hera.math.uni.wroc.pl>,
 Waldek Hebisch <hebisch <at> math.uni.wroc.pl> wrote:

> Christophe Rhodes wrote:
> > The issue at hand is whether the "extra" density of floats around 0
> > should be used by the RNG.  At first, it seems obvious that it should,
> > because well, why not?
> 
> One paradigm for floating point operations is that operation is
> first performed exactly and after that the result is rounded
> to a representable float.

According to this view, the probability of (random 1.0) returning 1.0 
should be positive. In fact, it should be equal to the probability of 
the random float being < 2^{-25}. I detect a certain tension with the 
spec here.

> > On the other hand, imagine a simple use of a RNG
> > to generate samples from a distribution using the CDF and a lookup
> > table: generate a float between 0 and 1 and transform according to the
> > inverse of the CDF.  Ignoring for the moment the actual generation of
> > zeros, if the RNG exploits the wide range of floats around 0, the lower
> > tail of the distribution will be much, much more explored than the upper
> > tail, because the floating point resolution around 0 is far greater than
> > it is around 1.
> 
> I am not sure what you mean by "more explored".

Many more distinct values in the left tail than in the right one.

> When RNG makes good use of extra
> absolute precision available close to 0 then tail of transformed
> distribution is much closer to the true exponential distibution.

Ah, but what happens if I need my extra precision at the other end? Or 
what if I'm working with a symmetric PDF? Or, what if my uniform's lower 
bound isn't 0?

> Of course, the user may do something stupid, like using log(1 - x)
> with x unifor in (0,1) to generate exponential distibution.  Then
> extra effort spent close to 0 is wasted.

http://en.wikipedia.org/wiki/Antithetic_variates. It's not stupid, but 
*useful*; sophisticated, one might even say.

> Given the above I think that RNG which makes use of extra precision
> around 0 is better than one which does not.

I like the current behaviour for two reasons: it's simple to explain and 
to reason about (we generate random fractions with a fixed denominator, 
and express them as floats), and it's the most common way to do it.

Simplicity is important to me because, as I noted above, getting small 
values around 0 right isn't enough: the exact same problems, modulo 
trivial differences, still crop up. The gain in correctness of intuitive 
code are extremely partial, and contingent on avoiding intuitively 
equivalent reformulations.

This plays in the second reason: AFAICT, it's by far the most common way 
to generate uniforms (either the U[1, 2)-1 trick, or by taking 
exactly-represented integers *and scaling them by a reciprocal*). Any 
issue with this way of doing things is common and language independent, 
and workarounds are likely to be known. Intuitively, any solution would 
still be applicable when generating tiny values; realistically, I know 
better than to trust my intuition here. I could certainly believe that 
there are strange side-effects on statistics when using these variates 
in stochastic simulations. Either way, someone who cares about that 
ought to be basing their experiments on well-tested methods, and these 
methods will most likely have been tested with a fixed-precision uniform 
generator.

Oh, extra data point: none of the test suite that I know of (diehard, 
dieharder, TestU01) attempts to detect that behaviour.  Still, I should 
be back in Montreal very soon, and I'll try to ask some stochastic 
simulation people.

Paul Khuong

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/

Re: Odd Division By Zero Error

Fun fact: there are 127 times more IEEE single-floats in [0,1) than in [1,2).

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/

Re: Odd Division By Zero Error

m_mommer <at> yahoo.com (Mario S. Mommer) writes:

>> There are other issues, but this one was enough to convince me that I
>> didn't want to place too much emphasis on my own instinct, and that I'd
>> like to read "what every RNG maintainer should know about actual uses of
>> floating point random variates".
>
> Could you elaborate? I'm interested in hearing about those other issues.
>
> In particular, do you know of any code that would actually break with
> this patch?

Sorry, too strong: I blame wading through exam papers.  I meant "There
may be other issues".  I don't know of code that would break under an
RNG that exploits the full float resolution around zero; what I meant
was that I was more uncertain about "correct" RNG behaviour.

A brief survey of other language runtimes didn't suggest that the
current RNG was wildly out of line; there's a variety of float range
RNGs out there, and only relatively few use the higher float resolution
near zero.

Cheers,

Christophe

------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and 
threat landscape has changed and how IT managers can respond. Discussions 
will include endpoint security, mobile security and the latest in malware 
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/