Factorial function works in Python, returns 0 for Julia
Question: I define a factorial function as follows in Python:

    
    
    def fact(n):
        if n == 1:
            return n
        else:
            return n * fact(n-1)
    
    print(fact(100))
    

and as follows in Julia:

    
    
    function fact(n)
        if n == 1
            n
        else
            n * fact(n-1)
        end
    end
    
    println(fact(100))
    

The python program returns a very large number for the evaluation of 100 (as
expected). Julia returns 0. With a smaller number (like 10) they both work.

I have two questions:

  1. Why does Python handle this OK and Julia not.
  2. Why doesn't Julia throw an error and just print 0 instead?


Answer: Julia has separate fixed-size integer types, plus a BigInt type. The default
type is `Int64`, which is of course 64 bits.

Since 100! takes about 526 bits, it obviously overflows an `Int64`.

You can solve this problem by just doing `fact(BigInt(100))` (assuming you've
`require`d it), or of course you can do the conversion in the `fact` function.

* * *

Python used to be the same, once upon a time. It had separate types `int`,
which was 16 or 32 or 64 bits depending on your machine, and `long`, which was
arbitrary-length. If you ran your program on Python 1.5, it would either wrap
around just like Julia, or raise an exception. The solution would be to call
`fact(100L)`, or to do the conversion to `long` inside the `fact` function.

However, at some point in the 2.x series, Python tied the two types together,
so any `int` that overflows automatically becomes a `long`. And then, in 3.0,
it merged the two types entirely, so there is no separate `long` anymore.

* * *

So, why does Julia just overflow instead of raising an error?

The FAQ actually explains [Why does Julia use native machine integer
arithmetic](http://docs.julialang.org/en/latest/manual/faq/#why-does-julia-
use-native-machine-integer-arithmetic). Which includes the wraparound behavior
on overflow.

* * *

By "native machine arithmetic", people generally mean "what C does on almost
all 2s-complement machines". Especially in languages like Julia and Python
that were originally built on top of C, and stuck pretty close to the metal.
In the case of Julia, this is not just a "default", but an intentional choice.

In C (at least as it was at the time), it's actually up to the implementation
what happens if you overflow a signed integer type like `int64`… but on almost
any platform that natively uses 2's complement arithmetic (which is almost any
platform you'll see today), the exact same thing happens: it just truncates
everything above the top 64 bits, meaning you wrap around from positive to
negative. In fact, _unsigned_ integer types are _required_ to work this way in
C. (C, meanwhile, works this way because that's how most CPUs work.)

In C (_unlike_ most CPUs' machine languages), there is no way to detect that
you've gotten an overflow after the fact. So, if you want to raise an
`OverflowError`, you have to write some logic that detects that the
multiplication will overflow before doing it. And you have to run that logic
on every single multiplication. You may be able to optimize this for some
platforms by writing inline assembly code. Or you can cast to a larger type,
but (a) that tends to make your code slower, and (b) it doesn't work if you're
already using the largest type (which `int64` is on many platforms today).

In Python, making each multiplication up to 4x slower (usually less, but it
can be that high) is no big deal, because Python spends more time fetching the
bytecode and unboxing the integer objects than multiplying anyway. But Julia
is meant to be faster than that.

As John Myles White explains in [Computers are
Machines](http://www.johnmyleswhite.com/notebook/2013/01/03/computers-are-
machines/):

> In many ways, Julia sets itself apart from other new languages by its
> attempt to recover some of the power that was lost in the transition from C
> to languages like Python. But the transition comes with a substantial
> learning curve.

* * *

But there's another reason for this: overflowing signed arithmetic is actual
useful in many cases. Not nearly as many as overflowing _unsigned_ arithmetic
(which is why C has defined unsigned arithmetic to work that way since before
the first ANSI spec), but there are use cases.

And, even though you probably want type conversions more often than you want
rollover, it is a lot _easier_ to do the type conversions manually than the
rollover. If you've ever done it in Python, picking the operand for `%` and
getting the signs right is certainly easy to get wrong; casting to `BigInt` is
pretty hard to screw up.

* * *

And finally, in a strongly-typed language, like both Python and Julia, type
stability is important. One of the reasons Python 3 exists was that the old
`str` type magically converting to `unicode` caused problems. It's far less
common for your `int` type magically converting to `long` to cause problems,
but it can happen (e.g., when you're grabbing a value off the wire, or via a C
API, and expect to write the result out in the same format). Python's dev team
argued over this when doing the `int`/`long` unification, quoting
"practicality beats purity" and various other bits of the Zen, and ultimately
deciding that the old behavior caused more problems than the new behavior
would. Julia's designed made the opposite decision.

