Large random integers

[WhiteCube]

I recently had to do this to test some large numbers for primeness.

Let x be any 100 digit integer.

How would you select a random number, from 0 to x-1, with each possible value equally likely?

Spoiler: my solution

I can do exact integer arithmetic, but my floating point is limited to 14 significant figures.

string y = "1"
loop 200 times
  append 1 random digit to y
end loop
y = x * y
truncate last 200 digits of y
return y - x

 

[phillip1882]

some thoughts:
i think you want y to simply equal ""
loop only 100 times
and convert to integer
but you still need to define how you generate 0 and 1 randomly and equally likely

 

[WhiteCube]

I'm working in base 10.

For generating a random digit from 0 to 9, I just use the language's built-in random function.

Truncating could be a problem if y has leading zeros. That's what the initial 1 and final subtract is for.

If I used just 3 random digits, there's only 1000 random states, and if x were say 701440, there are many values from 0 to x-1 that will not be selected.

The more digits the better, I guessed that 200 would be good enough. Twice the length of x. There's always going to be a little bias if x doesn't divide the number of states exactly.

 

[phillip1882]

well if you're gonna use the built in function, why not simply do that at the start?
i assure you they're just as good.

 

[WhiteCube]

The built-in random function produces a float, from 0 to 1. Normally I'd just multiply that by x and round off. But when x is huge, that isn't going to work.

I'm implementing the Rabin-Miller algorithm, not bouncing a ball around.