How can you calculate a factor if you have the other factor and the product with overflows?

Question

a * x = b

I have a seemingly rather complicated multiplication / imul problem: if I have a and I have b, how can I calculate x if they're all 32-bit dwords (e.g. 0-1 = FFFFFFFF, FFFFFFFF+1 = 0)? For example:

0xcb9102df * x = 0x4d243a5d

In that case, x is 0x1908c643. I found a similar question but the premises were different and I'm hoping there's a simpler solution than those given.

Griddlecake

Split into large and small, do 4 multiplications and add. (L1+S1)*(L2+S2) – Dunker

This may not always have a single unique solution, I'm not sure. My first thought was to find the multiplicative inverse, the way compilers do to turn division into multiplication, which is possible for modular types like 32bit integers. gcc just generates code that return 0 or 1 for division by 0xcb9102df, of course. (multiplicative inverses exist for division by small integers, like the div13 function I included in that godbolt link). – Kentigerma

I have this equation (in decimal) 4*x=?2, ? being the overflowed digit. Can I recover x? – Meghannmegiddo

Answer 1

Numbers have a modular multiplicative inverse modulo a power of two precisely iff they are odd. Everything else is a bit-shifted odd number (even zero, which might be anything, with all bits shifted out). So there are a couple of cases:

Given a * x = b

• tzcnt(a) > tzcnt(b) no solution
• tzcnt(a) <= tzcnt(b) solvable, with 2^tzcnt(a) solutions

The second case has a special case with 1 solution, for odd a, namely x = inverse(a) * b

More generally, x = inverse(a >> tzcnt(a)) * (b >> tzcnt(a)) is a solution, because you write a as (a >> tzcnt(a)) * (1 << tzcnt(a)), so we cancel the left factor with its inverse, we leave the right factor as part of the result (cannot be cancelled anyway) and then multiply by what remains to get it up to b. Still only works in the second case, obviously. If you wanted, you could enumerate all solutions by filling in all possibilities for the top tzcnt(a) bits.

The only thing that remains is getting the inverse, you've probably seen it in the other answer, whatever it was, but for completeness you can compute it as follows: (not tested)

; input x
dword y = (x * x) + x - 1;
dword t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
t = y * x;
y *= 2 - t;
; result y

Quadriplegic

Thank you very much! It works and this was exactly what I was looking for. I don't fully understand it, though. Instead of asking you to explain a huge subject could you perhaps refer me to a general topic I can google / a book to read? Thanks! – Griddlecake

(I'm currently in Alg 2 if the US system applies) – Griddlecake

@Griddlecake ok probably, where's the problem? – Quadriplegic

I understand well enough to implement all you said but I guess I don't understand the principle of inverses and I have little experience with modular math. I don't NEED to have perfect understanding for what I'm doing, per se, but it's a subject I'm interested in yet lacking. – Griddlecake

So the multiplicative inverse of a uint32_t multiply is different from the multiplicative inverse of a uint32_t divide? I'd only heard of modular multiplicative inverses in the context of replacing division with a multiply and shifts. (@Lupe: you might find that answer I linked interesting, but the math in Granlund and Montgomery's paper about replacing division with multiplication is pretty complex. I haven't tried to grok it; I just know it works) – Kentigerma

@PeterCordes that linked question isn't actually about modular multiplicative inverses though is it? All the terms occur there, but in a slightly different combination, afaict it ends up doing a modulo by using a fixed-point inverse. What happens here is solving x * c == 1 (with wrapping math) and then x is the inverse of c – Quadriplegic

@Griddlecake well I'm not sure what to tell you, they may cover this in Alg 2, maybe not. Either way the existence of multiplicative inverses modulo a power of two for odd numbers follows from the gcd between a power of 2 and an odd number being 1 and Bézout's identity. It also follows pretty intuitively from a method to construct them: build up the inverse by starting at 1, then seeing which is the lowest bit you need to cancel out, add the relevant power of two, etc. The algorithm for inverses there is an application of Newton's method. The rest is obvious I guess? – Quadriplegic

@harold It definitely won't be covered in my class this year but I will research it on my own with some of the keywords you used and general topics. Thank you! – Griddlecake

@harold: That's right, it's about replacing division with multiplication, not about using a multiply as an inverse to another multiply. I was saying I hadn't heard of the latter before, but I thought there might be some relation between that and this, or at least that it's another interesting tool to keep in your bag of tricks even if you don't really grok the math. (I figure I'll read more and understand it sometime when I need to implement it myself. Until then, I'm just happy to know it exists). Thanks for the summary of finding inverses, esp. confirming that those are Newton iterations – Kentigerma