How can I avoid overflow in modular multiplication?

Question

I know that,

(a*b)%m = ((a%m)*(b%m))%m

But there is a possibility of overflow. For simplicity lets assume size of integer is 2 bits. If a = 2 (i.e. 10₂) and b = 2 (i.e. 10₂), m = 3 (i.e. 11₂), then a%m and b%m turn out to be 2 and after multiplication, answer is 4 (i.e. 100) which does not fit in integer size. Final answer will be 0 if 2-lsb's are considered from 4. But actual answer is 1.

What should I do to avoid this situation?

Designedly

Answer 1

If m-1 squared doesn't fit in your integer type, you need to perform long multiplication. For your two-bit example, that means breaking your two-bit numbers into pairs of one-bit numbers (a high bit and a low bit) and multiplying all four pairs (high by high, high by low, low by high, low by low) individually. You can then get the result mod m for each pair (noting the actual places they represent, i.e. fours, twos, or ones) and add the results mod m.

Earmark

Re: "You can then get the result mod m for each pair (noting the actual places they represent, i.e. fours, twos, or ones)": Is there a straightforward way to do that? If (say) I'm working with 16-bit integers, and I have 0x05F4 offset by one byte (i.e. effectively 0x05F400), how would compute the result of that mod 0x6C31? – Uredo

Mathematically, x<<n mod m is just x mod m times 1<<n mod m, so you just need to know the value of 1<<n for each shift n that's involved in your long multiplication. For the procedure I described, there's only one such n: 1 for the two-bit example, and likewise 8 if you were multiplying two 16-bit integers mod m. 1<<n mod m is a single constant you can pre-compute and hard-code. – Earmark

I'm not 100% sure right off that the last multiply I described there can't overflow, so you should check it. If it can, you might have to break down the computation further or find some trick to work around it. – Earmark

Re: "1<<n mod m is a single constant you can pre-compute and hard-code": I'm not sure why you say that. I see no indication that m is any more hardcoded than a or b. – Uredo

By the way -- I get the impression, both from your replies to my comment, and from your comment above to the OP ("If your actual computations are with 16-bit integers, why don't you just [...]"), that you are thinking that I am the OP? To clarify: I am not the OP. But I think (s)he asked an interesting question, and I think it would be worthwhile to fully flesh out a working answer. (Your original answer was a start on the problem, but was a bit handwavy about the most difficult parts. Your comments improve that significantly, but not completely.) – Uredo

Sorry, I was mistaken about that. Deleted the irrelevant comment from the question itself. Anyway, to compute 1<<n mod m if m isn't constant, you simply use the fact that 1<<n fits in your integer type (n is half the width) and compute it directly. That's the easy part. The potentially hard part is multiplying the result by x. – Earmark

Answer 2

many small processor C implementations can directly check the result of a math operation for overflow/underflow.

Another way is to use a receiving field that is twice the length of the underlying int size I.E. for an int size of 2, use a result field of 4 bytes. (perhaps by a long long int) or transfer both numbers to double fields and multiply them then convert back to int (however, some precision in the result (I.E. the least significant digit) may be inaccurate.

Another way is to use an appropriate function from the math.h library.

Another way is to use long multiplication using arrays: this was copied from http://www.cquestions.com/2010/08/multiplication-of-large-numbers-in-c.html

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000

char * multiply(char [],char[]);
int main(){
    char a[MAX];
    char b[MAX];
    char *c;
    int la,lb;
    int i;
    printf("Enter the first number : ");
    scanf("%s",a);
    printf("Enter the second number : ");
    scanf("%s",b);
    printf("Multiplication of two numbers : ");
    c = multiply(a,b);
    printf("%s",c);
    return 0;
}

char * multiply(char a[],char b[]){
    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la,lb;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    la=strlen(a)-1;
    lb=strlen(b)-1;

    for(i=0;i<=la;i++){
            a[i] = a[i] - 48;
    }

    for(i=0;i<=lb;i++){
            b[i] = b[i] - 48;
    }

    for(i=lb;i>=0;i--){
        r=0;
        for(j=la;j>=0;j--){
            temp[k++] = (b[i]*a[j] + r)%10;
            r = (b[i]*a[j]+r)/10;
        }
        temp[k++] = r;
        x++;
        for(y = 0;y<x;y++){
            temp[k++] = 0;
        }
   }

   k=0;
   r=0;
   for(i=0;i<la+lb+2;i++){
        sum =0;
        y=0;
        for(j=1;j<=lb+1;j++){
            if(i <= la+j){
                sum = sum + temp[y+i];
            }
            y += j + la + 1;
        }
        c[k++] = (sum+r) %10;
        r = (sum+r)/10;
   }
   c[k] = r;
   j=0;
   for(i=k-1;i>=0;i--){
      mul[j++]=c[i] + 48;
   }
   mul[j]='\0';
   return mul;

}

Sample output of above code:

Enter the first number: 55555555

Enter the second number: 3333333333

Multiplication of two numbers:

185185183314814815

Logic for multiplication of large numbers

As we know in c there are not any such data types which can store a very large numbers. For example we want to solve the expression:

55555555 * 3333333333

Result of above expression is very big number which beyond the range of even long int or long double. Then question is how to store such a big numbers in c?

Solution is very simple i.e. using array. Above program has used same logic that is we are using as usual logic to multiply two numbers except instead of storing the data in the normal variables we are storing into the array.

Oraleeoralia

Answer 3

/// (a * n) mod m
fn mod_mul(mut a: i32, mut n: i32, m: i32) -> i32 {
    while n % 2 == 0 {
        a = (a + a) % m;
        n /= 2;
    }
    if n == 1 {
        a
    } else {
        mod_mul_acc(a, (a + a) % m, n / 2, m)
    }
}

fn mod_mul_acc(mut r: i32, mut a: i32, mut n: i32, m: i32) -> i32 {
    loop {
        if n % 2 == 1 {
            r = (r + a) % m;
            if n == 1 {
                return r;
            }
        }
        n /= 2;
        a = (a + a) % m;
    }
}

Engrossment

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. – Verdure

This looks like Rust code, I think? The question has a C tag though – Pirali