Finding Modulus of multiplication of two very large number with a very large number

Question

In a programming exercise, I need to find out the modulus of a very large number like 2 raise to power 500000(maximum number in input), with 1000000007 as a part of other computation.

As I may have to find out many times, one way is I create an array of 5,00,000. but it will is blocking a huge amount of memory, so I want to know is there any better way to do this ?

score 5 · Answer 1 · answered Apr 03 '13 at 02:57

5

This is an excellent time to use the repeated squaring algorithm. You can compute x^y (mod modulus) as follows:

int repeatedSquaring(int x, int y, int modulus) {
    if (y == 0) return 1;
    int val = repeatedSquaring(x, y / 2);
    val = (val * val) % modulus;

    if (y % 2 == 1) {
        val = (val * x) % modulus;
    }

    return val;
}

This algorithm requires only O(log y) multiplications and moduli to compute. Moreover, each intermediary value is at most modulus², so if your modulus is not too large you can just use plain ints to do the computation.

Hope this helps!

answered Apr 03 '13 at 02:57

templatetypedef

362,284
104
897
1,065

3

You can also reduce the size of the exponent (to no more than the size of the modulus) using Euler's theorem. – cohoz Apr 03 '13 at 03:03
1

`int` is not guaranteed to be able to hold `1000000007` because it's only guaranteed to have 16 bits in it. 32 are guaranteed in `long`. – Alexey Frunze Apr 03 '13 at 03:08
@AlexeyFrunze- You're not even guaranteed that. The spec leaves the sizes of int and long unspecified, as long as sizeof(int) ≤ sizeof(long). – templatetypedef Apr 03 '13 at 03:34
@templatetypedef C specifies that minimum range of `int` as -32767 to 32767 - at least 16 bits to implement. A similar minimum range exist for `long` requiring at least 32 bits. – chux - Reinstate Monica Mar 18 '15 at 16:23
@chux Are you sure about that? Can you give a citation? I was always under the impression that all of this was implementation-defined. – templatetypedef Mar 18 '15 at 17:58
@templatetypedef C specs have had something like this for decades: the _minimum_ range: : "— minimum value for an object of type int INT_MIN -32767 // −(215 − 1)" and "maximum value for an object of type int INT_MAX +32767 // 215 − 1" C11dr §5.2.4.2.1 1. also " minimum value for an object of type long int LONG_MIN -2147483647 // −(231 − 1) ..." http://stackoverflow.com/questions/81656/where-do-i-find-the-current-c-or-c-standard-documents – chux - Reinstate Monica Mar 18 '15 at 18:59
@chux Wow, I didn't know that! I always assumed everything was implementation-specific. – templatetypedef Mar 18 '15 at 19:08
@templatetypedef Not _everything_ is implementation-specific. Note: In 2015, `int` as 16-bit is found amongst embedded processors, 64-bit `int` can be found in some graphics processors. `long` is at _least_ as wide as `int`, often 2x. Suggest reading the first part of the latest C spec. – chux - Reinstate Monica Mar 18 '15 at 19:14

score 0 · Answer 2 · answered Apr 03 '13 at 03:05

How about something simple like this?:

#include <stdio.h>

unsigned long PowMod(unsigned long p)
{
  unsigned long prod;

  if (p == 0)
    return 1;
  if (p == 1)
    return 2;

  prod = PowMod(p / 2);
  prod = (unsigned long long)prod * prod % 1000000007ULL;
  if (p % 2 != 0)
  {
    prod = prod * 2 % 1000000007ULL;
  }

  return prod;
}

int main(void)
{
  printf("%lu\n", PowMod(3));
  printf("%lu\n", PowMod(4));
  printf("%lu\n", PowMod(30));
  printf("%lu\n", PowMod(31));
  printf("%lu\n", PowMod(32));
  printf("%lu\n", PowMod(33));
  return 0;
}

Output (ideone):

Finding Modulus of multiplication of two very large number with a very large number

2 Answers2