In almost all assembly books you’ll find some nice tricks to do fast multiplications. E.g. instead of “imul eax, ebx, 3” you can do “lea eax, [ebx+ebx*2]”\u00c2\u00a0(ignoring flag effects). It’s pretty clear how this works. But how can we speed up, say, a division by 3? This is quite important since division is still a really slow operation. If you never thought or heart about this problem before, get pen and paper and try a little bit. It’s an interesting problem.<\/p>\n
The non-obvious trick here is: We can multiply by the inverse (i.e. the reciprocal). Maybe this sounds a little bit strange, since the inverse of 3 is what, 1\/3? Yes, it is, over the rational numbers. But here we calculate over the finite ring Z\/(232<\/sup>)Z (for the non-mathematical readers: We wrap around after 232<\/sup>). And in Z\/(232<\/sup>)Z all odd elements have a multiplicative inverse. We can find the inverse with the extended euclidean algorithm<\/a> (gcdex):<\/p>\n For numbers a, b gcdex(a, b) returns [g, x, y] where<\/p>\n E.g. gcdex(3, 232<\/sup>) = [1, -1431655765, 1]<\/p>\n That means: Since we are using the modulo 232<\/sup> math (we have 32 bit registers), this is exactly what we need:<\/p>\n -1431655765*3 + 232<\/sup> = 0xaaaa_aaab * 3 = 1 (mod 232<\/sup>) Now, let’s look what we have so far: We need the another trick: We look at the 64 bit result and count the “overflows”. This is somehow similar to fixed point arithmetic. Look at this:<\/p>\n 3 * 0xaaaa_aaab = 0x2_0000_0001, and that means This is cool, because<\/p>\n (n*3 + c) * 0xaaaa_aaab = (n*233<\/sup> + n) + c*0xaaaa_aaab<\/p><\/blockquote>\n So, with c in {0, 1, 2} we have the nice identity:<\/p>\n (n * 0xaaaa_aaab) >> 33 = n div 3, for all 0 <= n < 232<\/sup><\/p><\/blockquote>\n Last but not least, our final solution for dividing by 3 is:<\/p>\n [IN: eax dividend] Of course, this is only half of the story; this is not the general solution for all divisors. And it doesn’t handle signed division. For futher reading see this paper<\/a> or this gcc bug report<\/a>. It also has its chapter in the AMD optimization manual<\/a>.<\/p>\n BTW: This is part of reason why you have to learn all that math stuff in computer science. It’s useful! \ud83d\ude42<\/p>\n","protected":false},"excerpt":{"rendered":" In almost all assembly books you’ll find some nice tricks to do fast multiplications. E.g. instead of “imul eax, ebx, 3” you can do “lea eax, [ebx+ebx*2]”\u00c2\u00a0(ignoring flag effects). It’s pretty clear how this works. But how can we speed up, say, a division by 3? This is quite important since division is still a … Read more<\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[32,38],"tags":[],"class_list":["post-23","post","type-post","status-publish","format-standard","hentry","category-tricks","category-x86"],"_links":{"self":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts\/23","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=23"}],"version-history":[{"count":0,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=\/wp\/v2\/posts\/23\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=23"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=23"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pagetable.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=23"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
\n-1431655765 * 3 + 1*232<\/sup> = 1<\/p><\/blockquote>\n
\nSo 1\/3 = 0xaaaa_aaab (mod 232<\/sup>)<\/p><\/blockquote>\n
\nFor numbers divisible by 3 this is already our solution. We just have to multiply them by 0xaaaa_aaab, since this is the inverse of 3. But — in the general case — we want this to work with all values (the remainder should be ignored, but with our solution it destroys the result).<\/p>\n
\n(n*3) * 0xaaaa_aaab = n * 233<\/sup> + n<\/p><\/blockquote>\n
\nmov ecx, 0xaaaa_aaab \/\/ 1\/3
\n<\/em>mul ecx \/\/ multiply with inverse
\n<\/em>shr edx, 1 \/\/ shift by 33
\n<\/em>[OUT: edx = eax div 3]<\/p><\/blockquote>\n