CODEWITHSUNDEEP
c++g++console-application
Jeidoz
Jeidoz

Reputation: 54

Calculation and data limits

I have a task:

On notebook in cell (standart grided notebook for math/numbers) painted rectangle with size NxM (intergers). How much different rectangles can contain this rectangle?

Max value for N and M == 10^9 (1 000 000 000)

If result >= (10^9 + 7) show: Result mod (10^9 + 7)

Example: Examples

I know formula:

M*(M+1) * N*(N+1) / 4

And realised this problem in C++:

#include <iostream>
#include <cmath>
#include <iomanip>
int main() 
{
    long double n, m;
    std::cin >> n >> m;
    long double n1 = (n*(n + 1) / 2);
    long double m1 = (m*(m + 1) / 2);
    long double count = std::fmod((n1 * m1), 1000000007);
    std::cout << std::fixed << std::setprecision(0) << count;
    return 0;
}

But when I wrote for test 1000000000 x 1000000000

My program displayed me 499881764, when Windows calclulator and other calculator displayed 441 =_=

What's wrong I made? I will be very grateful if someone can show code-example of correct solution.

Upvotes: 0

Views: 43

Answers (1)

Bathsheba
Bathsheba

Reputation: 234785

You're losing precision in the long double type: the fact that your observed output is a multiple of a power of 2 is a touchstone of this effect.

Since your're using Windows, my money is on long double being a 64 bit IEEE754 double precision floating point type (i.e. the same as a double on that platform), and that gives you 53 bits of precision.

You could switch to an arbitrary precision library, or Google "Schranges Algorithm" for a clever way of computing modulus for a product.

Upvotes: 1

Related Questions