 mersenneforum.org New way to Find (X^Y) % M
 Register FAQ Search Today's Posts Mark Forums Read  2004-05-08, 02:52 #1 maheshexp   May 2004 52 Posts New way to Find (X^Y) % M here i had developed a simple algorithm to calculate (X^Y)%M. i works well and faster than any string manipulated operations. //(x^y)%m long r1 = x % m; // loop upto y - 1, for x ^(y-1) for (long i = 0; i < y - 1; i++) { r1 = (r1 * x) % m; } hope this works... mahesh   2004-05-08, 03:14 #2 ColdFury   Aug 2002 26·5 Posts Actually that algorithm is quite trivial and also quite slow. With a Y of 32000, you'd need 32000 multiplications and modular reductions. Using a simple binary exponentiation algorithm, you'd only need on the order of 15.   2004-05-08, 05:10 #3 Cyclamen Persicum   Mar 2003 34 Posts I see what you want to say: Instead (x*x*x*x*x*x*...*x) mod y it is possible do not calculate the whole huge product of x, and one should take modulo after every mult, ((((x*x) mod y) *x) mod y) * x) mod y ... That is good guess. But are consequental mults a single way of powering ??? Do you know anything about really fast power algorithm (ordinary or modular) ?   2004-05-08, 13:55 #4 maheshexp   May 2004 52 Posts what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...   2004-05-08, 14:00 #5 maheshexp   May 2004 2510 Posts Cyclamen Persicum may i know what is consequental mults a single way of powering ???. since i am new to these type of jargons, and i will try to learn it   2004-05-08, 14:10 #6 maheshexp   May 2004 52 Posts ColdFury, what u say is right, i am trying to reduce it, but it's very simple rather than multiplying a huge number once , store in a datatype (if it supports ), and dividing it with a number is very huge process. i had benchmarked it with the available resources with java using the builtin functions, i will give u a sample here A 20 bit randomly generated prime number, i have a 2.66GHz system with 640MB ram. it shows the following benchmark ( simple benchmark ) Calculating 65101 ^ 47939 % 47939... ----------------------------- Calculating using My Algorithm... Time Taken using Loop:15 ms Result:17162 ----------------------------- Calculating using System Functions... Time Taken using Java Internals:4906 ms Result:17162   2004-05-08, 14:12 #7 maheshexp   May 2004 2510 Posts sorry it's not 20 bit random, its 16 bit random...since 20 bit random takes more time by system, and i need to waitfor it, but my algorithm takes Time Taken :63 ms Result:670543   2004-05-08, 14:28 #8 maheshexp   May 2004 52 Posts ColdFury, lets have an ex: 10^20 1: 10 mod 7 = 3 2: 10 mod 7 = 3 3 * 3 = 9 mod 7 = 2 == 100 mod 7 3: 10 mod 7 = 3 2 * 3 = 6 mod 7 = 6 == 1000 mod 7 4: 10 mod 7 = 3 6 * 3 = 18 mod 7 = 4 == 10000 mod 7 and so on....it may look simple for smaller exponents, but when u consider larger exponents , then u will see the difference. another benchmark with a sample number given by me Calculating 12321 ^ 934534 % 456456... ----------------------------- Calculating using My Algorithm... Time Taken using Loop:125 ms Result:258105... my system is calculating still   2004-05-08, 14:33 #9 maheshexp   May 2004 52 Posts finally my system got done Calculating 10 ^ 934534 % 456456... ----------------------------- Calculating using My Algorithm... Time Taken :78 ms Result:418408 ----------------------------- Calculating using System Functions... Time Taken using Java Internals:96016 ms Result:418408   2004-05-08, 15:52   #10
S80780

Jan 2003
far from M40

7D16 Posts Quote:
 Originally Posted by maheshexp what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...
Binary exponentiation goes like this:

e.g. 5^6%7

1. represent exponent in binary form: 610 = 1102
2. initialize the result as 1. -> 1
3. pass the binary representation of the exponent from left to right.
if the current bit is 1, multiply result by 5. -> 5
reduce result mod 7. -> 5
if you reached the rightmost bit, stop
otherwise square result. -> 25
reduce result mod 7. -> 4
process next bit.

Quote:
 Originally Posted by maheshexp may i know what is consequental mults a single way of powering ???
consequental mults means processing exponentiation by

r = 1;
while y > 0
{
y = y - 1;
r = r*x%m;
}
print r;

this was just a retoric question to let you think of other ways to do modular exponentiation, e.g. binary exponentiation.

Benjamin   2004-05-08, 18:43 #11 maheshexp   May 2004 52 Posts the binary algorithm is really faster   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Programming 18 2015-07-10 06:08 davar55 Math 2 2010-02-19 16:54 davar55 Puzzles 7 2009-07-02 19:46 davar55 Puzzles 25 2007-07-15 15:56 maheshexp Software 2 2004-05-08 03:16

All times are UTC. The time now is 23:54.

Sat May 15 23:54:18 UTC 2021 up 37 days, 18:35, 0 users, load averages: 1.59, 1.25, 1.35