CODEWITHSUNDEEP
pythonperformancemathtime-complexity
Zaruya
Zaruya

Reputation: 81

Having problems making this program run faster for large inputs

def calculate(i,j,m,k,n):
    for v in range(1,n+1):
        ans = (i*k + j) % m
        k = ans
    return ans

The program represents a general formula where x = (i * k + j) % m where k is the value of the previous answer. In a sense, it's basically x1 = (i * x0 + j) % m, and x2 = (i * x1 + j) % m, and so forth. The problem I'm having is that it takes a long while to calculate large inputs.

With that in mind, I was thinking along the lines of using an arithmetic series formula such as: a + (n - 1) * d), but I'm unsure on how to implement it in a program such as this.

Upvotes: 0

Views: 107

Answers (1)

MvG
MvG

Reputation: 60858

x1 = (i * x0 + j)
x2 = (i * x1 + j) = i * i * x0 + i * j + j
x3 = i * i * i * x0 + i * i * j + i * j + j
xn = i^n * x0 + sum(i^t for t from 0 to n - 1) * j
   = i^n * x0 + (i^n - 1) / (i - 1) * j

Found the last line with Wolfram Alpha.

The formula is nice if m is a prime. In that case you can perform all the computations modulo that prime, including the division, to keep the numbers small. You'd just need to get exponentiation i^n fast. I suggest you look at https://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method and references therein. This should give you O(log(n)) time complexity, compared to the O(n) of your loop.

If m is not a prime, the division in the above formula is annoying. But you can do something similar to exponentiation by squaring to compute the sum, too. Observe

1 + i + i^2 + i^3 + i^4 + i^5 + i^6 + … + i^(2n+1) =
(1 + i) * (1 + i^2 + i^4 + i^6 + … + i^n)
1 + i + i^2 + i^3 + i^4 + i^5 + i^6 + … + i^(2n+2) =
1 + (i + i^2) * (1 + i^2 + i^4 + i^6 + … + i^n)

so you can half the number of summands in the right parenthesis at each step. Now there is no division, so you can perform modulo operations after each operation. You can thus define something like

def modpowsum(a, n, m):
  """(1 + a + a^2 + a^3 + ... + a^n) mod m"""
  if n == 0:
    return 1
  if n == 1:
    return (1 + a) % m
  if n % 2 == 1:
    return ((1 + a) * modpowsum((a * a) % m, (n - 1) // 2, m)) % m
  return (1 + ((a + a * a) % m) * modpowsum((a * a) % m, n // 2 - 1, m)) % m

The whole computation can be seen at https://ideone.com/Xh0Fuf running some random and some not-so-random test cases against your implementation.

Upvotes: 2

Related Questions