{"id":521,"date":"2007-09-29T15:18:00","date_gmt":"2007-09-29T15:18:00","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2007\/09\/29\/fast-arithmetic-and-fractals\/"},"modified":"2007-09-29T15:18:00","modified_gmt":"2007-09-29T15:18:00","slug":"fast-arithmetic-and-fractals","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2007\/09\/29\/fast-arithmetic-and-fractals\/","title":{"rendered":"Fast Arithmetic and Fractals"},"content":{"rendered":"

As pointed out by a commenter, there are some really surprising places where fractal patterns can
\nappear. For example, there was a recent post<\/a> on the Wolfram mathematica blog<\/a> by the engineer who writes
\nthe unlimited precision integer arithmetic code.<\/p>\n

<\/p>\n

Unlimited precision integers are numbers represented in a variable-length form, so that you can
\nrepresent very large numbers by a sequence of smaller numbers. For an overly simplified example, suppose you wanted to represent the number “340123461297834610029346129834761298734612483”. One way of doing that
\nwould be as a list of four-digit numbers: [0003,4012,3461,2978,3461,0029,3461,2983,4761,2987,3461,2483].<\/p>\n

One of the challenges with very large numbers like that is doing arithmetic on them in a reasonable amount of time. You can<\/em> do what we’d do on paper – basic long multiplication, one digit at a time. But that’s really very slow for really big numbers.<\/p>\n

Naturally, people have searched for better algorithms. One great example of that is called Karatsuba multiplication. The Karatsuba algorithm is based on the idea that you can replace some of the sub-multiplies by shifts, where shifts are less expensive than multiplications.<\/p>\n

So, let’s look at a simple number, like 5743. We can re-write that as 57×102<\/sup>+43. In fact, we can write any<\/em> four-digit base-ten number x in a similar form, as x1<\/sub>×102<\/sup>+x2<\/sub>.<\/p>\n

So, suppose we want to multiply two 4-digit numbers in this expanded pair form: (x1<\/sub>×102<\/sup>+x2<\/sub>)×(y1<\/sub>×102<\/sup>+y2<\/sub>). We can generalize that slightly – replace the 102<\/sup> with a symbol B – we’re basically doing base-100 multiplication in the example, so B=100.<\/p>\n

The normal way of multiplying is basically to multiply the four pairs, (x1<\/sub>×y1<\/sub>,x2<\/sub>×y1<\/sub>,x1<\/sub>×y2<\/sub>,x2<\/sub>×y2<\/sub>), and then shift the first pair left 4 places, the second two each two places, and then add them all up. That’s four multiplications. If we repeat this splitting process for each of the two digit numbers, then we end up doing 16 one-digit multiplications to multiply the two 4-digit multiplications.<\/p>\n

Katsuba is based on doing a bit of algebra on the paired form. Do an algebraic expansion of the symbolic version of the paired form:<\/p>\n

(x1<\/sub>×B+x2<\/sub>)×(y1<\/sub>×B<\/sup>+y2<\/sub>) = x1<\/sub>y1<\/sub>B2<\/sup> + (x2<\/sub>y1<\/sub>+x1<\/sub>y2<\/sub>)B + x2<\/sub>y2<\/sub>.<\/p>\n

We can rewrite than in terms of three new variables:<\/p>\n