Correctness? Factorial implementation returning unexpected result

Hi there! First day trying out Julia… so far, love it…

Implemented two versions of a simple factorial function, and ran into an unexpected result:

function fact(n)
    if n == 0
        return 1
    else
        n * fact(n - 1)
    end
end

function fact2(n)
    foldl(*, range(1, n))
end

checked fact(5) with a return of 120… cool. That looks right. But then, when the input is around n=30 or so, I’m getting negative results, which is not what I’m expecting.

julia> fact(30)
-8764578968847253504

Both versions returning same erroneous values.

Expecting: 265252859812191058636308480000000, based on other implementation and a simple calculator check.

That kind of scares me. Now that I write this, I’m realizing there’s probably a BigNum issue going on here, and … yeah, haven’t looked through the documentation on that yet… sorry… but I suppose I’m assuming that the return would simply default to the correct value, or at least return an error. What’s the correct way about going about this sort of thing, so that I don’t return something and think it’s correct when it’s not?

https://docs.julialang.org/en/v1/manual/faq/#faq-integer-arithmetic-1

There are a lot of threads on this topic if you search for machine integers, overflow and even factorial.

4 Likes

See the above reply regarding machine arithmetic. Then try fact(big(30)).

Julia is basically doing what all other “big” languages except Python do here, so this shouldn’t be surprising.

As for what you should do, the simple answer is: use big integers.

These (and other options) are probably mentioned in the other threads @johnmyleswhite mentioned, but there’s modules like SaferIntegers, some inbuilt support in Base.Checked, etc.

In practice, since Julia is usually used where performance matters (and overflow checking is a performance killer), you might use these during development and local testing, but ultimately use normal overflowing types in production code with tests to make sure any edge cases are handled properly.

3 Likes