Let’s say I have three integers of the same type and want to compute (a * b) % c. a * b might overflow producing wrong results even though the mathematically correct answer (e.g. using BigInts) would not overflow. What is the best way to compute this expression? a, b, and c may be Int128s, and conv…

My initial thought was to do ( (a % c) * (b % c) ) % c but the bracketed product can still overflow. cf. Modular arithmetic - Wikipedia and Example implementations Here’s a reference I don’t claim to fully understand that may be a strategy to prevent overflow by multiplying out: Labor of Divis…

Translating the (completely opaque and unverified) wikipedia code to an equally dodgy julia version: ▶ Listing: `mul_mod(a,b,c)` “Testing”: julia> a, b, c = (4856388669903036, 6493747681980967, 3860134847225580) (4856388669903036, 6493747681980967, 3860134847225580) julia> (big(a) * big(b)) % big(…

Wow! That’s 3x faster than the bigint verison! Mind if I steal that and put it in GitHub - JuliaMath/IntegerMathUtils.jl ?

An unrolled arbitrary precision multiplication and an unrolled arbitrary precision division with remainder could do this, but I imagine it would be pretty ugly and take about 40-80 operations. Integrating the two might help, though.

Sure - it’s a line by line translation from the Wikipedia page and I make no claims of correctness!

[image] jd-foster: Translating the (completely opaque and unverified) wikipedia code to an equally dodgy julia version Looks kind of like the algorithm explained here: c++ - Ways to do modulo multiplication with primitive types - Stack Overflow

How about expressing (a*b)%c in base 2^64 but perform the calculations with 128-bit precision so you don’t need to worry about overflow?

a, b, and c may be Int128s already, and performing calculations in 256-bit precision is slower.

Mind if I steal that and put it in GitHub - JuliaMath/IntegerMathUtils.jl ? Be careful with code you don’t understand, especially when it is advertised as “completely opaque and unverified”. Here’s an example where it is wrong: julia> a,b,m = (0x557f0d8d9f08cab0f5b1f6e6fe814efe, 0xff3850c2465783…

[image] Lilith: for _ in 1:64 This looks wrong. In the original code there was a loop for (i = 0; i < 64; ++i), but that was for uint64_t, whereas you are working with UInt128. If you look at the stackoverflow post that I linked above , you’ll see that it is describing a variant of long mul…

Modular multiplication without overflow

General Usage Performance

stevengj November 18, 2022, 11:40pm 8

Looks kind of like the algorithm explained here: c++ - Ways to do modulo multiplication with primitive types - Stack Overflow

Topic		Replies	Views
Wrong results in calculation Performance	21	3347	March 12, 2019
Tonight I hated julia, REPL and overflows New to Julia integer-overflow	64	6694	March 14, 2020
`mul_hi` in Julia? General Usage	19	1317	October 1, 2025
What is faster? Modular Arithmetic functions and operations Performance question	20	2567	December 4, 2020
Memory consumtion Rational{BigInt} on bernoulli number example Performance	14	932	January 27, 2020

Modular multiplication without overflow

Related topics