possible Python integer overflow error

Question

Below is my code that I'm trying to run to solve for a maximum prioritized product problem i.e. return a maximum value for a product of two numbers in a list. My issue is that the product that is being computed is incorrect when the numbers in the input list are large. I was of the opinion that there will be no integer overflow in error and resulting product will be automatically long but that is not happening evidently as my multiplication is returning some kind of garbage.

#"python2"
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 28 17:12:38 2016

@author: pvatsa
"""
import numpy as np

n = int(raw_input())
alist = np.random.randint(100000, size = n)
print alist
assert(len(alist) == n)
alist = sorted(alist)
print alist
max_no = max(alist)
second_largest_no = alist[n-2]
print max_no*second_largest_no
#print long(product)
#print type(product)

Well I might have ran pretty bad test case. In theory 100k*100k can overflow int32, so most you can do in this situation is specify dtype for numpy array alist = np.random.randint(100000, size = n, dtype = 'int64') — Tomasz Plaskota
– Tomasz Plaskota, Commented Jun 28, 2016 at 14:38

val · Accepted Answer · 2016-06-28 14:35:38Z

2

Using np.random.randint will create an array of 32 bits integers:

>>> alist = np.random.randint(100000, size = n)
>>> alist.dtype
dtype('int32')

Sorting it will preserve that type, creating a list of numpy.int32 objects instead of converting them back to Python (overflow-safe) integers:

>>> foo = sorted(alist)
>>> type(foo[-1])
<type 'numpy.int32'>

As such, the multiplication can overflow: you can solve it by either:

Casting your numbers back to Python numbers
Having an array of longs in the first place

The first case is simply a matter of converting values of interest:

>>> foo[-1] * foo[-2]
1386578402
>>> int(foo[-1]) * int(foo[-2])
9976512994L

The second can be done by calling randint with dtype=np.int64 (for numpy >= 1.11) or converting the array afterwards:

>>> llist = np.array(alist, dtype=np.int64)
>>> llist.sort()
>>> np.prod(llist[-2:])
9987503750

answered Jun 28, 2016 at 14:35

val

8,73935 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Pradyut Vatsa Over a year ago

Thanks @val. It makes complete sense. Also the minute I replaced numpy object creation with python raw_input function to generate the list a = [int(x) for x in raw_input().split()] , everything became overflow-safe and i got the desired result.

Collectives™ on Stack Overflow

possible Python integer overflow error

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related