CODEWITHSUNDEEP
gorandom
felix
felix

Reputation: 9285

Generate random 128 bit decimal in given range in go

Let's say that we have a random number generator that can generate random 32 or 64 bit integers (like rand.Rand in the standard library)

Generating a random int64 in a given range [a,b] is fairly easy:

rand.Seed(time.Now().UnixNano())
n := rand.Int63n(b-a) + a

Is it possible to generate random 128 bit decimal (as defined in specification IEEE 754-2008) in a given range from a combination of 32 or 64 bit random integers?

Upvotes: 6

Views: 2156

Answers (5)

Peter O.
Peter O.

Reputation: 32888

It is possible, but the solution is far from trivial. For a correct solution, there are several things to consider.

For one thing, values with exponent E are 10 times more likely than values with exponent E - 1.

Other issues include subnormal numbers and ranges that straddle zero.

I am aware of the Rademacher Floating-Point Library, which tackled this problem for binary floating-point numbers, but the solution there is complicated and its author has not yet written up how his algorithm works.

EDIT (May 11):

I have now specified an algorithm for generating random "uniform" floating-point numbers—

  • In any range,
  • with full coverage, and
  • regardless of the digit base (such as binary or decimal).

Upvotes: 2

rohanmehto2
rohanmehto2

Reputation: 950

This is definitely what you are looking for.

Upvotes: 0

Alexey Sudachen
Alexey Sudachen

Reputation: 384

It depends how many values you want to generate. If it's enough to have no more 10^34 values in a specified range - it's quite simple.

As I see the problem, a random value in the range min..max can be calculated as random(0..1)*(max-min)+min

Look like we need to generate only decimal128 value in range 0..1. So it's a random value in range 0..10^34-1 with exponent -34. This value can be generated with a golang standard random package.

To multiply, add and substruct float128 values can be used golang math/big package with values normalization.

Upvotes: 1

Sudhir Jonathan
Sudhir Jonathan

Reputation: 17516

Go has a large number package that can do arbitrary length integers: https://golang.org/pkg/math/big/

It has a pseudo random number generator https://golang.org/pkg/math/big/#Int.Rand, and the crypto package also has https://golang.org/pkg/crypto/rand/#Int

You'd want to specify the max using https://golang.org/pkg/math/big/#Int.Exp as 2^128.

Can't speak to performance, though, or whether this is compliant if the IEEE standard, but large random numbers like what you'd use for UUIDs are possible.

Upvotes: 1

hobbs
hobbs

Reputation: 240139

Possible, but by no means easy. Here is a sketch of a solution that might be acceptable — writing and debugging it would probably be at least a day of concerted effort.

Let min and max be primitive.Decimal128 objects from go.mongodb.org/mongo-driver/bson. Let MAXBITS be a multiple of 32; 128 is likely to be adequate.

  1. Get the significand (as big.Int) and exponent (as int) of min and max using the BigInt method.

  2. Align min and max so that they have the same exponent. As far as possible, left-justify the value with the larger exponent by decreasing its exponent and adding a corresponding number of zeroes to the right side of its significand. If this would cause the absolute value of the significand to become >= 2**(MAXBITS-1), then either

    • (a) Right-shift the value with the smaller exponent by dropping digits from the right side of its significand and increasing its exponent, causing precision loss.
    • (b) Dynamically increase MAXBITS.
    • (c) Throw an error.

  3. At this point both exponents will be the same, and both significands will be aligned big integers. Set aside the exponents for now, and let range (a new big.Int) be maxSignificand - minSignificand. It will be between 0 and 2**MAXBITS.

  4. Turn range into MAXBITS/32 uint32s using the Bytes or DivMod methods, whatever is easier.

  5. If the highest word of range is equal to math.MaxUint32 then set a flag limit to false, otherwise true.

  6. For n from 0 to MAXBITS/32:

    • if limit is true, use rand.Int63n (!, not rand.Int31n or rand.Uint32) to generate a value between 0 and the nth word of range, inclusive, cast it to uint32, and store it as the nth word of the output. If the value generated is equal to the nth word of range (i.e. if we generated the maximum possible random value for this word) then let limit remain true, otherwise set it false.
    • If limit is false, use rand.Uint32 to generate the nth word of the output. limit remains false regardless of the generated value.

  7. Combine the generated words into a big.Int by building a []byte and using big/Int.SetBytes or multiplication and addition, as convenient.

  8. Add the generated value to minSignificand to obtain the significand of the result.

  9. Use ParseDecimal128FromBigInt with the result significand and the exponent from steps 2-3 to obtain the result.

The heart of the algorithm is step 6, which generates a uniform random unsigned integer of arbitrary length 32 bits at a time. The alignment in step 2 reduces the problem from a floating-point to an integer one, and the subtraction in step 3 reduces it to an unsigned one, so that we only have to think about one bound instead of 2. The limit flag records whether we're still dealing with that bound, or whether we've already narrowed the result down to an interval that doesn't include it.

Caveats:

  1. I haven't written this, let alone tested it. I may have gotten it quite wrong. A sanity check by someone who does more numerical computation work than me would be welcome.
  2. Generating numbers across a large dynamic range (including crossing zero) will lose some precision and omit some possible output values with smaller exponents unless a ludicrously large MAXBITS is used; however, 128 bits should give a result at least as good as a naive algorithm implemented in terms of decimal128.
  3. The performance is probably pretty bad.

Upvotes: 1

Related Questions