Why does 2^100 give 0?

New to Julia
,
1

As the title says, if I input a large enough computation into the REPL, it outputs 0, no matter whether I store the value or not.

I understand that as I’m on a 64-bit system, my default type for integers is Int64. So, when I input 2^100, shouldn’t it either
a) upgrade it to Int128
or
b) overflow, and then modulo to give me the value 2^100-2^63+1?

Moreover, BigInt(2^100) also returns 0, but when I check the type of that 0, it indeed is BigInt.

My sincerest apologies for such a dumb question, but I’m kinda stuck, and I think I’m misunderstanding some key concept, hence I ask for help.

Thank You
Warm Regards

2 Likes
2

Great question, thanks for asking.

I think this section on integer arithmetic answers your question better than I could.

Appending Edit: Alan Edelman recently gave a lecture on floating point arithmetic. Hope it helps!

4 Likes
3

Try BigInt(2)^100

Otherwise you’re just doing BigInt(0)

6 Likes
4

Powers of 2 are (generally) implemented as a bitshift

julia> 2^62 |> bitstring
"0100000000000000000000000000000000000000000000000000000000000000"

julia> 2^63 |> bitstring
"1000000000000000000000000000000000000000000000000000000000000000"

julia> 2^64 |> bitstring
"0000000000000000000000000000000000000000000000000000000000000000"

Once you’re past 64 you’re just multiplying 0. BigInt can handle it (note that BigInt isn’t the same as Int128, it’s arbitrary size.)

julia> big(2)^64
18446744073709551616

julia> Int128(2)^64
18446744073709551616

julia> Int128(2)^128
0

julia> big(2)^128
340282366920938463463374607431768211456
9 Likes
5

It does give you a modulo and that is the zero you see. I’m not sure why you expect 2^100-2^63+1 but it’s quite clear that that number can’t possibly be represented in 64 bits as it’s larger than 2^99.

2 Likes
6

My apologies, I forgot the constant in my head. I was expecting 2^{100}(\text{mod } 2^{63}-1) \text{ i.e. } 2^{100} -K2^{63}+K.

Which is still grossly incorrect, but my reasoning was that everytime I get to 2^{64}-1, it’ll zero out.

But of course, in reality, it’ll go to -2^{63}. Hence, our expectation should be 2^{100} \text{ mod } 2^{64}.

Thank You for the help. Sincerest apologies for such an error.

1 Like