BigInt bit shift yields incorrect results

[NegaScout]

Hi,

When doing big"2" << <big_number> it yields 0. I am assuming it is because big"2"^<big_number> throws an error, but I have not yet tested this. Here is a reproducer on 1.11.3:

[xxx@fedora ~]$ julia
               _
   _       _ _(_)_     |  Documentation: https://docs.julialang.org
  (_)     | (_) (_)    |
   _ _   _| |_  __ _   |  Type "?" for help, "]?" for Pkg help.
  | | | | | | |/ _` |  |
  | | |_| | | | (_| |  |  Version 1.11.3 (2025-01-21)
 _/ |\__'_|_|_|\__'_|  |  Official https://julialang.org/ release
|__/                   |


julia> _q = big"338529080896108965767114525934749117223216740941376711175117801548757039464925265185456890196066591384483538988140720866125823957951605413309645322444478475882910613426157401827900611393402398255676835299789253650685614604706767318106611143888606425239677611402987117990498540999873668868860546995543503171780419583331612111661293341988510184240889590244574477120700917"
338529080896108965767114525934749117223216740941376711175117801548757039464925265185456890196066591384483538988140720866125823957951605413309645322444478475882910613426157401827900611393402398255676835299789253650685614604706767318106611143888606425239677611402987117990498540999873668868860546995543503171780419583331612111661293341988510184240889590244574477120700917

julia> big"2"<<_q
0

julia> big"2"<<5
64

julia> big"2"^_q
ERROR: OverflowError: exponent 338529080896108965767114525934749117223216740941376711175117801548757039464925265185456890196066591384483538988140720866125823957951605413309645322444478475882910613426157401827900611393402398255676835299789253650685614604706767318106611143888606425239677611402987117990498540999873668868860546995543503171780419583331612111661293341988510184240889590244574477120700917 is too large and computation will overflow
Stacktrace:
 [1] (::Base.GMP.var"#throw1#3")(y::BigInt)
   @ Base.GMP ./gmp.jl:629
 [2] bigint_pow(x::BigInt, y::BigInt)
   @ Base.GMP ./gmp.jl:642
 [3] ^(x::BigInt, y::BigInt)
   @ Base.GMP ./gmp.jl:647
 [4] top-level scope
   @ REPL[5]:1

[NegaScout]

I think it might do something with convert

julia> Base.GMP.MPZ.mul_2exp(big"2", _q)
ERROR: InexactError: UInt64(338529080896108965767114525934749117223216740941376711175117801548757039464925265185456890196066591384483538988140720866125823957951605413309645322444478475882910613426157401827900611393402398255676835299789253650685614604706767318106611143888606425239677611402987117990498540999873668868860546995543503171780419583331612111661293341988510184240889590244574477120700917)
Stacktrace:
 [1] Type
   @ ./gmp.jl:368 [inlined]
 [2] convert
   @ ./number.jl:7 [inlined]
 [3] cconvert
   @ ./essentials.jl:687 [inlined]
 [4] mul_2exp!(x::BigInt, a::BigInt, b::BigInt)
   @ Base.GMP.MPZ ./gmp.jl:179
 [5] mul_2exp(a::BigInt, b::BigInt)
   @ Base.GMP.MPZ ./gmp.jl:180
 [6] top-level scope
   @ REPL[10]:1

julia> _t = big"0"
0

julia> Base.GMP.MPZ.mul_2exp!(_t, big"2", _q)
ERROR: InexactError: UInt64(338529080896108965767114525934749117223216740941376711175117801548757039464925265185456890196066591384483538988140720866125823957951605413309645322444478475882910613426157401827900611393402398255676835299789253650685614604706767318106611143888606425239677611402987117990498540999873668868860546995543503171780419583331612111661293341988510184240889590244574477120700917)
Stacktrace:
 [1] Type
   @ ./gmp.jl:368 [inlined]
 [2] convert
   @ ./number.jl:7 [inlined]
 [3] cconvert
   @ ./essentials.jl:687 [inlined]
 [4] mul_2exp!(x::BigInt, a::BigInt, b::BigInt)
   @ Base.GMP.MPZ ./gmp.jl:179
 [5] top-level scope
   @ REPL[13]:1

[adienes]

it's calling this method

function <<(x::Integer, c::Integer)
    @inline
    typemin(Int) <= c <= typemax(Int) && return x << (c % Int)
    (x >= 0 || c >= 0) && return zero(x) << 0  # for type stability
    oftype(x, -1)
end

which I guess just returns 0 when the number of bits to shift exceeds typemax(x)

why it does this I have no earthly idea; clearly this should be an OverflowError. maybe there can be a specialized <<(::BigInt, ::Integer) calling mpn_lshift

[NegaScout]

Also, the overflow error for exponentiation should not happen? Imho it should compute or get killed by OOM. Should I create a separate issue for this?

[adienes]

I think it's ok to have things error early if Julia knows that the operation will fail, for example there's precedent like this

julia> Vector{Int}(undef, 2^61-1)
ERROR: ArgumentError: invalid GenericMemory size: too large for system address width

although very possibly OverflowError is not the exact right error type

OOM kills are a pretty unpleasant experience in my opinion and I appreciate it when they can be avoided

[NegaScout]

maybe related to #14411 #855 ?

[StefanKarpinski]

That method should definitely be fixed. No idea why it's like that. Maybe a bit of git excavation can shed light, but probably not.