20040508, 02:52  #1 
May 2004
5^{2} 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 ^(y1) for (long i = 0; i < y  1; i++) { r1 = (r1 * x) % m; } hope this works... mahesh 
20040508, 03:14  #2 
Aug 2002
2^{6}·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. 
20040508, 05:10  #3 
Mar 2003
3^{4} 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) ? 
20040508, 13:55  #4 
May 2004
5^{2} Posts 
what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...

20040508, 14:00  #5 
May 2004
25_{10} 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 
20040508, 14:10  #6 
May 2004
5^{2} 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 
20040508, 14:12  #7 
May 2004
25_{10} 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 
20040508, 14:28  #8 
May 2004
5^{2} 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 
20040508, 14:33  #9 
May 2004
5^{2} 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 
20040508, 15:52  #10  
Jan 2003
far from M40
7D_{16} Posts 
Quote:
e.g. 5^6%7 1. represent exponent in binary form: 6_{10} = 110_{2} 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:
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 

20040508, 18:43  #11 
May 2004
5^{2} Posts 
the binary algorithm is really faster

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Where can I find a Reverse and Add program? I can't find any!  Stargate38  Programming  18  20150710 06:08 
Help Find a Sequence?  davar55  Math  2  20100219 16:54 
Find the Value  davar55  Puzzles  7  20090702 19:46 
Find the Value  davar55  Puzzles  25  20070715 15:56 
New way to Find (X^Y) % M  maheshexp  Software  2  20040508 03:16 