• Create Account

# Random Arbitrary Precision Numbers

7 replies to this topic

### #1Ectara  Crossbones+   -  Reputation: 2080

Like
0Likes
Like

Posted Yesterday, 10:11 PM

I have an arbitrary precision number class, and I'm looking for a way to generate numbers in a thread-safe way by having the caller pass in the RNG state. What do you think is the best way to generate a random arbitrary precision number? I have three random functions, one that generates a random number, one that generates a random number modulo a specified number, and one that generates a random number that is a certain number of bits in size. I considered randomly generating each piece of the number separately, or filling it all with random bytes, but I haven't yet decided on what the interface for the RNG state should look like, given that the number class is templated, so each "digit" in the class can vary in size, so the either the RNG class or the method that uses it has to account for this disparity.

Edited by Ectara, Yesterday, 11:40 PM.

### #2Bacterius  Crossbones+   -  Reputation: 6648

Like
0Likes
Like

Posted Yesterday, 10:27 PM

What does "generating a random number" mean? Is it a arbitrary precision decimal class, otherwise what should the maximum number be? Anyway, each of these can be achieved efficiently by simply generating each digit at random followed by some post-processing. I don't think having a templated digit size should be a problem - the generation process is much more efficient if the digits are powers of two, but I think an algorithm can handle arbitrary digit sizes (and you can always specialize as needed).

So for the interface I'd go with a function like "int<digit_size> rand_range(int<digit_size> n, random_engine engine)" or something like that, along with "rand_bits" that takes the number of bits needed (ideally as a plain unsigned integer, not an arbitrary precision integer).

The RNG state itself should IMHO be separate from the way it is used in the code, it's not a "random digit generator", it's a PRNG and so should behave that way, with functions to generate random bits, a random integer, a random double, and so on... (or just random bits, if you opt for separating the underlying random generator from the distribution to generate, which has its advantages). Another alternative is to extend your RNG class with a random arbitrary precision integer function, but I don't really like that approach as it couples the two classes.

I would try and promote interoperability with other RNG states, how were you thinking of proceeding? Is your RNG state custom-made specifically for your class, or were you planning on basing it on something standard (e.g. the C++11 random engines)?

"The best comment is a deleted comment."

### #3Ectara  Crossbones+   -  Reputation: 2080

Like
0Likes
Like

Posted Yesterday, 11:01 PM

What does "generating a random number" mean? Is it a arbitrary precision decimal class, otherwise what should the maximum number be?

I guess I could remove the most general function; it would have generated a number up to as large as allowed by the implementation. If one really wanted this behavior, they could generate a random number with a bit count of either (digit_bits * max_digits) or 2^size_type_bits - 1, whichever is less, ignoring the fact that it'd potentially fail to allocate. The other two have an upper bound defined by either a number that is the divisor, or a number of bits.

I would try and promote interoperability with other RNG states, how were you thinking of proceeding? Is your RNG state custom-made specifically for your class, or were you planning on basing it on something standard (e.g. the C++11 random engines)?

I was kind of torn between an approach where each RNG class has a unified interface, with functions to return an integer, return a normalized float, fill an array of characters... etc., and an approach where the class could have a templated get function, which could have specializations to efficiently return valid values of a given type, and fallback to writing over the value with random characters. Both have pros and cons.

The standard approach is clearly the most flexible, but also the least practical; it provides values in a way that need a large amount of processing and shuffling in order to be used, by generally returning a single value, which falls short when you need a large, complicated value, or a lot of such values. Worse is the fact that all of the types are templated everywhere, so there's the fact that the digit type could be larger or smaller than the RNG's generated value, requiring more complicated code to fill the values.

Hence, why I'm leaning toward the first two mentioned approaches. Ideally, I'd like this RNG class to have the ability to be used with other classes, with ease. If possible, I'd like for the majority of the bit fiddling to be in the RNG's implementation, rather than the caller having to know too much about what will come out of it. Do you have any suggestions?

### #4L. Spiro  Crossbones+   -  Reputation: 8957

Like
0Likes
Like

Posted Yesterday, 11:33 PM

one that generates a random number modulo a specified number

Then it isn’t very random. Modulus is absolutely the wrong way to give a range of random numbers from 0 to N, as it favors lower numbers.

This explains why:
http://stackoverflow.com/questions/10984974/why-do-people-say-there-is-modulo-bias-when-using-a-random-number-generator

However do not use a while loop to generate an unbiased range of random numbers as he suggested; by definition that could be an infinite loop, or at least be severely (order of seconds) slow. Imagine that the range of rand() is 0-268,435,456 (which RAND_MAX is allowed to be by the standard) and you looped until it picked a number below 3.

The correct way is:

unsigned int Rand( unsigned int _uiMax ) {
double dRand = static_cast<double>(rand()) / static_cast<double>(RAND_MAX);
return static_cast<unsigned int>(dRand * (_uiMax - 1.0)); // Remove “ - 1.0” to be inclusive instead of exclusive.
}

L. Spiro

Edited by L. Spiro, Yesterday, 11:34 PM.

It is amazing how often people try to be unique, and yet they are always trying to make others be like them. - L. Spiro 2011
I spent most of my life learning the courage it takes to go out and get what I want. Now that I have it, I am not sure exactly what it is that I want. - L. Spiro 2013
I went to my local Subway once to find some guy yelling at the staff. When someone finally came to take my order and asked, “May I help you?”, I replied, “Yeah, I’ll have one asshole to go.”
L. Spiro Engine: http://lspiroengine.com
L. Spiro Engine Forums: http://lspiroengine.com/forums

### #5Ectara  Crossbones+   -  Reputation: 2080

Like
0Likes
Like

Posted Yesterday, 11:39 PM

Then it isn’t very random.

Ordinarily, I'd agree, but how do I cast a 2048 bit number to a double?

Edited by Ectara, Yesterday, 11:40 PM.

### #6Bacterius  Crossbones+   -  Reputation: 6648

Like
0Likes
Like

Posted Yesterday, 11:47 PM

Then it isn’t very random.

Ordinarily, I'd agree, but how do I cast a 2048 bit number to a double?

You don't. You basically do what BlueRaja suggested in the comments of that stackoverflow question, which is an improved form of rejection sampling which sort of does the floating-point division using integers. Btw, I didn't mention that because when you said "modulo" I thought you meant "generating integers in the range 0..n - 1" without referring to any specific generation algorithm. Obviously just taking the modulo tends to have a slight bias, unfortunately.

"The best comment is a deleted comment."

### #7Ectara  Crossbones+   -  Reputation: 2080

Like
0Likes
Like

Posted Today, 12:00 AM

I'm using this call mostly for the Rabin-Miller Primality Test; is a uniform distribution actually required for this task?

Moreover, I understand what skews the uniformity of a random number generator. I'm just looking to write an interface, here.

### #8Bacterius  Crossbones+   -  Reputation: 6648

Like
0Likes
Like

Posted Today, 12:40 AM

I'm using this call mostly for the Rabin-Miller Primality Test; is a uniform distribution actually required for this task?

Yes. If the base is not chosen uniformly then the worst-case bounds of the primality test no longer hold. Though as usual, in practice, a very small bias is unlikely to make a difference in the operation of the program, but if you can get it right, you should, because it will screw you over eventually (the bias actually gets quite measurable in some cases). But, yeah, let's get this thread back on its rails.

In my opinion, if you'd like to keep it as "pure" as possible then all you fundamentally need is a function that generates a random integer of n - uniformly distributed - digits (or bits - which unit you choose is a tradeoff between putting the digit/bit conversion stuff into the random engine or elsewhere in the code) for arbitrary n, which makes the integer uniformly distributed between 0 and D^n - 1 (or 2^n - 1, if bits). At that point your random engine is finished, and you can specialize a distribution class to take those integers and generate any distribution you'd like from them, such as a more specific range, floating-point values, even numbers only, etc, etc.. whatever.

So that kind of builds on top of the design of <random>, and in fact with some work it might be possible to implement your class such that it can be directly dropped into existing <random> classes so you can seamlessly leverage the functionality that's already there, but I don't know enough to tell you how to do that. And of course it's not the only approach, but it's the one I find the most logical from a design point of view (that you should try to make your integer class behave like an integer, such that you only need to implement a transitional function that generates the simplest uniform distribution possible from a bitstring, at which point all the bit-fiddling is over and you can use existing numerical methods to transform that distribution into anything you need).

I guess I could remove the most general function; it would have generated a number up to as large as allowed by the implementation. If one really wanted this behavior, they could generate a random number with a bit count of either (digit_bits * max_digits) or 2^size_type_bits - 1, whichever is less, ignoring the fact that it'd potentially fail to allocate. The other two have an upper bound defined by either a number that is the divisor, or a number of bits.

Yes, I think you should remove that function. Arbitrary precision arithmetic suggests there is no upper bound (besides available memory) and conceptually it doesn't make much sense to speak of generating a random number on an unbounded interval. The n-digit/bit version I mentioned previously is general enough.

(btw: have you considered using the Baillie-PSW primality test? it's a bit of the unsung hero but tends to be much more efficient than Miller-Rabin computationally speaking from a practical perspective, though it is somewhat of a conjecture mathematically speaking - anyway, just throwing it out there)

"The best comment is a deleted comment."

PARTNERS