Prev: Different Views of 3d matrix
Next: OPEN error inconsistent
From: Richard Maine on 13 Feb 2010 13:06
steve <kargls(a)comcast.net> wrote:

> On Feb 13, 2:32 am, tho...(a)antispam.ham wrote:
> > cubsfan <cubsfan...(a)gmail.com> writes:

> > If so, then simply multiply by 4E16 and then subtract 2E16.
>
> The subtraction of two large number can lead to catastrophic
> cancellation, which may lead to some undesired bias in the
> final sequence. It might be better to multiply the result
> of random_number by 2 and then subtraction 1, and then multiply
> by 2e16.

The subtraction of two small numbers can lead to the same kind of
cancellation. Cancellation happens when you subtract two nearly equal
numbers of any magnitude. It is independent of scale (at least with
floatting point, which these numbers are). The above-proposed change
should make no difference in terms of cancellation.

I would tend to do the subtraction before the scaling, but for a reason
having nothing to do with cancellation. I would do it just because it
keeps the scaling factor in one place in the equation instead of two.

--
Richard Maine | Good judgment comes from experience;
email: last name at domain . net | experience comes from bad judgment.
domain: summertriangle | -- Mark Twain
From: glen herrmannsfeldt on 13 Feb 2010 14:41
steve <kargls(a)comcast.net> wrote:
> On Feb 13, 2:32?am, tho...(a)antispam.ham wrote:
(snip on random number generation)

>> If so, then simply multiply by 4E16 and then subtract 2E16.

> The subtraction of two large number can lead to catastrophic
> cancellation, which may lead to some undesired bias in the
> final sequence. It might be better to multiply the result
> of random_number by 2 and then subtraction 1, and then multiply
> by 2e16.

In general, that is a good suggestion.

It isn't so obvious to me in this case, but partly that depends
on what biases are undesired. Analyzing those in this case helps
understand some of the properties of random number generators
and floating point arithmetic.

Many random number generators generate equally spaced values
in the range between 0.0 and (slightly less than) 1.0.

Assuming binary floating point, multplying by 4e16 tends to
mix up the random bits, but mostly they should still be random,
assuming the original bits are random. For values where
the result, after subtraction, is close to zero on post normalization
you will get zeros for the low bits. With the multiply by
two, subtract one, and then multiply, the bits will be lost
on the subtract, and non-random but non-zero low bits will
be generated by the mutliplication. It isn't so obvious
that one is better or worse than the other.

On systems with decimal floating point the analysis will
be different.

-- glen
From: glen herrmannsfeldt on 13 Feb 2010 14:49
Richard Maine <nospam(a)see.signature> wrote:
> steve <kargls(a)comcast.net> wrote:
(snip)

>> The subtraction of two large number can lead to catastrophic
>> cancellation, which may lead to some undesired bias in the
>> final sequence. It might be better to multiply the result
>> of random_number by 2 and then subtraction 1, and then multiply
>> by 2e16.

> The subtraction of two small numbers can lead to the same kind of
> cancellation. Cancellation happens when you subtract two nearly equal
> numbers of any magnitude. It is independent of scale (at least with
> floatting point, which these numbers are). The above-proposed change
> should make no difference in terms of cancellation.

The result will likely be different, but the loss of randomness
should be about the same.

> I would tend to do the subtraction before the scaling, but for a reason
> having nothing to do with cancellation. I would do it just because it
> keeps the scaling factor in one place in the equation instead of two.

One that I didn't think about earlier, the rounding of the two
scaling factors could be different. That might result in different
rounding, which might also be a bias. Specifically, it might be
that results equal or greater than 2e16 could result even though
they might not otherwise. On average, though, I believe that they
are both equally useful.

-- glen
From: steve on 13 Feb 2010 18:45
On Feb 13, 10:06 am, nos...(a)see.signature (Richard Maine) wrote:
> steve <kar...(a)comcast.net> wrote:
> > On Feb 13, 2:32 am, tho...(a)antispam.ham wrote:
> > > cubsfan <cubsfan...(a)gmail.com> writes:
> > > If so, then simply multiply by 4E16 and then subtract 2E16.
>
> > The subtraction of two large number can lead to catastrophic
> > cancellation, which may lead to some undesired bias in the
> > final sequence.  It might be better to multiply the result
> > of random_number by 2 and then subtraction 1, and then multiply
> > by 2e16.
>
> The subtraction of two small numbers can lead to the same kind of
> cancellation. Cancellation happens when you subtract two nearly equal
> numbers of any magnitude. It is independent of scale (at least with
> floatting point, which these numbers are). The above-proposed change
> should make no difference in terms of cancellation.
>
> I would tend to do the subtraction before the scaling, but for a reason
> having nothing to do with cancellation. I would do it just because it
> keeps the scaling factor in one place in the equation instead of two.

Richard,

You're absolutely correct! My only defense is lack of coffee
intake at the time of my post. As penance, I'll read Goldberg
for the umpteenth time.

--
steve
From: Gib Bogle on 13 Feb 2010 20:27
steve wrote:
> On Feb 13, 2:32 am, tho...(a)antispam.ham wrote:
>> cubsfan <cubsfan...(a)gmail.com> writes:
>>> Sorry, I should have clarified: this is for a school physics project,
>>> not formal research. I would think that I would want a uniform
>>> distribution (I'm in high school, I don't know a whole lot about
>>> statistics) although I don't think that matters too much. I simply
>>> need the program to generate a random number (or pseudorandom number,
>>> I don't care) between -2E16 and 2E16, and I'll have the program repeat
>>> that probably up to 1,000 times. Sjouke's suggestion of using
>>> random_number and multiplying by 2E16 would work fine, I think, except
>>> all the numbers would be positive.
>> If so, then simply multiply by 4E16 and then subtract 2E16.
>
> The subtraction of two large number can lead to catastrophic
> cancellation, which may lead to some undesired bias in the
> final sequence. It might be better to multiply the result
> of random_number by 2 and then subtraction 1, and then multiply
> by 2e16.

It's extremely unlikely that this will be an issue for this user's application -
a high school project. Let's not get too precious.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Different Views of 3d matrix
Next: OPEN error inconsistent