10x15 matrix, `snf` crashes over `Int64` because of overflow; it gives incorrect result over `Int128`.

[lampretl]

The following code

using SmithNormalForm
X = [ 8   0  -18  -2    0   65   9  0   0  0  0   6   9  0   22;
     -4   0    0   1    0   -1   0  0   0  0  0   6   0  0   -4;
    -60   6  -54   6   13  -12  -3  0   0  0  0  42   0  0  -16;
     34  -7   71   2   -6  -23  -6  0  -1  0  0  -3  -4  0   -9;
      0   0    0   0    0    0  -1  0   0  0  0   0   0  0    0;
      0   0   -2   0    0    7   0  0   0  0  0   2   1  0    2;
      0   0    0   0    0    0   0  0   0  0  0   0   0  0    1;
     -6   1   -9   0    2   -1   0  0   0  0  0   1   0  0    0;
     28  -9   97   7  -18  -54  -1  0   0  0  0  17  -8  0  -48;
     -8   4  -50  -4    8   49  -9  0   0  0  0  -6   7  0   31 ];   
U,V,D = SmithNormalForm.snf(Int64.(X));

produces

ERROR: DivideError: integer division error
Stacktrace:
 [1] div
   @ ./int.jl:295 [inlined]
 [2] bezout
   @ ~/.julia/packages/SmithNormalForm/eLg8H/src/bezout.jl:12 [inlined]
 [3] colpivot(V::Matrix{Int64}, Vinv::Matrix{Int64}, D::Matrix{Int64}, i::Int64, j::Int64; inverse::Bool)
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:108
 [4] colpivot
   @ ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:98 [inlined]
 [5] smithpivot(U::Matrix{Int64}, Uinv::Matrix{Int64}, V::Matrix{Int64}, Vinv::Matrix{Int64}, D::Matrix{Int64}, i::Int64, j::Int64; inverse::Bool)
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:128
 [6] smithpivot
   @ ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:118 [inlined]
 [7] snf(M::Matrix{Int64}; inverse::Bool)
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:207
 [8] snf(M::Matrix{Int64})
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:173
 [9] top-level scope
   @ REPL[62]:1

Running U,V,D = SmithNormalForm.snf(Int128.(X)); X == U*D*V finishes successfully and returns true, but this is valid only modulo 2^128, because big.(X) == big.(U)*big.(D)*big.(V) returns false.

Running U,V,D = SmithNormalForm.snf(BigInt.(X)) returns

ERROR: MethodError: no method matching typemax(::Type{BigInt})

Closest candidates are:
  typemax(::Union{Dates.DateTime, Type{Dates.DateTime}})
   @ Dates ~/julia-1.9.2/share/julia/stdlib/v1.9/Dates/src/types.jl:444
  typemax(::Union{Dates.Date, Type{Dates.Date}})
   @ Dates ~/julia-1.9.2/share/julia/stdlib/v1.9/Dates/src/types.jl:446
  typemax(::Union{Dates.Time, Type{Dates.Time}})
   @ Dates ~/julia-1.9.2/share/julia/stdlib/v1.9/Dates/src/types.jl:448
  ...

Stacktrace:
 [1] snf(M::Matrix{BigInt}; inverse::Bool)
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:189
 [2] snf(M::Matrix{BigInt})
   @ SmithNormalForm ~/.julia/packages/SmithNormalForm/eLg8H/src/snf.jl:173
 [3] top-level scope
   @ REPL[18]:1

[thchr]

I don't think there's much to do here. The elements of the Smith normal form matrices of the matrix you gave are larger than typemax(Int).

The error you see in the Int version comes from calling bezout(-1, -9223372036854775808) - note that -9223372036854775808 is simply typemin(Int). The same div error occurs for the analogous Base function, gcdx(-1, typemin(Int)). Both come from div(typemin(Int), -1): and, indeed, it seems like a Base bug that this would error.

The Int128 error is probably wrap-around as you mention.

With a small fix to the package (*), the result can be computed using big.(X) though; answer below.

Details

U = BigInt[1 0 0 0 0 0 0 0 0 0; 32 -82396 1 0 0 0 0 0 0 0; 656 1 0 0 0 0 0 0 0 0; -448 -839725 1543334146932952046879412 1 0 0 0 0 0 0; 0 1 -22256072812537234348845 29898143144712239045773063978 1 0 0 0 0 0; 9 -23543 28606295047062974377813 24877080937203239268323576426 966475899959690585169 4 16 -16 -4 -1; 4 -11776 114440327684100469634980 -11297389966895249499261346992 2174570774909303816628 9 36 -36 -9 -2; 72 98097 -141459067172532009005552 114115050170835664739769477 -2323935232175801452518 -10 -41 41 10 0; -536 -1159446 335383205886542929613836 63816846644680293439046215909 2741300416003408844165 11712698252443098600167654884799834113257375746067176114342554594989444545085772065749195663015546861082258547669300 77526907480456700258252572808913187702036915652539677783457455251679838277979238490589274152716577134530848655934221 -77526907480456700258252572808913187702036915652539677783457455251679838277979238490589274152716577134530848655934220 -19381726870114175064563143202228296925509228913134919445864363812919959569494809622647318538179144283632712163983555 0; 227 545404 -451456530989421854882146 432381925096620919449920341700 -355838854076067897252 -3 -16 16 4 1]

V = BigInt[8 0 -18 -2 0 65 9 0 0 0 0 6 9 0 22; -5308 6 11754 1318 13 -42652 -5907 0 0 0 0 -3894 -5904 0 -14448; -437358228 494376 968483160 108597993 1071148 -3514356273 -486713460 0 0 0 0 -320850210 -486466272 0 -1190458116; 674989887714487542032148104745254 -762987362224125101128051148569 -1494693131557529706490231202582263 -167602990885285697856344949463460 -1653139284818937719110777488557 5423826040608923736358815820829873 751161502589885478750755857033971 0 -1 0 0 495179085143608520161185914990055 750780008908773416200191831459692 0 1837274660916269272046396356370839; -20180944284120989687814114892799353216103240555980788316901764 22811905373383299874497367097073256280204412092673664743196 44688549204725225645421326071362190065490451233006633054960660 5011018212970172472141782672554228419605503520856186582110647 49425794975663816394744295376717988961616364009540020523793 -162162327354143419477037588352976774477928726229391296378626827 -22458334129229529322083149871166296874358951759651933099344432 0 29898143144712239045773063978 0 0 -14804935169891257211566608972813405598099065404610902880242346 -22446928176542837672145901187617924686006145470920348018824712 0 -54931100808227259645405869381493578476808185300212277945999114; 12323232200797621798171844671874826577255886295821516636988092086999901385198545952 -13929794508179517029900267204992680838525715156133709615536810830411123752100992 -27288483671198327791785251038758020170328947969461003800523882879461835261256963800 -3059913358437136173998110767161217623056183001221178594823717805504358660671485000 -30181221434388953564783912277316786773572199144135124264308743279850844653724900 99022324529147117748718248086976550346459586636909037459162254235609143597014140540 13713890808140061481042126855403873076331162450294677700398013496408395178926178412 0 -18256913807292766635045080293201474840718924635700 0 0 9040441876640946884035788573430655878700055683383001908505870533078972287244861736 13706925910885971722527176721801477148937839702933103593531857088467767687512936364 0 33542965124671372463883739835174110444533198961731274012581311988882762233717403765; -376473946583344837286158553129351145833332659767964977778313571029416901881078231479829604417629041816669210021076796453901163772822425104895968710 425554321150413311255189009184149613945587450441173557148811946776597020521752314190313032240131818027222387613102888276836584579812746343609452 833661410949170507853312090416961291578268523511219803920435048107336579432259455049299739339602833058779288957273177726471111941156500017858126140 93480155164110589354656854768561562037414783766329484108855174837189329939486929398671931556047062727126468923849544781060036066335887156708578000 922034362492562174386242853227211477803658758312945714944140242807792309019084851857997030374973311853923269052491709508290288327748861000332520 -3025125608923595799457042814026410945014586208194936938437714231483106761119351972282406192792461262518738707871731510692706116859227551475379326680 -418958477080337320482931990254398326247415130577230011550634631057348625637649650876773982282197585713804299442994636562858122007275666081589384138 0 2758238776641353232632709972354179652194945448559 0 0 -276184914533710278215412473879065116265344520516772287724494494658413375959511897170790654261241511240238254515080732146325588219779679048355533756 -418745699919762113827304395749809319051889405282595182967387177814162976308477612938506278314882009710512145222895551860481320601187407367475305604 0 -1024735414770093983401649560450601107737025627983246137593093918634709961566115291204862243674166623022379593757506501396583161168170423472819079729; -188236973291672418643079276564675572916666329883982488889156785513777559299471669488973763582521818181275707124882816034947884282716975397450971891 212777160575206655627594504592074806972793725220586778574405973387246259596589215161243186582998116576168603812742782620697885716386108427940982 416830705474585253926656045208480645789134261755609901960217524051606929438808990533184077325147033710767673588857160518591665537237607776963608970 46740077582055294677328427384280781018707391883164742054427587418363520435473033549501576115755957370454673875501589834805924242104664686720831500 461017181246281087193121426613605738901829379156472857472070121401616278070254051738852967857185747573562295741976654719790886577986417055100710 -1512562804461797899728521407013205472507293104097468469218857115734073276908193649908386250317718014146867011060415792085049434908218840430001544810 -209479238540168660241465995127199163123707565288615005775317315527638371426843022232984528321086270070560587090359950541470937681966695275480124635 0 0 0 0 -138092457266855139107706236939532558132672260258386143862247247328523776902743502957464566123275274420648979166349563770721703170340708524062147826 -209372849959881056913652197874904659525944702641297591483693588906046072887589146734817633002197008379976595511585922781088973254342541376407538904 0 -512367707385046991700824780225300553868512813991623068796546959314821159676517721783216882497016202448832972496751967409571409534565290848251030947; 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0; -6171 7 -80706930 0 0 0 0 0 0 0 0 -4527 -6864 0 -16797; 75294789316668967467392764891716252494447851044772832511396739164738275509773781980447101952717943664298928022921580893550535529248394595068683184 -85110864230082662262563872143250626612560892071423636837336230663372150105672961227745418895708181506220484968961166322670747832437018996349618 -166732282189833968680126790172778825547224730546561154457875536121293564210814454612025055425571461903810189967235351075730038729410271167929455680 -18696031032822117870931370953712312407482956753265896821771034967344307485930782795277609543148727833928971642646239826514159726408231213299601850 -184406872498512434877248570645442295560731751662589142988828048560635654673628818913683351203206199465837302397817951411562286737928433424682829 605025121784719159891408562805282189002917241638987387687542846293593691222079925028912515145760955101068221839045126532775470994138036480059245931 83791695416067464096586398050879665249483026115446002310126926211050415516489676500908964321459350895326009282868867340472243490511464094774956850 0 0 0 0 55236982906742055650536569101122526997172944214482495447768438874760955970554861214412930677586465392706653462739226200722889313669494422405805060 83749139983952422776763014376143536816680096944034577164561270811184570254934521185509275654792125543640061151436230049755851262421431051763771816 0 204947082954018796707987541081112873279173528898309853243049899791418683965587715644963986944455799606986768780905685168212643772139826022265106598; 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0; 4248889328512863025497984974232384716203380172785998109373584313996934758919304097591928561444458881828962923099041147857945462222 -4802813860413937104933668019102168104223866058170259630287707623116012989433490587985150518859778346625958380984382216781150554 32127231944204873320036926466144707702493315270232105483471092667417061835926347657430300 3602492076151473820333026257103190440064182188953533284339388598801166229145049079600750 35532905128232884374779195129524530219771377161168954721533188958665746067231301893255 -116580797457792113328306590120170648647593190004390296660657635185046300164268931803291220 4727569776600785423623040553469567470591025487182738088227476596893729648428229773852297989090451064614609146942466931604236879684 0 0 0 0 3117026195408645181101950544397307099641289071746328371975587510600169021860981724858227334800699615237772372433947110838366198291 4725968838647314111254729330796533414556284201229981729496831160286129062702013512661196118750991245989367143875398633418705116096 0 11565175775876760548680272589998020794971069468050498895746545151919272011082408914610486654645628833989546983328273785219160107642]

D = BigInt[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

Which indeed has U * D * V == X.

*) The fix involves changing

SmithNormalForm.jl/src/snf.jl

Line 189 in 0b61553

rsize = typemax(R)

to rsize = typemax(eltype(eachindex(M))). See also #4.

[thchr]

Ah, and there's probably nothing to do for div(typemin(Int), -1) throwing, I think: the answer is typemax(Int)+1 which that's out of Ints range (wrapping back to typemin(Int)).

X-ref JuliaLang/julia#14273 (comment) though.

[lampretl]

In SNF computations, the entries of a matrix can get arbitrarily large, even for small matrices. So I think the package should work over BigInt instead of IntN for any N=64,128,....

[thchr]

I think it is more natural that if the user worries this could happen that the user is responsible for converting their input matrix to BigInt. This is pretty consistent with how Int etc is treated in Julia; overflow is possible and automatic lifting to BigInt is not done.

[lampretl]

Of course, but the problem is that SmithNormalForm.snf does not accept Matrix{BigInt}.