0

I know there are tons of way of doing it and the best solution that i have found is the recursive method of Kupala(a youtuber, u can check it on youtube). Well, i could say that this way is 50 percent successful but the number that it can compute is still very far from 2 billion. I checked the result using this website: https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html I just wanna ask if there is any other way that can possibly reach this number? My programming language that i use is C++. Here is the code:

int emod(int a, int b, int c)
{
  if(b==1)
  {
      return remainder(a,c);
  }
  if(b%2==0)
  {
    return remainder((emod(a,b/2,c)*emod(a,b/2,c)),c);
  }else if(b%2!=0)
  {
    return remainder(fmod(a,c)*emod(a,b-1,c),c);
  }
}
nick1507
  • 9
  • 1
  • Use a larger data type maybe like `unsigned long`. – kiner_shah Dec 28 '21 at 10:27
  • Your code is accidentally exponential in running time. Try `x=emod(a, b/2, c); return remainder(x*x, c);` in the even case. – Paul Hankin Dec 28 '21 at 10:27
  • Just out of interest why does that have to be done recursively? Why can't you just compute it in a loop or something? – Dimfred Dec 28 '21 at 10:27
  • An `int` is not large enough to hold the value of (2^2000000000). Second, I bet there is a math "trick" that doesn't require any loops whatsoever. – PaulMcKenzie Dec 28 '21 at 10:29
  • If you have 32-bit int, you get integer overflow when you multiply if both numbers are larger than 65536. This means your code only really works for very small c. – Paul Hankin Dec 28 '21 at 10:29
  • 2
    @PaulMcKenzie The question is unclear, but he's asking to compute 2^2e9 modulo 2e9, for which an `int` _is_ sufficient. Although there'll be overflows during the computation as written. – Paul Hankin Dec 28 '21 at 10:30
  • 1
    The program is broken anyway, due to the usage of a floating point function `fmod`. Don't use floating point functions for programs that are supposed to be integer-based. – PaulMcKenzie Dec 28 '21 at 10:33
  • @nick1507 If you want to get your money's worth from stackoverflow :D it's worth looking at how clearly the person in the duped question asked their question (which is essentially the same question as yours), and how that resulted in good answers and less confusion in the comments. – Paul Hankin Dec 28 '21 at 10:36
  • Hint: Think in binary, bear in mind that multiplication is essentially a *convolution* operation. Note though that the Javascript in the linked page is a naive O(N) solution. The accepted answer in the duplicate is *much* better. – Bathsheba Dec 28 '21 at 10:36
  • factor out 2.0^9 into powers that fit into 64 bits : 50x50x50x50x40x8 and repeatedly apply the rule (2^n) mod m = (((2^i) mod m) * ((2^j)mod m)) mod m, where i+j = n. (https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/modular-exponentiation) – Pepijn Kramer Dec 28 '21 at 10:52
  • `unsigned int twotothepoweroftwobillionmodtwobillion() { return 1787109376; } ` – Stef Dec 28 '21 at 11:46

0 Answers0