A friend of mine gave an interesting puzzle:
Calculate (12345678901234567 ^ 76543210987654321) % 115292150460684697
How to solve this programmatically, without using big number libraries?
I'm sure a bit of number theory is involved, but I'm not sure which theorem to use :red
Horner's Rule
or, as i call it, Ling Long Kai Fang
http://www.masm32.com/board/index.php?topic=12363.msg100575#msg100575
not sure my version can handle that large of a base, though
you might try factoring the base
and - not sure what "% 115292150460684697" means - lol
Looks like C code, where % = Mod
It is, it is a standard calculation for RSA encryption (PGP et.al.), raising a number to a power, modulo another number.
in that case, the base is prime - no factoring, there :bg
Just Google for Modular Exponentiation. There are a number of interesting articles related to the use of "binary" exponentiation. The PDF file available from the U. of Wyoming at the bottom of the first page should give you a good background.
Apparently, the divide & conquer approach works.
#include <stdio.h>
typedef long long LL;
LL _mul(LL,LL,LL);
LL _pow(LL,LL,LL);
int main(){
printf("%lld\n", _pow(12345678901234567LL,76543210987654321LL,115292150460684697LL));
return 0;
}
LL _mul(LL a, LL b, LL m) {
LL c;
if (b == 0) return 0;
c = _mul(a, b/2, m);
c = (c + c) % m;
if (b % 2 == 1) c = (c + a) % m;
return c;
}
LL _pow(LL a, LL b, LL m) {
LL c;
if (b == 0) return 1;
c = _pow(a, b/2, m);
c = _mul(c, c, m);
if (b % 2 == 1) c = _mul(c, a, m);
return c;
}
The result is: 96556738226978975
How long did it take for it to come up with that answer? I punched it into python and it's taking it well over 5 minutes to do the job, and it's still going! :lol
Quote from: TmX on July 26, 2010, 03:36:34 AM
Apparently, the divide & conquer approach works.
It does, but it's very slow, ~2,590,000 cycles versus ~33700 for the GMP mpz_powm function.
And the GMP result is the same 96556738226978975.
Edit:
And part of the reason for the slowness is that _pow gets called a total of 57 times, and _mul a total of 4668 times. That still works out at an average of 548 cycles per call, and while that is in line with the counts I'm seeing for the functions without the recursive calls, it still seems high.
Quote from: Radio Ga Ga on July 26, 2010, 06:59:39 AM
How long did it take for it to come up with that answer? I punched it into python and it's taking it well over 5 minutes to do the job, and it's still going! :lol
Instantly, on my C2D 2 GHz notebook
Quote from: MichaelW on July 26, 2010, 07:07:51 AM
Quote from: TmX on July 26, 2010, 03:36:34 AM
Apparently, the divide & conquer approach works.
It does, but it's very slow, ~2,590,000 cycles versus ~33700 for the GMP mpz_powm function.
How did you measure the clock cycles?
I compiled with a Microsoft compiler and used these (http://www.masm32.com/board/index.php?topic=13100.0) macros.
Ah thank you.
This will come in handy later. :U