CODEWITHSUNDEEP
python
sparky2012
sparky2012

Reputation: 55

Python Program Cannot Handle Large Numbers

So I have written a program (see below) to run a series of test cases and for each case determine if X exists for A≡X^2(modM) using Euler's Criterion. It works fine for small test cases, such as when A = 0 and M = 2 or A = 4 and M = 7, but when I consider larger test cases, such as when A = 83715323 and M = 118299443, the program just hangs on line 15 (shown below). Why is this program hanging? Is it a limit of python? Should I perhaps just redo it in something like C++?

The Problem Line

if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:

The Whole Program

number_of_cases = int(raw_input())

A = []
M = []

for case in range(number_of_cases):
    A_M = raw_input().split()
    A.append(int(A_M[0]))
    M.append(int(A_M[1]))

for case in range(number_of_cases):

    solution_exists = 0

    if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:
        print ("YES")
        break        

    else:
        print("NO")

Upvotes: 2

Views: 594

Answers (2)

Alex Riley
Alex Riley

Reputation: 176810

The integer calculated by A[case]**((M[case] - 1)/2) - 1) can get very large very quickly. It will take a lot of time and memory to calculate this number using any language.

Instead, take advantage of Python's pow operator and its third argument, which allows for efficient modular exponentiation.

Try changing

if((A[case]**((M[case] - 1)/2) - 1) % M[case]) == 0:

to

if pow(A[case], (M[case] - 1)/2 - 1, M[case]) == 0:

The large number A[case]**((M[case] - 1)/2) - 1) is not calculated here: Python increments the power gradually and keeps track of the remainder modulo M[case] at each step.

Upvotes: 4

Wai Ha Lee
Wai Ha Lee

Reputation: 8805

You are performing modular exponentiation.

For that reason, you don't need to calculate A[case]**((M[case] - 1)/2) in one statement. This is likely what is causing your hang.

Use the fact that

x**(n) % m == {(x**(n-1) % m) * x} % m

i.e. you can calculate the remainder of x^n for arbitrarily large n without calculating x^n directly by multiplying then getting the remainder repeatedly.

Try breaking up the exponentiation (see the "Memory-efficient method" section of the wiki article) and seeing if it's still slow.

My bet is that it isn't.

Upvotes: 2

Related Questions