CODEWITHSUNDEEP
cdoublemultiplication
pikapika
pikapika

Reputation: 1

C - erroneous output after multiplication of large numbers

I'm implementing my own decrease-and-conquer method for an.

Here's the program:

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>

double dncpow(int a, int n)
{
    double p = 1.0;
    if(n != 0)
    {
        p = dncpow(a, n / 2);
        p = p * p;
        if(n % 2)
        {
            p = p * (double)a;
        }
    }
    return p;
}

int main()
{
    int a;
    int n;
    int a_upper = 10;
    int n_upper = 50;
    int times = 5;
    time_t t;
    srand(time(&t));
    for(int i = 0; i < times; ++i)
    {
        a = rand() % a_upper;
        n = rand() % n_upper;
        printf("a = %d, n = %d\n", a, n);
        printf("pow = %.0f\ndnc = %.0f\n\n", pow(a, n), dncpow(a, n));
    }
    return 0;
}

My code works for small values of a and n, but a mismatch in the output of pow() and dncpow() is observed for inputs such as:

a = 7, n = 39

pow = 909543680129861204865300750663680

dnc = 909543680129861348980488826519552

I'm pretty sure that the algorithm is correct, but dncpow() is giving me wrong answers. Can someone please help me rectify this? Thanks in advance!

Upvotes: 0

Views: 91

Answers (1)

user2371524
user2371524

Reputation:

Simple as that, these numbers are too large for what your computer can represent exactly in a single variable. With a floating point type, there's an exponent stored separately and therefore it's still possible to represent a number near the real number, dropping the lowest bits of the mantissa.

Regarding this comment:

I'm getting similar outputs upon replacing 'double' with 'long long'. The latter is supposed to be stored exactly, isn't it?

  • If you call a function taking double, it won't magically operate on long long instead. Your value is simply converted to double and you'll just get the same result.
  • Even with a function handling long long (which has 64 bits on nowadays' typical platforms), you can't deal with such large numbers. 64 bits aren't enough to store them. With an unsigned integer type, they will just "wrap around" to 0 on overflow. With a signed integer type, the behavior of overflow is undefined (but still somewhat likely a wrap around). So you'll get some number that has absolutely nothing to do with your expected result. That's arguably worse than the result with a floating point type, that's just not precise.

For exact calculations on large numbers, the only way is to store them in an array (typically of unsigned integers like uintmax_t) and implement all the arithmetics yourself. That's a nice exercise, and a lot of work, especially when performance is of interest (the "naive" arithmetic algorithms are typically very inefficient).

For some real-life program, you won't reinvent the wheel here, as there are libraries for handling large numbers. The arguably best known is libgmp. Read the manuals there and use it.

Upvotes: 2

Related Questions