Ask Your Question

Uniform random choice of integer

asked 2018-02-03 12:28:10 -0500

Mark Bell gravatar image

I want to perform some statistical sampling and to do this I need to uniformly randomly choose an integer from [0, N) where $N \approx 10^{50}$. It appears that there are several plausible ways to do this in Sage:

1) randint(0, N-1)

However, the standard Python random library appears to have some non-uniformity, for example see this ticket.

2) import numpy; numpy.random.randint(0, N)

However, since N is so large, this raises

ValueError: high is out of bounds for int64

3) ZZ.random_element(0, N)

Do either of the issues that methods 1) and 2) suffer from apply to method 3)? That is, is 3) the correct way to integers uniformly at random?

edit retag flag offensive close merge delete

3 answers

Sort by ยป oldest newest most voted

answered 2018-02-03 15:18:39 -0500

dan_fulea gravatar image

Here is an other possibility:

sage: import random
sage: random.getrandbits(167)
sage: ZZ(_)
sage: len(str(_))

(Well, $51$ decimal digits will also occur... I hope this is not an issue in the further application.)

edit flag offensive delete link more

answered 2018-02-05 03:09:07 -0500

Emmanuel Charpentier gravatar image

Maybe, this :

sage: N=1e50
sage: L=2000
sage: foo=[Integer(t) for t in r.round(r.runif(L,0,N)).sage()]

would have better properties ?

edit flag offensive delete link more

answered 2018-02-03 13:11:16 -0500

tmonteil gravatar image

updated 2018-02-03 15:56:28 -0500

At least, the method is different since ZZ.random_element use random generation from gmp (or its fork mpir), so it should not show the same drawbacks (though i can not guarantee that there is no other issue) . It is moreover much faster than randint.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2018-02-03 12:28:10 -0500

Seen: 100 times

Last updated: Feb 05