Decreasing while loop working time for gigantic numbers

Question

i = 1
d = 1
e = 20199
a = 10242248284272

while(True):
  print(i)
  if((i*e)%a == 1):
      d = i
      break
  i = i + 1

Numbers are given to represent lengths of them.

I have a piece of Python code which works for really huge numbers and I have to wait for a day maybe two. How can I decrease the time needed for the code to run?

You need to format your code properly. Its difficult to understand what it does at the moment. — quamrana, Oct 31 '17 at 16:51
This should run really fast, since it has syntax (indentation) errors. — Scott Hunter, Oct 31 '17 at 16:52
Possible duplicate of [How to multiply big numbers faster?](https://stackoverflow.com/questions/37404689/how-to-multiply-big-numbers-faster) — Nir Alfasi, Oct 31 '17 at 16:53
Maybe it would run faster if you didn't print every integer between `i` and what eventually gets assigned to `d`. — Scott Hunter, Oct 31 '17 at 16:55
Pretty sure you could just use a `for` loop here, which should be faster as well. — juanpa.arrivillaga, Oct 31 '17 at 17:03
Are you saying that this code in particular runs slowly, or are you looking for help speeding up code in general? If it is the latter we cannot help without a more concrete example. If it is the former, [see here](https://stackoverflow.com/questions/9009139/optimising-multiplication-modulo-a-small-prime) — bendl, Oct 31 '17 at 17:48
@bendl: So 10242248284272 would be considered a small prime? — Scott Hunter, Oct 31 '17 at 18:05
this problem is np-hard so to solve it faster than via exaustive search would prove p == np and you could be a millionaire — Joran Beasley, Oct 31 '17 at 18:08
@ScottHunter that depends on what you consider small, but if you read the page, some people address the problem in a general enough way that it could help. I didn't vote to close, I only pointed to somewhere that could help — bendl, Nov 01 '17 at 12:21

score 0 · Accepted Answer · answered Nov 01 '17 at 17:38

There are a variety of things you can do to speed this up; whether it will be enough is another matter.

Avoid printing things you don't have to.
Avoid multiplication. Instead of computing i*e each iteration, you could have a new variable, say i_e, which holds this value. Each time you increment i, you can add e to it.
The vast majority of your iterations aren't even close to satisfying (i*e)%a==1. If you used a larger increment for i, you could avoid testing most of them. Of course, you have to be careful not to overshoot.
Because you are doing modular arithmetic, you don't need to use the full value of i in your test (though you will still need to track it, for the output)
Combining the previous two points, you can avoid computing the modulus: If you know that a<=x<2*a, then x-a==1 is equivalent to x%a==1.

None of these may be enough to reduce the complexity of the problem, but might be enough to reduce the constant factor to speed things up enough for your purposes.

Decreasing while loop working time for gigantic numbers

1 Answers1