mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2004-05-08, 02:52   #1
maheshexp
 
May 2004

1916 Posts
Lightbulb 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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 03:14   #2
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

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.
ColdFury is offline   Reply With Quote
Old 2004-05-08, 05:10   #3
Cyclamen Persicum
 
Cyclamen Persicum's Avatar
 
Mar 2003

34 Posts
Default

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) ?
Cyclamen Persicum is offline   Reply With Quote
Old 2004-05-08, 13:55   #4
maheshexp
 
May 2004

52 Posts
Lightbulb

what is simple binary exponentiation algorithm, can u explain me that. since i am new to lot of algos...
maheshexp is offline   Reply With Quote
Old 2004-05-08, 14:00   #5
maheshexp
 
May 2004

318 Posts
Default

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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 14:10   #6
maheshexp
 
May 2004

52 Posts
Default

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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 14:12   #7
maheshexp
 
May 2004

52 Posts
Default

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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 14:28   #8
maheshexp
 
May 2004

52 Posts
Default

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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 14:33   #9
maheshexp
 
May 2004

318 Posts
Default

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
maheshexp is offline   Reply With Quote
Old 2004-05-08, 15:52   #10
S80780
 
Jan 2003
far from M40

53 Posts
Default

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
S80780 is offline   Reply With Quote
Old 2004-05-08, 18:43   #11
maheshexp
 
May 2004

1916 Posts
Default

the binary algorithm is really faster
maheshexp is offline   Reply With Quote
Reply

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 2015-07-10 06:08
Help Find a Sequence? davar55 Math 2 2010-02-19 16:54
Find the Value davar55 Puzzles 7 2009-07-02 19:46
Find the Value davar55 Puzzles 25 2007-07-15 15:56
New way to Find (X^Y) % M maheshexp Software 2 2004-05-08 03:16

All times are UTC. The time now is 04:05.

Tue Oct 27 04:05:47 UTC 2020 up 47 days, 1:16, 0 users, load averages: 2.15, 1.92, 1.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.