Tonight I hated julia, REPL and overflows

New to Julia
61

The error is at a place where it isn’t even using rtype (it fails for both SometimesBigInt and my SBig types).

Here is the code I used to test:

using BenchmarkTools
using Strs

using Base: mul_with_overflow
import Base: //, promote_type, convert

struct SometimesBigInt <: Integer
value::Union{Int, Base.RefValue{BigInt}}
end

SometimesBigInt(x::BigInt) = SometimesBigInt(Ref(x))

function Base.show(io::IO, x::SometimesBigInt)
print(io, “SometimesBigInt(”, value(x), “)”)
end

function value(x::SometimesBigInt)::Union{Int, BigInt}
x.value
end

//(x::SometimesBigInt, y) = value(x)//y
//(x::SometimesBigInt, y::Integer) = value(x)//y

function Base.:(*)(x::SometimesBigInt, y::SometimesBigInt)
xv, yv = value(x), value(y)
if xv isa Int && yv isa Int
zv, overflowed = mul_with_overflow(xv, yv)
if overflowed
zv = big(xv) * big(yv)
end
else
zv = xv * yv
end
SometimesBigInt(zv)
end

convert(::Type{BigInt}, v::SometimesBigInt) = BigInt(value(v))

promote_type(SometimesBigInt, Int) = SometimesBigInt
promote_type(SometimesBigInt, BigInt) = BigInt

const b0 = big"0"

struct SBig <: Integer
v::Int
b::BigInt
end

value(x::SBig) = isint(x) ? x.v : x.b

//(x::SBig, y) = value(x)//y
//(x::SBig, y::Integer) = value(x)//y

fitint(x) = typemin(Int) <= x <= typemax(Int)
isint(x::SBig) = (x.b === b0)
SBig(x::Int) = SBig(x, b0)
SBig(x) = fitint(x) ? SBig(convert(Int, x)) : SBig(0, x)
SBig(x::BigInt) = fitint(x) ? SBig(x % Int, b0) : SBig(0, convert(BigInt, x))

convert(::Type{BigInt}, v::SBig) = isint(v) ? BigInt(v.v) : v.b
convert(::Type{SBig}, v::BigInt) = fitint(v)isint(v) ? BigInt(v.v) : v.b

promote_type(SBig, Int) = SBig
promote_type(SBig, BigInt) = BigInt

Base.show(io::IO, x::SBig) = print(io, “SBig(”, value(x), “)”)

function Base.:(*)(x::SBig, y::SBig)
if isint(x)
isint(y) ? SBig(widemul(x.v, y.v)) : SBig(0, x.v * y.b)
else
isint(y) ? SBig(0, x.b * y.v) : SBig(0, x.b * y.b)
end
end

function out(s, t)
m0 = minimum(t).time / 1000
md = median(t).time / 1000
pr"%-25s(s)min=%10.3f(m0) μs, median=%10.3f(md) μs\n"
m0
end

function bench(p, nums)
xs = rand(nums, 1000)
ys = rand(nums, 1000)

pr"\n\%d(p)% chance of overflow\n"
t1 = out("Int mul:", @benchmark $xs .* $ys)

bigxs = big.(xs)
bigys = big.(ys)
t2 = out("BigInt mul:", @benchmark $bigxs .* $bigys)
pr"\%8.3f(t2/t1)x BigInt/Int\n"
pr"\%8.3f(t1/t2)x Int/BigInt\n"

sbigxs = SometimesBigInt.(xs)
sbigys = SometimesBigInt.(ys)
t3 = out("SometimesBigInt mul:", @benchmark $sbigxs .* $sbigys)
pr"\%8.3f(t3/t1)x SBI/Int\n"
pr"\%8.3f(t1/t2)x Int/SBI\n"
pr"\%8.3f(t3/t2)x SBI/BigInt\n"
pr"\%8.3f(t2/t3)x BigInt/SBI\n"

xbigxs = SBig.(xs)
xbigys = SBig.(ys)
t4 = out("SBig mul:", @benchmark $xbigxs .* $xbigys)
pr"\%8.3f(t4/t1)x SBig/Int\n"
pr"\%8.3f(t1/t2)x Int/SBig\n"
pr"\%8.3f(t4/t2)x SBig/BigInt\n"
pr"\%8.3f(t2/t4)x BigInt/SBig\n"
pr"\%8.3f(t4/t3)x SBig/SometimesBigInt\n"
pr"\%8.3f(t3/t4)x SometimesBigInt/SBig\n"

nothing

end

bench(1, (1:9…, 10^10))
bench(0, (1:10…,))
bench(100, ((10^10 .+ (1:10))…,))

function test_hm(rtype,rank)
mr = [rtype(1) // (i + j) for i in 1:rank, j in 1:rank]
one(mr) == mr * inv(mr)
end

println(“test_hm(SometimesBigInt”)
@btime test_hm(SometimesBigInt, 45)

println(“test_hm(SBig”)
@btime test_hm(SBig, 45)

62

Dear Scott,
there were quite a few wrong things with your code:
a missing convert function, an error in the arguments of promote_type (I replaced with promote_rule
which is better), and the main thing is that // must build a Rational{SometimesBigInt} if you want rational operations to be protected from overflows.

You also need to define all the arithmetic for SometimesBigInts. I put “dummy” definitions for -, rem, div
just so one can build a Rational. Dummy since they don’t check for overflow!
I did not finish, but with a few more definitions you should be able to make the example run…

using BenchmarkTools
using Strs
using Statistics

using Base: mul_with_overflow
import Base: //, promote_type, convert

struct SometimesBigInt <: Integer
value::Union{Int, Base.RefValue{BigInt}}
end

SometimesBigInt(x::BigInt) = SometimesBigInt(Ref(x))

function Base.show(io::IO, x::SometimesBigInt)
print(io, "SometimesBigInt(", value(x), ")")
end

function value(x::SometimesBigInt)::Union{Int, BigInt}
x.value
end

Base.signbit(x::SometimesBigInt)=signbit(x.value)

//(x::SometimesBigInt, y) = Rational{SometimesBigInt}(x,1)//y
//(x::SometimesBigInt, y::Integer) = Rational{SometimesBigInt}(x,y)

function Base.:(*)(x::SometimesBigInt, y::SometimesBigInt)
  xv, yv = value(x), value(y)
  if xv isa Int && yv isa Int
    zv, overflowed = mul_with_overflow(xv, yv)
    if overflowed
    zv = big(xv) * big(yv)
    end
  else
    zv = xv * yv
  end
  SometimesBigInt(zv)
end

Base.:-(x::SometimesBigInt, y::SometimesBigInt)=x.value-y.value
Base.rem(x::SometimesBigInt, y::SometimesBigInt)=rem(x.value,y.value)
Base.div(x::SometimesBigInt, y::SometimesBigInt)=div(x.value,y.value)

convert(::Type{BigInt}, v::SometimesBigInt) = BigInt(value(v))
convert(::Type{SometimesBigInt}, a::Int)=SometimesBigInt(a)

Base.promote_rule(::Type{SometimesBigInt}, ::Type{Int}) = SometimesBigInt
Base.promote_rule(::Type{SometimesBigInt}, ::Type{BigInt}) = BigInt

const b0 = big"0"

struct SBig <: Integer
v::Int
b::BigInt
end

value(x::SBig) = isint(x) ? x.v : x.b

//(x::SBig, y) = value(x)//y
//(x::SBig, y::Integer) = value(x)//y

fitint(x) = typemin(Int) <= x <= typemax(Int)
isint(x::SBig) = (x.b === b0)
SBig(x::Int) = SBig(x, b0)
SBig(x) = fitint(x) ? SBig(convert(Int, x)) : SBig(0, x)
SBig(x::BigInt) = fitint(x) ? SBig(x % Int, b0) : SBig(0, convert(BigInt, x))

convert(::Type{BigInt}, v::SBig) = isint(v) ? BigInt(v.v) : v.b
convert(::Type{SBig}, v::BigInt) = fitint(v)isint(v) ? BigInt(v.v) : v.b

promote_type(SBig, Int) = SBig
promote_type(SBig, BigInt) = BigInt

Base.show(io::IO, x::SBig) = print(io, "SBig(", value(x), ")")

function Base.:(*)(x::SBig, y::SBig)
if isint(x)
isint(y) ? SBig(widemul(x.v, y.v)) : SBig(0, x.v * y.b)
else
isint(y) ? SBig(0, x.b * y.v) : SBig(0, x.b * y.b)
end
end

function out(s, t)
m0 = minimum(t).time / 1000
md = median(t).time / 1000
pr"%-25s(s)min=%10.3f(m0) μs, median=%10.3f(md) μs\n"
m0
end

function bench(p, nums)
xs = rand(nums, 1000)
ys = rand(nums, 1000)

pr"\n\%d(p)% chance of overflow\n"
t1 = out("Int mul:", @benchmark $xs .* $ys)

bigxs = big.(xs)
bigys = big.(ys)
t2 = out("BigInt mul:", @benchmark $bigxs .* $bigys)
pr"\%8.3f(t2/t1)x BigInt/Int\n"
pr"\%8.3f(t1/t2)x Int/BigInt\n"

sbigxs = SometimesBigInt.(xs)
sbigys = SometimesBigInt.(ys)
t3 = out("SometimesBigInt mul:", @benchmark $sbigxs .* $sbigys)
pr"\%8.3f(t3/t1)x SBI/Int\n"
pr"\%8.3f(t1/t2)x Int/SBI\n"
pr"\%8.3f(t3/t2)x SBI/BigInt\n"
pr"\%8.3f(t2/t3)x BigInt/SBI\n"

xbigxs = SBig.(xs)
xbigys = SBig.(ys)
t4 = out("SBig mul:", @benchmark $xbigxs .* $xbigys)
pr"\%8.3f(t4/t1)x SBig/Int\n"
pr"\%8.3f(t1/t2)x Int/SBig\n"
pr"\%8.3f(t4/t2)x SBig/BigInt\n"
pr"\%8.3f(t2/t4)x BigInt/SBig\n"
pr"\%8.3f(t4/t3)x SBig/SometimesBigInt\n"
pr"\%8.3f(t3/t4)x SometimesBigInt/SBig\n"

nothing

end

bench(1, (1:9..., 10^10))
bench(0, (1:10...,))
bench(100, ((10^10 .+ (1:10))...,))

function test_hm(rtype,rank)
mr = [rtype(1) // (i + j) for i in 1:rank, j in 1:rank]
one(mr) == mr * inv(mr)
end

println("test_hm(SometimesBigInt")
@btime test_hm(SometimesBigInt, 45)

println("test_hm(SBig")
@btime test_hm(SBig, 45)
63

I was just trying to quickly test that code snippet as you asked me to do, I didn’t have time to add all of the stuff (that wasn’t in the code you had posted either)

64

Also - you were the one who had promote_type, and I copied the code you gave exactly - so if there was an error, it was in that.

65

Sorry if I did not give the impression, but do I appreciate your code. That’s why I tried to debug it. Just realized that more work was required than I had time to do. I hope that someone more knowledgeable than us continues the work (this could be myself some months from now…). Anyway thanks a lot for your contribution to the discussion.

2 Likes