[Python-bugs-list] [ python-Bugs-812202 ] randint is always even

[SourceForge.net]

Bugs item #812202, was opened at 2003-09-24 23:52
Message generated for change (Settings changed) made by rhettinger
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=812202&group_id=5470

Category: Python Library
Group: Python 2.3
Status: Open
Resolution: None
Priority: 5
Submitted By: Ronald L. Rivest (ronrivest)
>Assigned to: Raymond Hettinger (rhettinger)
Summary: randint is always even

Initial Comment:
The result of 

    random.randint(2**64,2**65-1) 

is always even!



(I was trying to find some large prime numbers, and

was puzzled by the fact that none were turning

up.  Finally, I discovered that randint wasn't really

returning "random" integers as desired, but only

even ones.)



I'm not sure what the cause of the problem is, but

randint should work properly, even when the given

endpoints are large...



Thanks...



        Ron Rivest



----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-09-25 19:07

Message:
Logged In: YES 
user_id=31435

Ya, something like that indeed.  You might enjoy writing the 

core in C <wink>.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-09-25 12:10

Message:
Logged In: YES 
user_id=80475

If the range is too large, instead of raising an exception,

how about  

calling a _randbigint routine that builds up the random

selection using repeated calls to the underlying generator. 

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-09-25 10:23

Message:
Logged In: YES 
user_id=31435

No disagreement here.  I'd rather fix the code than the docs, 

and a fix can take two forms:  raise an exception if the full 

range of ints can't be delivered, or deliver the full range of 

ints.



If anyone wants to take this on, I think the latter ("do a right 

thing") may be much more practical than it used to be, given 

the new-in-2.3 Twister impelementation -- we can generate 

long pseudo-random bitstrings quickly now (at least at the C 

level), but couldn't before 2.3.

----------------------------------------------------------------------

Comment By: Ronald L. Rivest (ronrivest)
Date: 2003-09-25 09:56

Message:
Logged In: YES 
user_id=863876

If the code is not going to be fixed, then the

documentation should be updated.  I am well aware

of other approaches to generating large random numbers,

but was misled by the documentation Python provides.  The

documentation should make it clear when the code violates

its "contract" (i.e. doesn't generate all integers in the range).

I prefer the code being fixed best, but also feel that the code 

should raise an exception if it can't honor the contract implied 

in its documentation.

----------------------------------------------------------------------

Comment By: Tim Peters (tim_one)
Date: 2003-09-25 00:16

Message:
Logged In: YES 
user_id=31435

The cause is that randint takes a pseudo-random float (C 

double in [0, 1),), multiplies it by (hi-lo+1), then truncates 

and adds that to lo.  Since a double on your box almost 

certainly has only 53 bits of precision, and your multiplier 

effectively moves the radix point 64 bits "to the right", I 

expect the last 11 bits you see will always be 0.



Under Python 2.3, which uses the Mersenne Twister to 

generate random doubles, this does appear to be the case:



>>> from random import randint

>>> def f():

...     return randint(2**64, 2**65-1)

...

>>> hex(f())

'0x11EDD95B72CEF4000L'

>>> hex(f())

'0x1DD69BF4B39C65000L'

>>> hex(f())

'0x13328DC9C1C733800L'

>>> hex(f())

'0x1E65B47170C057800L'

>>>



Under earlier versions of Python, it may be even worse than 

that.



It takes a fundamentally different kind of algorithm to 

generate arbitrarily long random ints.  Here's a link to one 

such for Python:



http://www.faqts.com/knowledge_base/view.phtml/aid/4406



I doubt the implementation of randint() will change, since 

most people want fast-as-possible generation of mountains of 

small integers, and there's a tradeoff between catering to 

that and catering to extreme inputs.  The randint docs should 

change, though (I think randint() used to raise an exception 

when fed arguments as large as the ones you're using; I 

suspect, but don't know, that we lost the helpful exception 

as an unintended consequence of the long-term effort to 

eradicate the user-visible distinction between Python ints 

(machine C longs) and Python longs (unbounded integers)).



BTW, given what you're doing, you may want to install one of 

the Python wrappers for GNU GMP.  Python's unbounded-int 

arithmetic implementation is extremely portable and reliable, 

but buys those in part by not caring much about speed.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=812202&group_id=5470