Calculating modulus for larger numbers in python

Question

My code works fine with small number but when i do it with large numbers it gives running error

n = int(input().strip())
a=[]
for a_i in range(n): 
  a,n,m = [int(a_temp) for a_temp in input().strip().split(' ')]

  #n = test cases
  #a is a number 
  # n is no of times a will repeat itself (for example a=12 ,n =2 so y=1212.)
  #m is divisor

  y=[a]*n
  #print(y)

  s = map(str, y)   # ['1','2','3']
  s = ''.join(s)          # '123'
  s = int(s)
  #print(s)

  mod=s%m
  print(mod)

INPUT:

2  
12 2 17  
523 3 11

OUTPUT:

5
6

For input like :

2
366 457429086499 164868357
764 438211694736 385254849

It gives error:

Traceback (most recent call last):
  File "C:/Users/LENOVO/AppData/Local/Programs/Python/Python35-32/try123.py", line 11, in <module>
    y=[a]*n
OverflowError: cannot fit 'int' into an index-sized integer

How to fix this?

Have a look at this: http://stackoverflow.com/questions/538551/handling-very-large-numbers-in-python — ppasler, Dec 28 '16 at 14:13
If `[366]*457429086499` was possible it would have 457,429,086,499 entries and would require over a terabyte to store. Do you *really* want to do that? — John Coleman, Dec 28 '16 at 14:16
yes for test cases having larger numbers like that i have to perform the modulus operation. Is there any other way of doing that ? I mean any other syntax to use in place of y=[a]*n. — Pygirl, Dec 28 '16 at 14:20
What are you trying to do? What output do you expect for `366 457429086499 164868357` ? I can't imagine that the only way to get that output is by creating a ridiculously large list. — John Coleman, Dec 28 '16 at 14:23
I think that you need to do some mathematical analysis. It is unlikely that you have enough RAM to hold an integer with 1,372,287,259,497 (nearly 1.4 trillion) digits. Instead, you need to find a pattern involving the sequence 366, 366366, 366366366, ... and determine where you are in that pattern after 457429086499 steps. — John Coleman, Dec 28 '16 at 14:29
python has built-in LongInts but i don't know how to use it . — Pygirl, Dec 28 '16 at 14:32

score 1 · Accepted Answer · edited May 23 '17 at 12:24

1

There is no naïve solution to the problem that works for large numbers. You need to use some clever algebra and/or number theory. 366, 366366, 366366366, ... are partial sums of a geometric series. There is a standard formula for summing them, but unfortunately it involves division which doesn't play nice with modular arithmetic. This answer to the question of how to compute them gives a clever recursive solution which is similar to standard approaches to modular exponentiation. Implementing this in Python and then calling it with the right arguments leads to:

def geom(a,k,n):
    """calculates (1 + a + a^2 + ... + a^(k-1)) mod n)"""
    if k <= 2:
        return sum(a**i for i in range(k)) % n
    else:
        m = k//2
        b = pow(a,2,n)
        g = ((1+a)*geom(b,m,n))%n
        return g if k%2 == 0 else (g + pow(a,k-1,n))%n

def f(a,m,n):
    """ returns aaaa...a (m times) modulo n"""
    k = len(str(a))
    r = pow(10,k,n)
    return (a*geom(r,m,n))%n

For example,

>>> f(366, 457429086499,164868357)
2013258

Which is calculated almost instantaneously.

edited May 23 '17 at 12:24

Community

1
1

answered Dec 28 '16 at 15:41

John Coleman

51,337
7
54
119

but cant we use any inbuilt function in python to handle larger no. i tried using type method but it doesn't work – Pygirl Dec 28 '16 at 15:46
A potentially useful observation is that e.g. 366366366 = 366 *(1001001). It is enough if you can find a pattern in numbers that look like `1001001 % n` (beginning and ending in 1 interspersed with equal-length blocks of 0). – John Coleman Dec 28 '16 at 16:06
@KritiSahu I am not quite sure what you mean by "I tried to use type method". The approach I gave works with arbitrarily large inputs. It is simply impossible to work with such large numbers without using things such as modular exponentiation. – John Coleman Dec 28 '16 at 16:12
type(sys.maxint+1) this one syntax – Pygirl Dec 28 '16 at 16:48
@KritiSahu Python3 uses arbitrarily large integers by default. You don't have to do anything with the type system. You do need an algorithm which allows you to compute a 7 digit number (2013258) without first computing a 1.4 trillion digit number. – John Coleman Dec 28 '16 at 16:58
@KritiSahu 366366...366 (457429086499 times) would take up over 500 gigabytes. Even a high-end consumer computer has less than 100 gigabytes of RAM. Unless you have a supercomputer, this number would exceed the capacity of your computer by 1 or 2 orders of magnitude. No amount of tweaking Python's type system will make it possible for you to directly represent this number (and, if you *do* have a supercomputer -- surely it would be better employed doing something like 3-D protein folding rather than running extremely inefficient algorithms). – John Coleman Dec 28 '16 at 17:27

Calculating modulus for larger numbers in python

1 Answers1