0

I have an excessively big number (1500+) digits and I need to find 2 ** that number modulo 1_000_000_000 so I wrote this python:

n = 1
return_value = 2
while n < To_the_power_of:
    return_value *= 2
    return_value = return_value % 1_000_000_000 
    n += 1

This returns the correct value for smaller values, but takes too long for bigger values.

If the number is modulo 10 then you get this pattern which could be used.

2 ** 1 modulo 10 = 2
2 ** 2 modulo 10 = 4
2 ** 3 modulo 10 = 8
2 ** 4 modulo 10 = 6
2 ** 5 modulo 10 = 2
2 ** 6 modulo 10 = 4 
2 ** 7 modulo 10 = 8 
2 ** 8 modulo 10 = 6

I'm hoping that a similar pattern could be used to answer the original problem.

Prune
  • 76,765
  • 14
  • 60
  • 81
Krish
  • 1,044
  • 9
  • 20
  • 1
    Did you try using larger moduloes? i.e. mod 100, 1000, etc. which can be computed easily? – zdimension Oct 16 '18 at 22:13
  • Can any power of 2 modulo a power of 10 be 0 or an odd number? No. That should be a big clue. – stark Oct 16 '18 at 22:24
  • 1
    Your idea is good, why don't you use it: you are guaranteed that there will be a repeating pattern before the 10^9 th iteration... – Julien Oct 16 '18 at 22:39
  • Just out of curiosity: Have you tried `(2 ** the_big_number) % 1000000000`? – mkrieger1 Oct 16 '18 at 22:51
  • @mkrieger1 that's an even worse way, much slower, a lot more memory hungry and requires a bigint implementation. You need [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation) for this purpose. [Calculating pow(a,b) mod n](https://stackoverflow.com/q/8496182/995714), [How did Python implement `pow(a, b, c)`?](https://stackoverflow.com/q/5246856/995714) – phuclv Oct 17 '18 at 02:56

2 Answers2

3

You already know that the sequence will repeat. You found the cycle of 4 for mod 10; now, just find it for a billion:

mod_billion = set()
pow_2 = 2
billion = 10**9

while pow_2 not in mod_billion:
    mod_billion.add(pow_2)
    pow_2 *= 2
    if pow_2 > billion:
        pow_2 -= billion

print (pow_2, len(mod_billion))

Three seconds later, we get:

512 1562508

Thus, this sequence repeats every 1562508 items. To find your value for your given power:

cycle = 1562508
small_power = big_power % cycle
result = (2 ** small_power) % billion
Prune
  • 76,765
  • 14
  • 60
  • 81
0

Your code makes about 10 ** 1500 iterations, which is indeed insanely long. A useful general technique is exponentiation by squaring, which will give you the result in about 4500 iterations.

If you want to follow the path of the @Prune's answer, you should go along the lines of Fermat's Little Theorem, specifically the Euler's generalization. phi(1_000_000_000) is easy to compute, because 10 ** 9 = (2 ** 9) * (5 ** 9), the product of 2 powers of primes.

user58697
  • 7,808
  • 1
  • 14
  • 28