2010-02-08

Really slick way to calculate x % (2^32-1)

From Numernia's solution/analysis of WiteG #5:

mul dword ptr ds:[40120C]
add eax, edx
adc eax, 0

The result is that eax = (eax * [40120C]) % (2^32-1)... Can you prove why?

1 comment:

  1. AnonymousFebruary 9, 2010 at 5:52 PM

    edx:eax = edx * 2^32 + eax (mod 2^32-1)
    = ((edx * 2^32) mod 2^32-1 + eax (mod 2^32-1)) mod 2^32-1
    = (edx + eax) mod 2^32-1

    There are some corner cases, however, that you might want to check. Example 3650476437 * 2908093780. While the result is correct mod 2^32-1, it is not reduced (i.e. [0, 2^32-2]).

    It's a cool trick, though.

    ReplyDelete

thanks for commenting!

Subscribe to: Post Comments (Atom)