calculating modulo of a^n faster than o(n) [duplicate]

Multi tool use
This question already has an answer here:
Raising a number to a huge exponent
2 answers
I need to calculate (a^n) mod b
. I used this java code but it's not fast enough when n
is too large.
for (long i = 0; i < n; i++) {
ans = (ans * a) % b;
}
As you can see in above code, n
is a long
number so this algorithm is not fast enough. Do you suggest any faster algorithm?
It may seems like this problem but a little different: Fast way to calculate n! mod m where m is prime?
java algorithm data-structures
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
marked as duplicate by Jim Mischel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 27 '18 at 18:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
add a comment |
This question already has an answer here:
Raising a number to a huge exponent
2 answers
I need to calculate (a^n) mod b
. I used this java code but it's not fast enough when n
is too large.
for (long i = 0; i < n; i++) {
ans = (ans * a) % b;
}
As you can see in above code, n
is a long
number so this algorithm is not fast enough. Do you suggest any faster algorithm?
It may seems like this problem but a little different: Fast way to calculate n! mod m where m is prime?
java algorithm data-structures
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
marked as duplicate by Jim Mischel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 27 '18 at 18:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46
add a comment |
This question already has an answer here:
Raising a number to a huge exponent
2 answers
I need to calculate (a^n) mod b
. I used this java code but it's not fast enough when n
is too large.
for (long i = 0; i < n; i++) {
ans = (ans * a) % b;
}
As you can see in above code, n
is a long
number so this algorithm is not fast enough. Do you suggest any faster algorithm?
It may seems like this problem but a little different: Fast way to calculate n! mod m where m is prime?
java algorithm data-structures
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
This question already has an answer here:
Raising a number to a huge exponent
2 answers
I need to calculate (a^n) mod b
. I used this java code but it's not fast enough when n
is too large.
for (long i = 0; i < n; i++) {
ans = (ans * a) % b;
}
As you can see in above code, n
is a long
number so this algorithm is not fast enough. Do you suggest any faster algorithm?
It may seems like this problem but a little different: Fast way to calculate n! mod m where m is prime?
This question already has an answer here:
Raising a number to a huge exponent
2 answers
java algorithm data-structures
java algorithm data-structures
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Dec 27 '18 at 18:41
Jim Mischel
106k12128247
106k12128247
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Dec 27 '18 at 16:44
Nil Bah
234
234
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Nil Bah is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
marked as duplicate by Jim Mischel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 27 '18 at 18:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
marked as duplicate by Jim Mischel
StackExchange.ready(function() {
if (StackExchange.options.isMobile) return;
$('.dupe-hammer-message-hover:not(.hover-bound)').each(function() {
var $hover = $(this).addClass('hover-bound'),
$msg = $hover.siblings('.dupe-hammer-message');
$hover.hover(
function() {
$hover.showInfoMessage('', {
messageElement: $msg.clone().show(),
transient: false,
position: { my: 'bottom left', at: 'top center', offsetTop: -7 },
dismissable: false,
relativeToBody: true
});
},
function() {
StackExchange.helpers.removeMessages();
}
);
});
});
Dec 27 '18 at 18:42
This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46
add a comment |
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46
add a comment |
2 Answers
2
active
oldest
votes
Take advantage of property of modular arithmetic
(x × y) modulo b == ((x module b) × (y modulo b)) modulo b
By using above multiplication rule
(a^n) modulo b
= (a × a × a × a ... × a) modulo b
= ((a module b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b
Calculate the result by divide and conquer approach. The recurrence relation will be:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
Here is the C++ implementation:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (double) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
Time complexity is O(logn)
.
Here is my original answer. Hope it helps!
1
As the result ismod
and you want the precision, I would uselong
(orlong long
) rather thandouble
– Peter Lawrey
Dec 27 '18 at 17:08
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
add a comment |
You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.
For example:
n=4
then separate for 2 threads and each thread will the following:
int ans=1;
for(int i =0; i<n_thread;i++){
ans = ans*a;
}
Finally, when the threads finish you have to mul the result and then make the mod of b.
I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Take advantage of property of modular arithmetic
(x × y) modulo b == ((x module b) × (y modulo b)) modulo b
By using above multiplication rule
(a^n) modulo b
= (a × a × a × a ... × a) modulo b
= ((a module b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b
Calculate the result by divide and conquer approach. The recurrence relation will be:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
Here is the C++ implementation:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (double) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
Time complexity is O(logn)
.
Here is my original answer. Hope it helps!
1
As the result ismod
and you want the precision, I would uselong
(orlong long
) rather thandouble
– Peter Lawrey
Dec 27 '18 at 17:08
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
add a comment |
Take advantage of property of modular arithmetic
(x × y) modulo b == ((x module b) × (y modulo b)) modulo b
By using above multiplication rule
(a^n) modulo b
= (a × a × a × a ... × a) modulo b
= ((a module b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b
Calculate the result by divide and conquer approach. The recurrence relation will be:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
Here is the C++ implementation:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (double) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
Time complexity is O(logn)
.
Here is my original answer. Hope it helps!
1
As the result ismod
and you want the precision, I would uselong
(orlong long
) rather thandouble
– Peter Lawrey
Dec 27 '18 at 17:08
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
add a comment |
Take advantage of property of modular arithmetic
(x × y) modulo b == ((x module b) × (y modulo b)) modulo b
By using above multiplication rule
(a^n) modulo b
= (a × a × a × a ... × a) modulo b
= ((a module b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b
Calculate the result by divide and conquer approach. The recurrence relation will be:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
Here is the C++ implementation:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (double) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
Time complexity is O(logn)
.
Here is my original answer. Hope it helps!
Take advantage of property of modular arithmetic
(x × y) modulo b == ((x module b) × (y modulo b)) modulo b
By using above multiplication rule
(a^n) modulo b
= (a × a × a × a ... × a) modulo b
= ((a module b) × (a modulo b) × (a modulo b) ... × (a modulo b)) modulo b
Calculate the result by divide and conquer approach. The recurrence relation will be:
f(x, n) = 0 if n == 0
f(x, n) = (f(x, n / 2))^2 if n is even
f(x, n) = (f(x, n / 2))^2 * x if n is odd
Here is the C++ implementation:
int powerUtil(int base, int exp, int mod) {
if(exp == 0) return 1;
int ret = powerUtil(base, exp / 2, mod) % mod;
ret = 1LL * ret * ret % mod;
if(exp & 1) {
ret = 1LL * ret * base % mod;
}
return ret;
}
double power(int base, int exp, int mod) {
if(exp < 0) {
if(base == 0) return DBL_MAX; // undefined
return 1 / (double) powerUtil(base, -exp, mod);
}
return powerUtil(base, exp, mod);
}
Time complexity is O(logn)
.
Here is my original answer. Hope it helps!
edited Dec 27 '18 at 16:54
answered Dec 27 '18 at 16:48
Kaidul
9,487851108
9,487851108
1
As the result ismod
and you want the precision, I would uselong
(orlong long
) rather thandouble
– Peter Lawrey
Dec 27 '18 at 17:08
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
add a comment |
1
As the result ismod
and you want the precision, I would uselong
(orlong long
) rather thandouble
– Peter Lawrey
Dec 27 '18 at 17:08
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
1
1
As the result is
mod
and you want the precision, I would use long
(or long long
) rather than double
– Peter Lawrey
Dec 27 '18 at 17:08
As the result is
mod
and you want the precision, I would use long
(or long long
) rather than double
– Peter Lawrey
Dec 27 '18 at 17:08
1
1
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
@Kaidul Thank you. It worked!
– Nil Bah
Dec 27 '18 at 17:47
add a comment |
You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.
For example:
n=4
then separate for 2 threads and each thread will the following:
int ans=1;
for(int i =0; i<n_thread;i++){
ans = ans*a;
}
Finally, when the threads finish you have to mul the result and then make the mod of b.
I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.
add a comment |
You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.
For example:
n=4
then separate for 2 threads and each thread will the following:
int ans=1;
for(int i =0; i<n_thread;i++){
ans = ans*a;
}
Finally, when the threads finish you have to mul the result and then make the mod of b.
I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.
add a comment |
You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.
For example:
n=4
then separate for 2 threads and each thread will the following:
int ans=1;
for(int i =0; i<n_thread;i++){
ans = ans*a;
}
Finally, when the threads finish you have to mul the result and then make the mod of b.
I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.
You can use threads in order to divide the n. Then when you finalize to mul, you can mul the final result and then make the mod.
For example:
n=4
then separate for 2 threads and each thread will the following:
int ans=1;
for(int i =0; i<n_thread;i++){
ans = ans*a;
}
Finally, when the threads finish you have to mul the result and then make the mod of b.
I will not tell you how to use threads because you have to learn in your own, but if you have doubts about threads after searching and learning about them, then you can ask for help.
answered Dec 27 '18 at 16:58


Joan Jara Bosch
256
256
add a comment |
add a comment |
gT,Rpe TKsHV5vxEN5wUxYtMFFdx
Exponentiation by squaring
– MBo
Dec 27 '18 at 16:46