CODEWITHSUNDEEP
c++c
user650521
user650521

Reputation: 583

Multiply large numbers in c

I have two integer x and y Let us say x= 10^5 and y = 10^8 Now I have to multiply the numbers and store them in a variable z. I need not have the exact value. z can have the answer modulo 100000009. How can I do this?

Thanks in advance

Upvotes: 2

Views: 873

Answers (3)

LeeNeverGup
LeeNeverGup

Reputation: 1114

You can use logarithms and exponents. Exponent is the function f(x)=e^x, where e is a mathmaticall constant equal to 2.71828182845... Logarithm (marked by ln) is the inverse of the exponent.

Since ln(a*b)=ln(a)+ln(b), a*b=e^(ln(a)+ln(b)).

remark:
the method was wןdely used before the computers.

Upvotes: 0

Alnitak
Alnitak

Reputation: 339965

In general you should be relying on the relationship:

(a * b) % n = (a % n) * (b % n) % n

In this particular case it doesn't help much because your a and b are both smaller than n, but for larger a or b this guarantees that the largest multiplication you need to handle is of the order of n^2 and not a * b.

On a 64-bit system your current value of n^2 would fit inside a long. If you anticipate larger values then you'll need an arbitrary precision math library like GMP.

Upvotes: 4

Rapptz
Rapptz

Reputation: 21317

#include <iostream>
#include <cmath>

int main() {
    typedef unsigned long long ull;
    ull x = std::pow(10,5);
    ull y = std::pow(10,8);
    ull z = (x*y) % 100000009;
    std::cout << z << std::endl;
}

Upvotes: 0

Related Questions