Karatsuba Multiplication & Fractals

[David Makin]

Just found this, some of you probably have heard of it before, but anyway:

http://scienceblogs.com/goodmath/2007/09/fast_arithmetic_and_fractals.php

[HPDZ]

That pattern is kind of cool ... I hadn't thought of it before, but since the Karatsuba algorithm is recursive, it naturally gives rise to something with self-similarity. Thanks for sharing this article.

I've tried Karatsuba arithmetic in my software, but I don't generally make animations at magnifications high enough to reach the breakpoint where it's faster than traditional multiplication. My basic multiplication code is pretty fast (using SSE2 instructions and some tricky carry-save techniques), so the breakpoint is at a fairly high number of bits, at least 512 (that's about 154 decimal digits).

[David Makin]

Assuming you've seen the image relating to Karatsuba then you might like to see this - I created it a while ago and just realised it's basically the Karatsuba fractal:

http://makinmagic.deviantart.com/art/A-RIFS-reduced-cube-anim-48112383

(Hit the "download" button on the left of the page for the anim)