Why 2 ^ 3 ^ 4 = 0 in Julia?

Question

I just read a post from Quora: http://www.quora.com/Is-Julia-ready-for-production-use

At the bottom, there's an answer said:

2 ^ 3 ^ 4 = 0

I tried it myself:

julia> 2 ^ 3 ^ 4
0

Personally I don't consider this a bug in the language. We can add parenthesis for clarity, both for Julia and for our human beings:

julia> (2 ^ 3) ^ 4
4096

So far so good; however, this doesn't work:

julia> 2 ^ (3 ^ 4)
0

Since I'm learning, I'd like to know, how Julia evaluate this expression to 0? What's the evaluation precedent?

julia> typeof(2 ^ 3 ^ 4)
Int64

Answer 1

I'm surprised I couldn't find a duplicate question about this on SO yet. I figure I'll answer this slightly differently than the FAQ in the manual since it's a common first question. Oops, I somehow missed: Factorial function works in Python, returns 0 for Julia

Imagine you've been taught addition and multiplication, but never learned any numbers higher than 99. As far as you're concerned, numbers bigger than that simply don't exist. So you learned to carry ones into the tens column, but you don't even know what you'd call the column you'd carry tens into. So you just drop them. As long as your numbers never get bigger than 99, everything will be just fine. Once you go over 99, you wrap back down to 0. So 99+3 ≡ 2 (mod 100). And 52*9 ≡ 68 (mod 100). Any time you do a multiplication with more than two factors of 10, your answer will be zero: 25*32 ≡ 0 (mod 100). Now, after you do each computation, someone could ask you "did you go over 99?" But that takes time to answer… time that could be spent computing your next math problem!

This is effectively how computers natively do arithmetic, except they do it in binary with 64 bits. You can see the individual bits with the bits function:

julia> bits(45)
"0000000000000000000000000000000000000000000000000000000000101101"

As we multiply it by 2, 101101 will shift to the left (just like multiplying by 10 in decimal):

julia> bits(45 * 2)
"0000000000000000000000000000000000000000000000000000000001011010"
julia> bits(45 * 2 * 2)
"0000000000000000000000000000000000000000000000000000000010110100"
julia> bits(45 * 2^58)
"1011010000000000000000000000000000000000000000000000000000000000"
julia> bits(45 * 2^60)
"1101000000000000000000000000000000000000000000000000000000000000"

… until it starts falling off the end. If you multiply more than 64 twos together, the answer will always zero (just like multiplying more than two tens together in the example above). We can ask the computer if it overflowed, but doing so by default for every single computation has some serious performance implications. So in Julia you have to be explicit. You can either ask Julia to check after a specific multiplication:

julia> Base.checked_mul(45, 2^60) # or checked_add for addition
ERROR: OverflowError()
 in checked_mul at int.jl:514

Or you can promote one of the arguments to a BigInt:

julia> bin(big(45) * 2^60)
"101101000000000000000000000000000000000000000000000000000000000000"

In your example, you can see that the answer is 1 followed by 81 zeros when you use big integer arithmetic:

julia> bin(big(2) ^ 3 ^ 4)
"1000000000000000000000000000000000000000000000000000000000000000000000000000000000"

For more details, see the FAQ: why does julia use native machine integer arithmetic?