-6

I got this function that calculates factorial given an integer number:

long iterFact(long number) {
    long factorial = 1;

    for (long i = 1; i <= number; i++)
        factorial *= i;

    return factorial;
}

But it returns a negative number when I pass for example 20 as a parameter, I thought it would be because the number gets too long, but I'm still getting a negative number as result even after changing everything from int to long.

Bruno Pereira
  • 121
  • 1
  • 1
  • 5
  • 3
    Integer overflow. Also, it's factorial not Fibonacci. – zch Jan 21 '17 at 19:45
  • Because factorial grows rapidly and breaks the integer limit. – Weather Vane Jan 21 '17 at 19:45
  • 1
    _"I thought it would be because the number gets too long, but I'm still getting a negative number as result even after changing everything from int to long"_ `long` isn't infinite either. Instead of guessing, examine each value and find out whether your types are big enough or not – Lightness Races in Orbit Jan 21 '17 at 19:49
  • Please look at the numbers. `2**63` is `9223372036854775808`. Now `19!` is `121645100408832000` (smaller) but `20!` is `2432902008176640000` (larger). Do you see the problem? – Weather Vane Jan 21 '17 at 19:49
  • @WeatherVane: I'm afraid you are mistaken: `2432902008176640000` is smaller than `9223372036854775808`, so it fits in `long long`. – chqrlie Jan 21 '17 at 19:53
  • @chqrlie indeed thank you. But OP said it breaks at `20!` which was the source of my confusion. 64-bit breaks at `21!` – Weather Vane Jan 21 '17 at 20:01

5 Answers5

3

You are not adding numbers, but instead multiplying them. Indeed you are not computing the Fibonacci sequence, but the factorials ;-)

Factorials grow very fast: 20! (2432902008176640000) does not fit in a long on your system (32 bits, probably Windows), so one of the multiplications causes an arithmetic overflow, which the C Standard explicitly describes as undefined behavior. On your system, the computation might be performed modulo 2^32 and the result could be a negative number, but this is not guaranteed by the Standard.

Switching to type unsigned long long, which is guaranteed to have at least 64 bits, will let you compute 20! but will fail soon after, for 21!. In fact 2432902008176640000 is slightly smaller than 2^63-1, so type long long would suffice too.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
0

I assume you mean factorials, not the fibonacci sequence?

On most modern systems, int and long are both 32 bits, which can represent numbers up to about 2 billion. 20 factorial is about 2 billion billion. Try using long long which is 64 bits.

hnau
  • 79
  • 5
0

That's an integer overflow ; since your variable is signed, and since the sign bit is the most significant one, at some point you overflow your variable. Actually, 20! is a huge number. You should try to declare your variable as unsigned long, and print it as such.

m.raynal
  • 2,983
  • 2
  • 21
  • 34
  • Randomly guessing is not a solution for a problem caused by randomly guessing. – Lightness Races in Orbit Jan 21 '17 at 19:52
  • This is **one** possible explanation. But as signed integer overflow invokes undefined behaviour, there are numerous other reasons. – too honest for this site Jan 21 '17 at 19:58
  • Sorry for the poor answer, I'll be more careful before answering questions in the future. And thanks for the precision, i wasn't conscious an overflow induced an undefined behavior, i thought the most significant bits were just getting ignored,, but the least ones remained coherent ; i ran few tests on my machine to observe, and yes, there's no apparent logic in the results. – m.raynal Jan 21 '17 at 21:35
0

If sizeof(long) is 4 bytes and LONG_MAX is 2^31 - 1 then there'll be integer overflow when you calculate 13!. Signed integer overflow is undefined behaviour. You can use a different data type, such as uintmax_t, which can hold bigger numbers but still wouldn't be enough for handling bigger factorials.

Have a look at GMP library.

Also: What is the simplest way of implementing bigint in C?

Community
  • 1
  • 1
P.P
  • 117,907
  • 20
  • 175
  • 238
0

this is overflow of signed type

int could be 4 bytes: -2 147 483 648 / 2 147 483 647

long could be 8 bytes: -9223372036854775808 / 9223372036854775807

int/long could be signed and unsigned

Andrii Rallo
  • 87
  • 1
  • 12