CODEWITHSUNDEEP
javascriptalgorithmmathmodulo
A. Esposito
A. Esposito

Reputation: 43

Modulo operation on a very large number

How would you go about performing a modulo operation on a fairly large number where modular exponentiation approaches cannot be taken?

For example, take this prime number modulo operation:

6864797660130609714981900799081393217269435300143305409394463459185543183
3976560521225596406614545549772963113914808580371219879997166438125740282
91115057151 % 4

WolframAlpha tells me it's 3. That's great, but I'd like to write an algorithm so that my own calculator app can handle that.

I'm assuming that for such a large number I would store the number in an array, one element per digit.

Upvotes: 3

Views: 2349

Answers (2)

misztsu
misztsu

Reputation: 129

I don't have enough reputation to comment, but these two guys that say, that you can look only at last digits are wrong, take %7 for example - you always have to look at all digits.

As you probably know (a+b)%n = (a%n + b%n) % n and (a*b)%n = (a%n * b%n) % n Using that we can first calculate 1%n, 10%n, 100%n and so on, then multiply these values by digits you have in your number and at the end add it all together.

I wrote it in c++:

//assume we have number of length len in reversed order
//example: 123%9 -> n = 9, num[0] = 3, num[1] = 2; num[2] = 1, len = 3
int mod(int n, int num[], int len)
{
    int powersOf10modn = 1;
    int anwser = 0;
    for(int i = 0; i < len; i++)
    {
        anwser = (anwser + powersOf10modn * num[i]) % n;
        powersOf10modn = (powersOf10modn*10) % n;
    }
    return anwser;
}

Upvotes: 5

JSFnta
JSFnta

Reputation: 11

If you have a number like : xyz % n , you only need to do yz % n. You need n%10 + 1 last digits to make your operation with best performances.

Upvotes: -2

Related Questions