[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #7 from github-bugzi...@puremagic.com --- Commits pushed to master at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/93ee606fba69390b2f9ef7d77e43abc02b82cd19 Fix Issue 16264(+11599) - BigInt multiplication crashes on 64-bit https://github.com/dlang/phobos/commit/18c19d8527ac8ff2bf688df2ebdae304f1b5d7b6 Merge pull request #5715 from yosupo06/Issue_16264 --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #6 from github-bugzi...@puremagic.com --- Commits pushed to stable at https://github.com/dlang/phobos https://github.com/dlang/phobos/commit/93ee606fba69390b2f9ef7d77e43abc02b82cd19 Fix Issue 16264(+11599) - BigInt multiplication crashes on 64-bit https://github.com/dlang/phobos/commit/18c19d8527ac8ff2bf688df2ebdae304f1b5d7b6 Merge pull request #5715 from yosupo06/Issue_16264 Fix Issue 16264(+11599) - BigInt multiplication crashes on 64-bit --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 Kirill Kryukovchanged: What|Removed |Added CC||kkryu...@gmail.com --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #5 from Kirill Kryukov--- Looks like it might be the same issue with #11599 ( https://issues.dlang.org/show_bug.cgi?id=11599 ) If so, "Asymmetric Karatsuba" bug is known since 2013, and stays unfixed. Which practically means that no one uses D's BigInt in large calculations. --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #4 from Kirill Kryukov--- Actually I've no idea why the 32-bit compile works with my initial test. If I add the following unittest into biguintcore.d, and compile in 32-bit (dmd.exe -main -unittest biguintcore.d), it crashes too. unittest { BigUint a, b; a.fromDecimalString( `207672245542926038535480439528441949928508406405023044025560363701392340829` ~ `852529131306106648201340460604257466180580583656068555417076345439694125326` ~ `843947164365500055567495554645796102453565953360564114634705366335703491527` ~ `429426780005741168078089657359833601261803592920462081364401456331489106355` ~ `199133982282631108670436696758342051198891939367812305559960349479160308314` ~ `068518200681530999860641597181672463704794566473241690395901768680673716414` ~ `243691584391572899147223065906633310537507956952626106509069491302359792769` ~ `378934570685117202046921464019396759638376362935855896435623442486036961070` ~ `534574698959398017332214518246531363445309522357827985468581166065335726996` ~ `711467464306784543112544076165391268106101754253962102479935962248302404638` ~ `21737237102628470475027851189594709504`); b.fromDecimalString( `335690982744637013564796917901053301979460129353374296317539383938630086938` ~ `465898213033510992292836631752875403891802201862860531801760096359705447768` ~ `957432600293361240407059207520920532482429912948952142341440301429494694368` ~ `264560802292927144211230021750155988283029753927847924288850436812178022006` ~ `408597793414273953252832688620479083497367463977081627995406363446761896298` ~ `967177607401918269561385622811274398143647535024987050366350585544531063531` ~ `7118554808325723941557169427279911052268935775`); BigDigit[] cdata = new BigDigit[a.uintLength() + b.uintLength()]; mulInternal(cdata, a.data, b.data); // Crashes } Also, this test is a bit further reduction. Note that the crash disappears if you change the operand sizes (by adding or removing a few lines in either a or b), so it's specific to particular length of the operands. The crash message is now more specific: "core.exception.AssertError@m\biguintcore.d(1190): Bigint Internal Error: Asymmetric Karatsuba" So I think it's related to how mulInternal divides the operands before calling mulKaratsuba. However, this bug is now probably applies to both 32-bit and 64-bit! This blocks D's BigUint (and be extension BigInt) use in any non-toy calculation. --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #3 from Kirill Kryukov--- Here is the reason 32-bit BigUint multiplication works: std/internal/math/biguintcore.d has the following: version(D_InlineAsm_X86) { import std.internal.math.biguintx86; } else { import std.internal.math.biguintnoasm; } So, 32-bit compile uses the seemingly correct std.internal.math.biguintx86. On the other hand, 64-bit compile uses std.internal.math.biguintnoasm - buggy, untested and apparently never used in the real world. --
[Issue 16264] BigInt multiplication crashes on 64-bit (biguintnoasm.d(276): Range violation)
https://issues.dlang.org/show_bug.cgi?id=16264 --- Comment #1 from Kirill Kryukov--- Slightly reduced (same behavior: 32-bit compile works, 64-bit one - crashes). = a.d begin = import std.internal.math.biguintcore; void main() { BigUint a, b; a.fromDecimalString( `335690982744637013564796917901053301979460129353374296317539383938630086938` ~ `465898213033510992292836631752875403891802201862860531801760096359705447768` ~ `957432600293361240407059207520920532482429912948952142341440301429494694368` ~ `264560802292927144211230021750155988283029753927847924288850436812178022006` ~ `408597793414273953252832688620479083497367463977081627995406363446761896298` ~ `967177607401918269561385622811274398143647535024987050366350585544531063531` ~ `7118554808325723941557169427279911052268935775`); b.fromDecimalString( `207672245542926038535480439528441949928508406405023044025560363701392340829` ~ `852529131306106648201340460604257466180580583656068555417076345439694125326` ~ `843947164365500055567495554645796102453565953360564114634705366335703491527` ~ `429426780005741168078089657359833601261803592920462081364401456331489106355` ~ `199133982282631108670436696758342051198891939367812305559960349479160308314` ~ `068518200681530999860641597181672463704794566473241690395901768680673716414` ~ `243691584391572899147223065906633310537507956952626106509069491302359792769` ~ `378934570685117202046921464019396759638376362935855896435623442486036961070` ~ `534574698959398017332214518246531363445309522357827985468581166065335726996` ~ `711467464306784543112544076165391268106101754253962102479935962248302404638` ~ `21737237102628470475027851189594709504`); BigUint c = BigUint.mul(a,b); // Crashes BigUint ce; ce.fromDecimalString( `697137001950904057507249234183127244116872349433141878383548259425589716813` ~ `135440660252012378417669596912108637127036044977634382385990472429604619344` ~ `73874622429527200379708978133071390303850450970292020176369525401803474` ~ `998613408923490273129022167907826017408385746675184651576154302536663744109` ~ `111018961065316024005076097634601030334948684412785487182572502394847587887` ~ `507385831062796361152176364659197432600147716058873232435238712648552844428` ~ `058885217631715287816333209463171932255049134340904981280717725999710525214` ~ `161541960645335744430049558161514565159449390036287489478108344584188898872` ~ `434914159748515512161981956372737022393466624249130107254611846175580584736` ~ `276213025837422102290580044755202968610542057651282410252208599309841499843` ~ `67225104863867183370008181364966502137725166782667358559333222947265344` ~ `524195551978394625568228658697170315141077913403482061673401937141405425042` ~ `283546509102861986303306729882186190883772633960389974665467972016939172303` ~ `653623175801495207204880400522581834672918935651426160175413277309985678579` ~ `830872397214091472424064274864210953551447463312267310436493480881235642109` ~ `668498742629676513172286703948381906930297135997498416573231570483993847269` ~ `479552708416124555462530834668011570929850407031109157206202741051573633443` ~ `58105600`); assert(c == ce); } = a.d end = --