4 ms·

If someone can access it, my university notes where I looked into LCGs such as this discusses that in Numerical Recipes, 1992 C Edition, a clever LCG can be use

by snet0 4y ago

If someone can access it, my university notes where I looked into LCGs such as this discusses that in Numerical Recipes, 1992 C Edition, a clever LCG can be used to generates random numbers between 0 and 1. Using a 32 bit int generated by a fast LCG modulo 2^32. The cleverness is that you treat this value as a float. It uses a bit mask to mask only the mantissa of a float-32, and then is OR'd with a value to set the exponent to 127. Subtracting 1 from this results in a random value between 0 and 1, using only simple or bitwise operations!

ralphb 4y ago
This is well-known, and almost trivial. But because I am curious I looked this up in NR 3rd edition. Section 7.1.5 says > The steps above that convert a 64-bit integer to a double precision floating-point value involves both a non-trivial type conversion and a 64-bit floating multiply. They are performance bottlenecks. One can instead directly move the random bits into the right place in the double word with a union structure, a mask, and some 64-bit logical operations; but in our experience this is not significantly faster It goes on to describe a lagged Fibonacci generator which generates values directly as floating point.
binarycoffee 4y ago
This is a widely used method to map random integers to floating point numbers, but it has the disadvantage of wasting 1 bit of float mantissa precision. On modern CPUs, its computational advantage over full-precision mapping methods, such as multiplication by a float, is not always clear [1]. [1] https://github.com/rust-random/rand/issues/416 https://github.com/rust-random/rand/issues/416
10000truths 4y ago
The issue with this is approach that the interval [1,2) has much fewer representable values than [0,1) in IEEE-754 floats, so the range of generatable values is only a fraction of the representable values. On modern hardware, you should instead use a count-leading-zeroes or count-trailing-zeroes instruction on a uniform bit pattern to directly generate the exponent. This is what is done in the Zig standard library: https://github.com/ziglang/zig/pull/10428 https://github.com/ziglang/zig/pull/10428
- binarycoffee 4y ago
  You are right of course, but I would contend that generating as well sub-normal floats is in 99.9% of the cases a needless cost. The reason is that, more often than not, all this extra precision will be immediately lost in subsequent operations. A very common situation is for instance to plug the random number in a log, in which case you need to use log(1-r) rather than log(r) to avoid an infinite at r=0. The problem is, by doing this simple subtraction you have already lost all the subnormal precision.

by snet0 4y ago

ralphb 4y ago

This is well-known, and almost trivial. But because I am curious I looked this up in NR 3rd edition. Section 7.1.5 says > The steps above that convert a 64-bit integer to a double precision floating-point value involves both a non-trivial type conversion and a 64-bit floating multiply. They are performance bottlenecks. One can instead directly move the random bits into the right place in the double word with a union structure, a mask, and some 64-bit logical operations; but in our experience this is not significantly faster It goes on to describe a lagged Fibonacci generator which generates values directly as floating point.

binarycoffee 4y ago

This is a widely used method to map random integers to floating point numbers, but it has the disadvantage of wasting 1 bit of float mantissa precision. On modern CPUs, its computational advantage over full-precision mapping methods, such as multiplication by a float, is not always clear [1]. [1] https://github.com/rust-random/rand/issues/416 https://github.com/rust-random/rand/issues/416

10000truths 4y ago

The issue with this is approach that the interval [1,2) has much fewer representable values than [0,1) in IEEE-754 floats, so the range of generatable values is only a fraction of the representable values. On modern hardware, you should instead use a count-leading-zeroes or count-trailing-zeroes instruction on a uniform bit pattern to directly generate the exponent. This is what is done in the Zig standard library: https://github.com/ziglang/zig/pull/10428 https://github.com/ziglang/zig/pull/10428

binarycoffee 4y ago
You are right of course, but I would contend that generating as well sub-normal floats is in 99.9% of the cases a needless cost. The reason is that, more often than not, all this extra precision will be immediately lost in subsequent operations. A very common situation is for instance to plug the random number in a log, in which case you need to use log(1-r) rather than log(r) to avoid an infinite at r=0. The problem is, by doing this simple subtraction you have already lost all the subnormal precision.