Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Modulo of a 100k-digit number

Tags:

c

modulus

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.

like image 731
user314159265 Avatar asked Feb 18 '14 17:02

user314159265


People also ask

How do you find modulo of large numbers?

Given a big number 'num' represented as string and an integer x, find value of “num % x” or “num mod x”. Output is expected as an integer. y: rest of the digits except x.

Why does MOD 10 give the last digit?

Modular Arithmetic Finding the last digit of a number is the same as finding the remainder when this number is divided by 10. In general, the last digit of a power in base n is its remainder upon division by n. So, for decimal numbers, we compute mod 10 to find the last digit, mod 100 to find the last two digits, etc.


3 Answers

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

like image 182
Eric Lippert Avatar answered Oct 16 '22 11:10

Eric Lippert


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.

like image 21
Utkan Gezer Avatar answered Oct 16 '22 09:10

Utkan Gezer


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

like image 1
purplemind Avatar answered Oct 16 '22 09:10

purplemind