Understanding the use of BigInt

Question

I'm struggling to understand how to use BigInt correctly. It seems to me that one should use BigInt when Int64 or Int128 is not enough, and apparently BigInt uses arbitrary precision arithmetic (of which I have no knowledge of).

Let's say I want to compute the factorial of some big number, e.g. 30. I don't know how many bits is required to store factorial(30) but both

test = Int128
test = factorial(30)

and

test = BigInt
test = factorial(30)

produces -8764578968847253504 which is obviously incorrect.

According to the Julia lang documentation, it seems that the usual mathematical operators are defined for this type (BigInt), and the results are promoted to a BigInt. Therefore I fail to see what I'm doing wrong, I have obviously misunderstood something. Hoping some of you might have an explanation for me :)

PS: I'm running the 64-bit version of Windows 7 if that has anything to say

Answer 1

factorial will calculate a result with the same type as its argument, so

test = factorial(BigInt(30))  

Will work, will be using a BigInt throughout computation.

test = BigInt(factorial(30))

Won't work, will convert the already overflowed Int result into a BigInt.

test = BigInt(factorial(BigInt(30)))

Will work, but the outer BigInt is redundant, as the result is already a BigInt.

The code you wrote

test = BigInt
test = factorial(30)

is essentially meaningless. You said

According to the Julia lang documentation, it seems that the usual mathematical operators are defined for this type (BigInt), and the results are promoted to a BigInt.

so I'm guessing you thought this meant "the result should be a BigInt", but it doesn't. It assigns the type BigInt to a variable test, then calculates factorial on the Int literal 30. It then stores it in test, squashing the previous value, which was BigInt. Maybe check out the Types section of manual. Julia doesn't automatically promote Ints to BigInts on overflow - you need to start with a BigInt. This is for performance (and other) reasons.

Most operations are defined on BigInts - only some linear algebra operations (like eigenvalues) might not be. Just change your number into a BigInt once and it will propagate throughout the computation. Most people will never need BigInts - tend to only crop up in a research setting. Int (which is the same as the platform integer size, so Int64 on your computer), goes pretty big - and is fast.

Answer 2

Related question about arbitrary precision math. Note I have only spent two days experimenting with the Julia language. After viewing this posting I added the BigInt casting which got one more number printed out. I must be missing something as it still does not execute like it is using arbitrary precision for all the calculations that it needs to. I also had to add the try/catch as the ismersenneprime function throws an error if it is not a Merseene prime number. According to the documentation I thought it was supposed to return true or false.

# Perfect numbers are 2^(p-1)x(2^p-1) if 2^p-1 is Mersenne prime.
using Compat
using Primes

limit = 1000000

for p = 1:limit
  perfect = BigInt(2^(p-1))*(BigInt(2^p)-1)
  try 
    if ismersenneprime(BigInt(2^p)-1)
      println("$p $perfect")
    end
  catch e
#   println(e)
  end
end

2 6
3 28
5 496
7 8128
13 33550336
17 8589869056
19 137438691328
31 2305843008139952128
61 2658455991569831744654692615953842176

Answer 3

I want to prefix this answer with the assertion that I do not know anything about Julia, but reading the documentation at https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/#Arbitrary-Precision-Arithmetic-1 it can be seen that they use factorial(BigInt(40)), so the explicit cast seems to be required.

Try factorial(BigInt(30)) to see if that gives the expected result.

Also, from that page:

However, type promotion between the primitive types above and BigInt/BigFloat is not automatic and must be explicitly stated.

So I would try 3 things, to see what works:

test = factorial(BigInt(30))
test = BigInt(factorial(30))
test = BigInt(factorial(BigInt(30)))