Why python isn't handling very large numbers in all areas?

Question

I am doing a puzzle where I have to deal with numbers of order 10^18. However, I find python isn't able to handle very large numbers in all areas.

To be specific, if we assign a = 1000000000000000000 (10^18) and do basic arithmetic calculations (+, -, /, *), its responding. However, its showing OverflowError when I use it in range()

>>> a = 1000000000000000000
>>> a/2
500000000000000000L
>>> a*2
2000000000000000000L
>>> a+a
2000000000000000000L
>>> a*a
1000000000000000000000000000000000000L
>>> range(a)

Traceback (most recent call last):
  File "<pyshell#5>", line 1, in <module>
    range(a)
OverflowError: range() result has too many items
>>> xrange(a)

Traceback (most recent call last):
  File "<pyshell#6>", line 1, in <module>
    xrange(a)
OverflowError: Python int too large to convert to C long

I used Python 2.7.

1. How can I handle such cases?, Whats the best way to deal with puzzles holding such numbers. (A tutorial/ book reference would be appreciated)
2. Why Python isn't able to handle it in range()/ xrange()

I would like to do it in python 2.7 using inbuild functions. Isn't that possible?

Answer 1

In Python 2.x, range and xrange are limited to working with C long and your large integers are just too big for that. This limitation is simply due to the implementation choices made for range and xrange.

In Python 3.x the limitation has been removed and you can perform range() with very large integers.

>>> range(2**128)
range(0, 340282366920938463463374607431768211456)

The official list of changes for Python 3 has this to say:

range() now behaves like xrange() used to behave, except it works with values of arbitrary size. The latter no longer exists.

---

In Python 2.x the range() function returned a list. Clearly there's no hope of allocating memory for all the elements for very large ranges. The xrange() function returns an xrange object. The documentation describes it as "an opaque sequence type which yields the same values as the corresponding list, without actually storing them all simultaneously". The documentation goes on to say this:

xrange() is intended to be simple and fast. Implementations may impose restrictions to achieve this. The C implementation of Python restricts all arguments to native C longs (“short” Python integers), and also requires that the number of elements fit in a native C long.

This explains the limitations in Python 2.x.

---

I'm not quite sure what you can usefully do with the new Python 3 support for very large ranges. For example, I would not recommend you try this:

2**128 in range(2**128)

That will run for a long time.

---

You indicate in the comments that you are writing code to count up to a large number. You can do this trivially in Python with code like this:

i = 0
while i<N:
    doSomething(i)
    i += 1

But you will discover that if N is a large number then this will take a very long time. There's not any getting around that for values of N of the order 2¹⁸ as per your question.

Answer 2

Your problem is that range() in Python 2.7 constructs an explicit list of every value in the range - you simply don't have enough resources to construct such a list.

Python 3 corrects this behaviour - and only calculates the values on demand... as if by a generator expression.

The Python 2 xrange() function isn't going to help you as it is constrained to register values... which was a compromise for Python 2 to avoid the huge overhead of range() for any numbers that are not trivially small.

One approach might be to define your own generator which iterates over arbitrary integers - something like:

def genrange(min,max,stride=1):
    val=min
    while val<max:
        yield val
        val+=stride

My suspicion, however, is that this is probably a mistake in the bigger scheme of things - as you're unlikely to have sufficient processing resources to iterate through every value in a 32 bit integer - let alone for an integer range larger than that of a (32bit) register. I suspect there's a better way to address your problem which doesn't depend upon a range in the first place.