CODEWITHSUNDEEP
algorithmnumbers
Narendra Modi
Narendra Modi

Reputation: 861

Comparing a Multiplication

I am having an Array A and B , we multiply all elements of array A and let this value called MulA , similary we do for B call this value MulB.

Now we want to compare these value which one is greater, Can we do without actually multiplying the elements, since value is of order 10^10 and array length is upto 10^6 we cannot store our result?

Upvotes: 0

Views: 69

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58339

To avoid large products, you can compare the sum of the logs: sum(log a for a in A) to sum(log b for b in B). That's because (a1*a2*a3*...*an) = exp(log(a1)+log(a2)+...+log(an)), and exp is an increasing function.

This will introduce some numerical error (since log is not exactly computable), but it'll work well enough in practice unless the products are very close to each other.

Note, this works both when the product is huge, and also when the product is tiny (for example if the elements were probabilities).

Upvotes: 3

Kaidul
Kaidul

Reputation: 15885

Use 64 bit integer (long long in C++) which can hold upto 9 x 10^18 (2^63 - 1). And no, there is no way to compare two lists multiplications without multiplying them (modular arithmetic rules for multiplication won't work here).

since value is of order 10^10 and array length is upto 10^6 we cannot store our result?

In worst case, the multiplied value will be 10^(10^7) which can't fit in any data-type. So you need to use Big Integer here which does everything in string form under the hood.

If you need a simple Big Integer implementation in C++, I can provide one. Thanks.

Upvotes: 0

Related Questions