Modulo of a 100k-digit number

Question

For numbers n and m I need to evaluate n % m.

The catch is n can be as big as 10^100000, m maxes out at 10^18.

unsigned long long is about 2^64 (please correct me if I'm wrong) which won't do, then I thought I could read it in array of characters, but how to calculate remainder of character.

Is there any way to reduce that number to a smaller number so it could be transferred from char array to unsigned long long (like atol but for long long instead of long).

Also I think I would be needing a faster way to do %, because time limit is 0.1s

Any help is appreciated.

Answer 1

There are many tricks that you can do to make modular arithmetic easier. For example, suppose you want to know what 1234567890 mod 17 is, but you don't have a numeric type big enough to represent 1234567890. Well, what do we know about %, assuming all numbers are positive?

(a+b)%e == ((a%e)+(b%e))%e
(c*d)%e == ((c%e)*(d%e))%e

If you don't understand why these identities are true, go back to the definition of % and study them until you have this solid.

Now that we know that, we know that

1234567890 % 17 = (12345 * 100000 + 67890) % 17
                = ((((12345 % 17) * (100000 % 17)) % 17) + (67890 % 17)) % 17

And now you have only much smaller numbers. If those numbers are still too big, keep breaking them down until they're small enough.

I answered a very similar question on the Math StackExchange site; it might also be of help to you.

https://math.stackexchange.com/questions/91583/implementing-fermats-primality-test/91584#91584

Answer 2

Or alternatively, one could replicate what a 2nd grader would do in maths class to calculate the result and the remainder of a division:

• attempt to divide the first digit from the left
• put down the result to the bottom right (not important for our cause)
• calculate the remainder for that digit
• put the next digit right next to the previous remainder

... which is basically multiplying the remainder by 10 each time and adding the subsequent digit, until we use up all our digits. How you store the numbers that user inputs from standard input is up to you, and that should be it. Here's an example:

#include <stdio.h>

int main( ){
    unsigned long long number[100000] = { 0 };
    int length = 0;
    unsigned long long divident = 0;
    char temp = 0;

    puts( "first-operand % second-operand\n" );

first:

    printf( "first-operand: " );
    temp = getchar( );
    while ( temp != 10 ){
        if ( temp <= '9' && temp >= '0' && length < 100000 ) {
            number[length] = temp - '0';
            length++;
        }
        else {
            while ( length ) {
                length--;
                number[length] = 0;
            }
            fflush( stdin );
            puts( "Invalid input, again from the beginning..." );
            goto first;
        }
        temp = getchar( );
    }


second:

    printf( "second-operand: " );
    temp = getchar( );
    while ( temp != 10 ){
        if ( temp <= '9' && temp >= '0' ) divident = divident * 10 + temp - '0';
        else {
            divident = 0;
            fflush( stdin );
            puts( "Invalid input, again from the beginning..." );
            goto second;
        }
        temp = getchar( );
    }

    puts( "The result is..." );

    length--;
    for ( long i = 0; i < length; i++ ) {
        number[i + 1] += 10 * number[i] % divident;
    }
    printf( "%lli", number[length] % divident );

    fflush( stdin );
    getchar( );

    return 0;
}

I could not really test it for big numbers, since I may not be sure of the answer, or have the time to write down 100k digits... Sorry for an answer this late, I had been convinced to do something else.

Answer 3

Read all digits for n as char, and read m as long long.
Algorithm:
1. if ( strlen(n) < strlen(m) ) printf("%s", n);
2. else: if there are, get the first 17 digits (17 is max digits for long long in this case) and convert them to long long using function strtoull, example: number = strtoull(digits, tmp, 10)
3. do calculate: tmp_rest = number % m
4. convert tmp_rest to string using sprintf function, ex. sprintf(string_digits, "%lld", tmp_rest)
5. replace the first 17 digits with string_digits start from 17th place and go to the left.
6. repeat from 2. but take 17-strlen(string_digits) as start point to get another 17 digits. Repeat until there are enough digits (>=17).
7. do 2. and 3. for rest of digits ( 0 < strlen(digits) < 17 ) -> solution is tmp_rest ;)

see: http://bytes.com/topic/software-development/insights/793965-how-find-modulus-very-large-number