avoiding overflow while multiplying very large integer in c++

Question

The other day I was solving one multiplication programming problem in which multiplicand(a1,a2,..an) can be 1<= ai <= 10^9 . So my question is how to multiply those numbers so that they'll always remain in (long long) range in C++.

Should I use any kind of mod(like 10^9+7) but it's not mentioned in question whether to use it or not?

I used normal multiplication with/without mod 10^9+7 only to vain. Also tried my luck with Russian Peasant Multiplication with mod 10^9+7

long long mulmod(long long a, long long b)
{
    long long res = 0; // Initialize result
    a = a % mod;
    while (b > 0)
    {
        // If b is odd, add 'a' to result
        if (b % 2 == 1)
            res = (res + a) % mod;

        // Multiply 'a' with 2
        a = (a * 2) % mod;

        // Divide b by 2
        b /= 2;
    }

    // Return result
    return (res % mod);
}

still no accepted solution. :-(

Edit 1: ll to long long.

"still no accepted solution" - How if you tagged your question with the wrong language? — too honest for this site, Oct 13 '16 at 13:51
well, what would you LIKE it to do if it goes out of range? Given that it's UB for it to go out of range you should be avoiding that situation where you can anyway. — UKMonkey, Oct 13 '16 at 14:03
Instead of `a * 2` you need to perform an operation which won't overflow. I would say `a + a` with some modified `a` value. — Eugene Sh., Oct 13 '16 at 14:04
I didn't get the question. If you are multiplying two"large" integers and their product actually exceeds the type (int OR long), how can you avoid it? — MayurK, Oct 13 '16 at 14:05
@MayurK that's what i'm asking. Answer is overflowing for sure. then how'd u make it to fit it in long long range. — SevenDante, Oct 13 '16 at 14:07
"My number doesn't fit in a long long, how do I make it fit in a long long?" is the question I'm currently seeing ... I think you need to revisit what you want to ask. — UKMonkey, Oct 13 '16 at 14:09
Short answer - you don't. Long answer - you make a class, and keep the exponent as one variable, and some digits on another, and then implement all the operations for your new class. — UKMonkey, Oct 13 '16 at 14:14
You tagged as C until I edited. Next time use the correct tag from the start. — too honest for this site, Oct 13 '16 at 14:18

score 0 · Answer 1 · edited May 23 '17 at 12:06

0

The solution could be either

Using wider integers (128+), which has already been solved: representing 128 bit numbers in c
Using floating point real numbers, where you lose accuracy in exchange of flexibility.

edited May 23 '17 at 12:06

Community

1
1

answered Oct 13 '16 at 15:27

Jorge Bellon

2,901
15
25

avoiding overflow while multiplying very large integer in c++

1 Answers1