Ask Your Question
0

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
1

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

dan_fulea gravatar image

Here is an other possibility:

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

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

edit flag offensive delete link more
0

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
0

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

Stats

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

Seen: 82 times

Last updated: Feb 05