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

Multi tool use
Multi tool use












4















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?










share|improve this question









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 algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

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
















4















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?










share|improve this question









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 algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

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














4












4








4








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?










share|improve this question









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






share|improve this question









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.











share|improve this question









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.









share|improve this question




share|improve this question








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 algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

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 algorithm
Users with the  algorithm badge can single-handedly close algorithm questions as duplicates and reopen them as needed.

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


















  • 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












2 Answers
2






active

oldest

votes


















7














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!






share|improve this answer



















  • 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






  • 1




    @Kaidul Thank you. It worked!
    – Nil Bah
    Dec 27 '18 at 17:47



















-4














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.






share|improve this answer




























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    7














    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!






    share|improve this answer



















    • 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






    • 1




      @Kaidul Thank you. It worked!
      – Nil Bah
      Dec 27 '18 at 17:47
















    7














    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!






    share|improve this answer



















    • 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






    • 1




      @Kaidul Thank you. It worked!
      – Nil Bah
      Dec 27 '18 at 17:47














    7












    7








    7






    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!






    share|improve this answer














    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!







    share|improve this answer














    share|improve this answer



    share|improve this answer








    edited Dec 27 '18 at 16:54

























    answered Dec 27 '18 at 16:48









    Kaidul

    9,487851108




    9,487851108








    • 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






    • 1




      @Kaidul Thank you. It worked!
      – Nil Bah
      Dec 27 '18 at 17:47














    • 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






    • 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













    -4














    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.






    share|improve this answer


























      -4














      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.






      share|improve this answer
























        -4












        -4








        -4






        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.






        share|improve this answer












        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Dec 27 '18 at 16:58









        Joan Jara Bosch

        256




        256















            gT,Rpe TKsHV5vxEN5wUxYtMFFdx
            PPdfzAk,2fFg D9O4,mS9Hr7CSg0,IpnGOkNxYdG NDs18c2S m0b iVSvP Njr7TBMprj5TGXG

            Popular posts from this blog

            Monofisismo

            Angular Downloading a file using contenturl with Basic Authentication

            Olmecas