Multiplication of 2 positive numbers in Julia gives a negative product

213 views Asked by At

In Julia 1.7.2 multiplication of 3037000691 and 3037000693 returns the negative product -9223370870501072753. The product I expected is 9223373203208478863.

function m(a::BigInt, b::BigInt)::BigInt
    a * b
end

This function gives the same negative result.

Any ideas on how to get the correct answer in Julia 1.7.2 to 3037000691 * 3037000693 ?

P.S.
I did run into this issue doing some math on (big) twin prime numbers.

2

There are 2 answers

4
Sash Sinha On BEST ANSWER

Try calling your function like this:

julia> m(BigInt(3037000691), BigInt(3037000693))
9223373203208478863

Or changing your function to any of the following:

# TL;DR: Use this it is the fastest.
function m1(a::Int64, b::Int64)::Int128
    Int128(a) * Int128(b)
end

function m2(a, b)::BigInt
    BigInt(a) * BigInt(b)
end

function m3(a::Int64, b::Int64)::BigInt
    BigInt(a) * BigInt(b)
end

Note you technically only need to cast either a or b, but I think that decreases readability.

Example usage:

julia> m1(3037000691, 3037000693)
9223373203208478863
julia> m2(3037000691, 3037000693)
9223373203208478863
julia> m3(3037000691, 3037000693)
9223373203208478863

In this case, you should use m1, which uses Int128s only since it is not possible to multiply two Int64 values to overflow an Int128:

julia> m1(9223372036854775807, 9223372036854775807) # Max val for Int64 squared.
85070591730234615847396907784232501249

In general, not using BigInt's whenever possible and being explicit about the types in your functions will result in significant performance gains:

julia> using BenchmarkTools

julia> @benchmark m1(3037000691, 3037000693)
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max):  0.049 ns … 7.780 ns  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     0.060 ns             ┊ GC (median):    0.00%
 Time  (mean ± σ):   0.064 ns ± 0.078 ns  ┊ GC (mean ± σ):  0.00% ± 0.00%

   ▁          █         ▃▆▃         ▂                       ▁
  ▆█▆▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁███▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▄▆▄▁▁▁▁▁▁▁▁▁█ █
  0.049 ns    Histogram: log(frequency) by time      0.1 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

julia> @benchmark m2(3037000691, 3037000693)
BenchmarkTools.Trial: 10000 samples with 199 evaluations.
 Range (min … max):  413.317 ns …  2.404 ms  ┊ GC (min … max):  0.00% … 64.79%
 Time  (median):     507.080 ns              ┊ GC (median):     0.00%
 Time  (mean ± σ):     1.957 μs ± 42.299 μs  ┊ GC (mean ± σ):  26.95% ±  1.29%

  ▇▆█▇▆▅▅▄▄▃▂▂▁▂▁                                              ▂
  █████████████████▇█▇▆▆▆▅▆▄▄▆▄▅▅▁▄▄▅▄▄▁▃▄▄▄▄▃▃▁▄▁▄▃▃▄▄▁▃▄▁▄▄▄ █
  413 ns        Histogram: log(frequency) by time      2.39 μs <

 Memory estimate: 128 bytes, allocs estimate: 7.

julia> @benchmark m3(3037000691, 3037000693)
BenchmarkTools.Trial: 10000 samples with 199 evaluations.
 Range (min … max):  414.774 ns …  2.487 ms  ┊ GC (min … max):  0.00% … 64.53%
 Time  (median):     496.080 ns              ┊ GC (median):     0.00%
 Time  (mean ± σ):     1.895 μs ± 41.026 μs  ┊ GC (mean ± σ):  24.60% ±  1.20%

  ▄ ▂▁ ▂█▄                                                      
  █▄██▇████▇▇▇▄▃▃▃▃▃▃▃▃▃▃▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▂▁▂▂▁▂▂ ▃
  415 ns          Histogram: frequency by time         1.14 μs <

 Memory estimate: 128 bytes, allocs estimate: 7.
0
Przemyslaw Szufel On

It should be noted that your m function as defined in the question does not provide negative result (which would be very wrong given function's syntax).

julia> m(3037000691, 3037000693)
ERROR: MethodError: no method matching m(::Int64, ::Int64)
Stacktrace:
 [1] top-level scope
   @ REPL[3]:1

Julia does not do automatic casting from Int64 to BigInt. This in conclusion means that you have had m(::Int64, ::Int64) (or just m(::Any, ::Any)) defined and it was called for your parameter values.

[What to do is described in the other, accepted answer]