Algorithm

[D4rk$!d3]

a,b,c are long long int datatypes. How do I solve (a^b)%c in a really efficient manner and in the fastest possible way ?

[reqq456]

I don't know of which dimension you are speaker if you say very very big.

But haskell is fast in that one:

Code: [Select]

Prelude> mod (10240000^10240000) 560
400
(3.22 secs, 546365816 bytes)
If I add another 0 it takes much longer :/

Code: [Select]

Prelude> mod (102400000^102400000) 560
480
(44.51 secs, 5975936856 bytes)

[D4rk$!d3]

I don't know of which dimension you are speaker if you say very very big.

But haskell is fast in that one:

Code: [Select]

Prelude> mod (10240000^10240000) 560
400
(3.22 secs, 546365816 bytes)
If I add another 0 it takes much longer :/

Code: [Select]

Prelude> mod (102400000^102400000) 560
480
(44.51 secs, 5975936856 bytes)

Oops, Sorry I wanted the algorithm for the C++ language...! Haskell ? No Idea dude !

[D4rk$!d3]

Code: [Select]


int modExp(int b, int e, int m){int remainder;int x = 1;while (e != 0){remainder = e % 2;e= e/2;if (remainder == 1)x = (x * b) % m;b= (b * b) % m; // New base equal b^2 % m} return x;
}

[Deque]

Did you try to search it?
http://math.stackexchange.com/questions/26722/calculating-ab-mod-c

[HardCodedShadow]

Used this as an opportunuity to make m first C++ program, so don't judge me.
Had an algorithm idea, implementing the number's prime factors to cut the running time down the most possible.
Unfortunately my program doesn't work with large numbers, for this you would need to use a Bignum library, which I couldn't be bothered installing.

Here's the code:

Code: [Select]

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

vector<long> getPrimes(long n)
{
    vector<long> vec;
   
    double sqrt_of_n = sqrt(n);

    while (n % 2 == 0)
    {
        n = n / 2;
        vec.push_back(2);
    }

    for (int i = 3; i <= sqrt_of_n; i = i + 2)
    {
        while (n % i == 0)
        {
            vec.push_back(i);
            n = n / i;
        }
    }
   
    return vec;
}

vector<long> copy(vector<long> vec)
{
    vector<long> newVec;

    for (int i = 0; i < vec.size(); i++)
    {
        newVec.push_back(vec.at(i));
    }
   
    return newVec;
}


int main()
{
    long a = 1024;
    long b = 1024;
    int c = 560;
   
    if (a % c == 0)
    {
        cout << 0 << endl;
        return 0;
    }
   
    vector<long> a_factors = getPrimes(a);
    vector<long> c_factors = getPrimes(c);
   
   
    int max_missing = 0;
    int needed_pow = 0;
    bool contains_all = true;
    for (int i = 0; i < c_factors.size(); i++)
    {
        int count_c = 1;
        long fac = c_factors.at(i);
        while (i + 1 < c_factors.size() && c_factors.at(i + 1) == fac){
            i++;
            count_c++;
        }
       
       
        int count_a = 0;
        for (int j = 0; j < a_factors.size(); j++)
        {
            if (a_factors.at(j) == fac)
            {
                count_a++;
            }
        }
       
        if (count_a == 0)
        {
            contains_all = false;
            break;
        }
       
        if (count_c - count_a > max_missing)
        {
            max_missing = count_c - count_a;
            needed_pow = count_c / count_a;
            if (count_c % count_a != 0)
            {
                needed_pow++;
            }
        }
    }
   
    if (contains_all && needed_pow <= b)
    {
        cout << 0 << endl;
        return 0;
    }
    else
    {
        vector<long> period;
        unsigned long long int new_a = a;
        unsigned long long int new_b = b;
        while(new_b > 0)
        {
            long mod = new_a % c;
            if (period.size() > 0 && mod == period.at(0))
            {
                break;
            }
            else
            {
                period.push_back(mod);
            }

            if (period.size() <= 1)
            {
                break;
            }

            new_a = new_a * a;
            new_b = new_b - 1;
        }
        cout << period.at((b-1) % period.size()) << endl;
        return 0;
    }
   
    return 0;
}

Again, I've never used C++ before, so if you see any errors in it, don't hesitate to tell me.
Sorry for not commenting my code, I hope it's readable.