Big exponentiation


#1

Hi all.
I wanted to do something simple - calculate 2^122.

By default Julia returns 0 because of an overflow, so I decided to try using BigInt.

Intuitive solution - BigInt(2^122). Still returns 0 because I’m casting the BigInt after the calculation happened inside. It’s equivalent to x = 2^122; BigInt(x).

So after fiddling I found a solution.

2^(BigInt(122)) returns the correct answer 5316911983139663491615228241121378304

But I have no idea why it works.
Can someone explain to me?
And I wonder if using BigInts will always be troublesome like this…

Thanks!


#2

You could instead convert the base to BigInt: BigInt(2)^122


#4

The usual logic when a mathematical operation receives two values of different types is to first promote them to a common type then perform the operation, e.g. 1 + 1.0 will first promote to 1.0 + 1.0, then do floating point addition. The logic here is the same: 2^BigInt(122) gives the same result as BigInt(2)^BigInt(122), which has a BigInt-valued result.

(the actual methods which get called in this case are slightly different, since GMP doesn’t actually provide a method to take a BigInt to the power of a BigInt, but it gives the same result as if it did).


#5

Right — slightly more concretely, you can see that 2^BigInt(122) and 2^122 dispatch to different implementations:

julia> @which 2^122
^(x::T, p::T) where T<:Integer in Base at intfuncs.jl:220

julia> @which 2^big(122)
^(x::Integer, y::BigInt) in Base.GMP at gmp.jl:527

This is multiple dispatch in action. Julia picks which method to use based upon the types of the arguments you pass to functions. Now, the reason why we’ve chosen to give these different methods these behaviors is a different answer. :slight_smile:


#6

Thanks! It’s clear to me now.
Could be worth adding this as an example on the BigInt docs.
https://docs.julialang.org/en/stable/manual/integers-and-floating-point-numbers/#Arbitrary-Precision-Arithmetic-1

Or maybe it’s something too simple and I was the only one confused? :stuck_out_tongue:


#7

You are certainly not the first or last person to have found this confusing, and this could be an excellent opportunity for a pull request. Documentation improvements are generally well-received :slightly_smiling_face: