CODEWITHSUNDEEP
pythonalgorithmjupyter-notebook
kmrydlx
kmrydlx

Reputation: 91

Error when running stress test on large numbers (overflow encountered in long_scalars)

I am running a max pairwise product script using a fast algorith and a trivial one in a stress test in Jupyter Notebook. I get correct answers when the maximum numbers are limited to 10000 but when I get strange errors. For instance 97319 * 87247 is not -99143799. I also get the following warning: "RuntimeWarning: overflow encountered in long_scalars". Do you know how I could fix it? Is it because I'm using jupyter?

StressTest(10,10000) - OK

StressTest(10,100000)

[30389 11418 34445 51909 58968 91476 48414 93444]
Fast algorithm: 93444 * 91476 = -42051248
Wrong answer: trivial = 2031152760, algorithm = -42051248

def max_pairwise_product_trivial(numbers):
    n = len(numbers)
    max_product = 0
    for first in range(n):
        for second in range(first + 1, n):
            max_product = int((max(max_product,numbers[first] * numbers[second])))
    return max_product

# Fast algorithm, correct
def max_pairwise_product(numbers):
    n = len(numbers)
    index_1 = 0
    for i in range(1,n):
        if numbers[i] > numbers[index_1]:
            index_1 = i

    if index_1 == 0:
        index_2 = 1
    else:
        index_2 = 0
    
    for i in range(1,n):
        if numbers[i] > numbers[index_2] and i != index_1: # numbers[i] != numbers[index_1]
            index_2 = i
    result = int(numbers[index_1] * numbers[index_2])
    print('Fast algorithm: {} * {} = {}'.format(numbers[index_1], numbers[index_2],result))
    return result

def StressTest(N, M):
    while True:
        n = random.randint(2,N)
        A = np.arange(n)
        for i in range(n):
            A[i] = random.randint(0,M)
        print(A)
        result1 = max_pairwise_product_trivial(A)
        result2 = max_pairwise_product(A)
        if result1 == result2: print('OK')
        else: 
            print('Wrong answer: trivial = {}, algorithm = {}'.format(result1,result2))
            break

Thanks

Upvotes: 0

Views: 111

Answers (1)

Jérôme Richard
Jérôme Richard

Reputation: 50836

The problem comes integer overflows. On your environment, Numpy integers are by default np.int32. It is probably because you have a 32-bit Python installed. Hopefully, almost all mainstream desktop machine use 64-bits processors, so you can run 64-bit programs on them. 32-bit programs are obsolete on these platforms (since at least decade). Thus, you can fix the problem just by using a 64-bit system and a 64-bit Python.

If you do not want to change your environment or you cannot, then you can just try to use np.arange(n, dtype=np.int64). This will probably not work. If so, you can use np.arange(n, dtype=int) which is very inefficient (because it prevent numpy from vectorizing efficiently your code), but works.

Upvotes: 1

Related Questions