Most of us know that the command random.randint(1,n) in Python (2.X.X) would generate a number in random (pseudo-random) between 1 and n. I am interested in knowing what is the upper limit for n ?
views:
299answers:
2
+5
A:
randint() works with long integers, so there is no upper limit:
>>> random.randint(1,123456789012345678901234567890)
113144971884331658209492153398L
sth
2010-04-08 03:43:26
@sth : I did see that, however how come that is possible ? .... how can an algorithmic structure (as is python) generate numbers unto infinity ?
Arkapravo
2010-04-08 04:04:52
@Arkapravo: by implementing arbitrary-precision integers
Eli Bendersky
2010-04-08 04:08:10
Although `randint()` may raise a RuntimeError of "Underlying random() generator does not supply enough bits to choose from a population range this large" on a machine with a small or no entropy pool. The code in random.py is pretty clever about getting it right.
msw
2010-04-08 04:27:37
@Eli Bendersky : Can you please elaborate ? .... I had read about the Mersenne Twister, but not arbitrary-precession integer !
Arkapravo
2010-04-08 04:29:51
@arkapravo, traditionally, ints needed to fit into 4 bytes, so they were limited to about 4.3 billion numbers, but if you don't place a memory constraint on storing the integer, and let it reside in 8, or 16, or 1000 bytes, you are limited only by the amount of memory you have.
Brendan Abel
2010-04-08 04:54:07
@007brendan : cool ! .... that sure makes sense !
Arkapravo
2010-04-08 05:24:03
+1
A:
No doubt you have a bounded amount of memory, and address space, on your machine; for example, for a good 64-bit machine, 64 GB of RAM [[about 2**36 bytes]] and a couple of TB of disk (usable as swap space for virtual memory) [[about 2**41 bytes]]. So, the "upper bound" of a Python long integer will be the largest one representable in the available memory -- a bit less than 256**(2**40) if you are in absolutely no hurry and can swap like crazy, a bit more than 256**(2*36) (with just a little swapping but not too much) in practical terms.
Unfortunately it would take quite a bit of time and space to represent these ridiculously humongous numbers in decimal, so, instead of showing them, let me check back with you -- why would you even care about such a ridiculous succession of digits as to constitute the "upper bound" you're inquiring about? I think it's more practical to put it this way: especially on a 64-bit machine with decent amounts of RAM and disk, upper bounds of long integers are way bigger than anything you'll ever compute. Technically, a mathematician would insist, they're not infinity, of course... but practically, they might as well be!-)
Alex Martelli
2010-04-08 05:24:29
@Alex Martelli : Many thanks, so you happen to know what happens in random structures of Java, C++ , Matlab ..... (they are surely unlike Python)
Arkapravo
2010-04-08 05:27:15
I think it's safe to assume that his concern was that random.randint might not accept arbitrary sized integers, rather than that arbitrary sized integers wouldn't support a high enough upper limit for his purposes.
jemfinch
2010-04-08 05:28:00
@jemfinch : Well, I had an opinion that an algorithmic pedagogy cannot generate integers at will, without an upper bound ! .... guess I was wrong !
Arkapravo
2010-04-08 06:19:18
@Arkapravo, I believe there are "unbounded integers" in the standard libraries of Java and Matlab, but I'm not sure about the implementation. For C++ you need third-party libraries such as GMP or MPIR -- they're _definitely_ implemented similarly to Python's.
Alex Martelli
2010-04-08 14:15:04
@Alex Martelli : I had read about the use of Mersenne Twister for generating random numbers in python, which has a period of 2**19937-1. This number, 2**19937-1 is in no ways an upper bound ? At least I hope so ! :)
Arkapravo
2010-04-10 05:02:37
@Arkapravo, it's THE bound on the Mersenne Twister, by design of the latter. As there seem to be about `10**80` atoms in the Universe, and the Universe seems to be about 14 billion years old (less than `10**18` seconds old), if you somehow parallelized the Twister so every atom in the Universe ran it ceaselessly since the Big Bang, at 1000 GHz (a trillion operations per second), we'd already be somewhere like `1/(10**6000)` of the way through it -- oh the horror, if we got a googol Universes we'd be less than `1/(10**5700)` way through! Surely there must be some _better_ one, right?
Alex Martelli
2010-04-10 05:16:56
@Arkapravo, if you wanted to represent `2**19937-1` as a Python (or any other language's) value, you'd need to buy many more bytes of memory than there are atoms in the Universe, even if you found a quantum-computing way to store a googol bytes per atom. No more problematic than a Turing Machine's "infinite tape", of course.
Alex Martelli
2010-04-10 05:27:50