Error for 396^n

General Usage
,
1

Something weird is happening in Julia when using 396^8…
In fact 396^n with n < 8 works fine, with n =>8 gives you a large negative number…

1 Like
2

This is because Int64 type overflows in some calculations, leading to mathematically incorrect results (including negative numbers).
Julia chose to use Int64 and to overflow silently because of performance considerations.
Two ways to get around this problem are:

  1. choose an appropriate bigger datatype such as Int128 or BigInt.
  2. use safe operation at the cost of performance. Safe operations can be used with the help of SaferIntegers package.

For example:

julia> BigInt(396)^8
604729962940281716736

julia> Int128(396)^8
604729962940281716736

and

julia> using SaferIntegers

julia> SafeInt64(396)^8
ERROR: OverflowError: 396^8
11 Likes
3

And note that Julia is not alone in this behavior, for example in python you would get:

>>> import numpy as np
>>> np.power(396,np.arange(1,10))
array([                 396,               156816,             62099136,
                24591257856,        9738138110976,     3856302691946496,
        1527095866010812416, -4012591492133486592, -2566240545839251456])
3 Likes
4

You’ll find relevant documentation under “Overflow behavior”
https://docs.julialang.org/en/v1/manual/integers-and-floating-point-numbers/#Overflow-behavior

8 Likes
5

The power ^ operator is the one thing I would want to change in Julia, even power of 3 can be a problem, see linked issue. For a^b it’s rather unsafe, unless a and/or b are floating point numbers, or big integers, not even Int128 type is safe.

All math operators can overflow, even + (and * and -), except /, and this may come as a surprise, except to users of most languages, such as C and C++, i.e. fast languages.

julia> typemax(Int128)+1
-170141183460469231731687303715884105728

In some sense that IS a correct result, i.e. ALL operators (expect / since it divides with a Float64 result) return modular math results, and they are correct when defined that way, but unexpected definition for many or most users. And for power, I think maybe never a good definition, while ok when you do not actually overflow, as with all the other operators.

So why do I only want to change ^? Because the problem is more apparent there (it’s the one operator that is really dangerous, much more than the other), and with Int64 type (the default Int type on 64-platforms), +, -, are in practice not a worry, and * also rarely, though more often.

[If you divide by 2, you get the correct exact result at least half the time, but if you divide by e.g. 3, you never get the correct exact result, unless you use Rationals, and that is a problem for any language (except maybe Raku/Perl 6 that may default to rationals, or does it not?). And even the rationals need to be of the BigInt type to guard against overflow. So with math you are screwed in pretty much any language, unless you opt into non-defaults, take care. Why do I mention thi? Because correct math vs fast math is a trade-off in any language, even a trade-off between approximately correct and fast.]

2 Likes
6

And the answer to “why” in the Frequently Asked Questions · The Julia Language

https://docs.julialang.org/en/v1/manual/faq/#faq-integer-arithmetic

2 Likes
7

What you CAN do (without adding a package) is this and similar for all the operators except pow (in 1.10, it seems to be there already in 1.11, and can also be used in older Julia versions with Compat.jl, not yet, but hypothetically in a future version of it):

julia> Base.Checked.checked_mul(396, 8)
3168

help?> Base.Checked.checked_div(396, 8)
Base.checked_div(x, y)

Calculates div(x,y), checking for overflow errors where applicable.

The overflow protection may impose a perceptible performance penalty.

but there’s actual no extra penalty over div (and some other related) since I checked:

julia> @edit Base.Checked.checked_div(396, 8)

checked_div(x::T, y::T) where {T<:Integer} = div(x, y) # Base.div already checks

This is intriguing, because div(a, b) can’t overflow for any positive b (e.g. never if it’s an Unsigned type), and only in rare cases like produces an error, only for typemin I think:

julia> div(typemin(Int64), -1)
ERROR: DivideError: integer division error

I know there’s an issue about making ^ checked by default. I want such available for sure, as for other operators (maybe I overlooked it, and it’s already available as I thought), and I would rather argue for Float64 result (same as with division, and for the same reason), rather than checked by default, though that is also a valid choice.

The problem with checked by default is that, while ^ is most dangerous, you could argue for checked by default for all (or none), and it is a bit of an inconsistency to only check one operator. In general a^b implies division if b is negative, so that’s why I rather want Float64 result for more consistency.

FYI: Unrelated, or not, and looking up I found this I did NOT know of: Collections and Data Structures · The Julia Language

Base.checked_length(r)

Calculates length(r), but may check for overflow errors where applicable when […]

8

FYI: It’s been discussed to change this to check (but only for ^; for now), but it was closed recently, considered inconsistent for just one operator:

I’ve suggested starting work on Julia 2.0, and I still believe that should be done, maybe even just to change a few things such ^ behaviour, and that issue was also closed (for now, maybe time to reconsider that?), moved to a discussion:

9

Numpy uses machine integers. Python itself uses big integers

In [2]: [396 ** n for n in range(10)]
Out[2]: 
[
    1,
    396,
    156816,
    62099136,
    24591257856,
    9738138110976,
    3856302691946496,
    1527095866010812416,
    604729962940281716736,
    239473065324351559827456,
]
1 Like