I would not be tempted to use a while loop, experience says that "if it can go wrong, it will.... at the most inopportune time".

I also don't like reinventing the wheel.
[...]
It explains how they generate large random numbers 20 bits at a time.

The goal there is to generate a pseudorandom sequence that extracts true random from a pool of true random entropy. This isn't needed in the OP's case (at least, there was no mention of that).

Generating large random numbers 20 bits (it's bytes, by the way, so rather 160 bits, but that does not matter) or in fact any number of bits at a time is trivial. I would use 32 or 64 bits since fast quality PRNGs that output 32/64 bits at a time are readily available, but that's only an implementation detail. Using a 160 bit cryptographic hash works just fine, too (it is however considerably slower).

The point where the problem gets absolutely not trivial is if you need random numbers in a particular range which doesn't correspond to exactly some number of bits.

Say you have a PRNG that produces 8-bit random numbers and you need a 24-bit "big" random number (works the same for 24 bits as it does for 4096 bits). Simply run the generator 3 times, and write out 8 bits every time, no problem. Want only 21 bits? Or 18 bits? No problem. Use logical AND to mask out the bits that you don't want.

Now assume you don't want numbers to range from 0 to 16777215 or another 2n-1 value, but only from 0 to 16772083. Using 23 bits won't do since that would be 8383475 numbers short, but using 24 bits will give you 5132 numbers outside the allowed range.Unluckily, that number doesn't map quite so good to "bits".

What do you do now?

Simply generate random bytes or words (or whatever is appropriate, according to the max value generated by your PRNG) and copy the raw bits into the memory buffer where the arbitrary precision number (or 2048 bit number) lives.



No special treatment necessary other than choosing a quality PRNG.

This topic is quickly veering off course. I'm asking for the best way to use a PRNG with a templated output size to randomize a AP number class with templated digit size. The 2048 bits was an example to throw out the floating point conversion, please pay it no mind. I will eliminate bias later, that is a problem that is impossible to solve if I haven't yet begun to generate random numbers.

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.

I'm not sure that I follow. The standard random classes return a templated type, requiring significant legwork for anyone to actually make use of it unless they provide their own parameters for that particular use, essentially making their own RNG that can't be used elsewhere. I hope to alleviate this issue by having the RNG class do most of the work.

(btw: have you considered using the Baillie-PSW primality test?

Not yet, I'll look into it once this class is up and running again. Thank you for the suggestion.

Two ways I'm reading "arbitrary precision number", and perhaps a bit of clarification would help others to answer.

1- A known-at-call-time fixed precision. Arbitrary in the sense that you can pass in a desired precision, and get a number back that satisfies that precision.
"Arbitrary" in the polymorphic sense.

2- An unknown-at-call-time variable precision number. Arbitrary in the sense that it grows more digits if your expression requires more digits. This is the more conventional use of "arbitrary precision math" on computers.

If case 1, your answer is clear from above posters. You break it down to the task of generating 1 digit, which can in turn be broken down into the task of generating 1 bit, then repeat as necessary.

If case 2, you're hosed, since the probability of any particular number selected from the space of potentially infinite numbers having less than X digits is effectively zero, for really any fixed value of X. Your computer has fixed memory in which to store the generated number, thus X is defined, thus you're either screwed or you're going to bound your number in some way which renders it no longer "arbitrary-precision".

Two ways I'm reading "arbitrary precision number", and perhaps a bit of clarification would help others to answer.

use a PRNG with a templated output size to randomize a AP number class with templated digit size

So basically, it is exactly as expected, running a simple for(...) loop for the easy case. Still, that leaves the "not so easy" case which was described as "generates a random number modulo a specified number", so basically generating a random number with some upper limit that isn't incidentially a power of two.

And as clarified later:

I'm using this call mostly for the Rabin-Miller Primality Test

an unbiased distribution is needed (so... no modulo).

If case 2, you're hosed, since the probability of any particular number selected from the space of potentially infinite numbers having less than X digits is effectively zero, for really any fixed value of X. Your computer has fixed memory in which to store the generated number, thus X is defined, thus you're either screwed or you're going to bound your number in some way which renders it no longer "arbitrary-precision".

It grows, and there are functions that specify an upper bound. I'm not hosed in any way.

running a simple for(...) loop

No, not a simple for loop. Not only do the types not necessarily match, but who knows if all of the bits are used? For instance, rand() returns an int, often 32 bits, but RAND_MAX can be a 16 bit value, meaning that if you try to guess based on the size of the return type, you'll get garbage if you fail to take into account that not all of the bits are used.

Still, that leaves the "not so easy" case which was described as "generates a random number modulo a specified number", so basically generating a random number with some upper limit that isn't incidentially a power of two.

And as clarified later:

I'm using this call mostly for the Rabin-Miller Primality Test

an unbiased distribution is needed (so... no modulo).

I'm still trying to generate numbers, here. Can we please forget the modulus? I'm starting to become frustrated.

No, not a simple for loop. Not only do the types not necessarily match, but who knows if all of the bits are used? For instance, rand() returns an int, often 32 bits, but RAND_MAX can be a 16 bit value, meaning that if you try to guess based on the size of the return type, you'll get garbage if you fail to take into account that not all of the bits are used.

I fail to see your problem. Nobody said something about guessing. Simply use a random number generator with a known number of valid output bits. This isn't hard, these exist in many flavors (such as MT, to name one well-known generator, but a 64-bit xorshift which is like 3 lines of code would do just fine, too).

So your generator outputs, say, 32 bits, and you need a 1024 bit number? Initialize an int32_t pointer to the beginning of your AB number, and run a for() loop with 32 iterations, writing out one number every time and incrementing the pointer. Need a 2048 bit number? Well, run 64 iterations. Need a 2040 bit number? Run 63 iterations and fill the last 3 bytes either one-by-one, or something similar.

Why doesn't this work?

Simply use a random number generator with a known number of valid output bits.

Templated. I don't know what the RNG class will be, so I can't control it.

Technically the random generator should just return an endless stream of uniformly distributed bits, and not any particular word size.

However, it returns data in discrete words. I don't even know what data type to use to hold an endless stream of bits; at some point, I must use it piece by piece. Perhaps I am misunderstanding, can you show pseudocode?

My method has a signature like this:

template <typename digit_>
class BigNumber{
    template <class rng_ = ectara::Random>
    static BigNumber<digit_> genRandomNumber(sizeType bits, rng_ & rand);
};

There's a RNG object of some sort that gets passed in; I haven't decided on its interface. I am trying to figure it out, in the context of generating these digits. All the standard random classes provide is a single unsigned integer return value at a time; should I mandate that these RNG objects have a method that fills a buffer of bytes?