As pointed out by a commenter, there are some really surprising places where fractal patterns can
appear. For example, there was a recent post on the Wolfram mathematica blog by the engineer who writes
the unlimited precision integer arithmetic code.
Unlimited precision integers are numbers represented in a variable-length form, so that you can
represent 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
would be as a list of four-digit numbers: [0003,4012,3461,2978,3461,0029,3461,2983,4761,2987,3461,2483].
One of the challenges with very large numbers like that is doing arithmetic on them in a reasonable amount of time. You can 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.
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.
So, let’s look at a simple number, like 5743. We can re-write that as 57×102+43. In fact, we can write any four-digit base-ten number x in a similar form, as x1×102+x2.
So, suppose we want to multiply two 4-digit numbers in this expanded pair form: (x1×102+x2)×(y1×102+y2). We can generalize that slightly – replace the 102 with a symbol B – we’re basically doing base-100 multiplication in the example, so B=100.
The normal way of multiplying is basically to multiply the four pairs, (x1×y1,x2×y1,x1×y2,x2×y2), 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.
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:
(x1×B+x2)×(y1×B+y2) = x1y1B2 + (x2y1+x1y2)B + x2y2.
We can rewrite than in terms of three new variables:
- L = x1y1
- M = x2y2
- N = (x1y2 + x2y1)
So X×Y = LB2 + NB + M
Now, here’s the clever part. We’re going to find an alternate way of producing N, using
one multiply instead of two. We’ll start by taking (x1+x2)×(y1+y2):
- (x1+x2)(y1+y2) = (expand)
- x1y1 + x1y2 + x2y1 + x2y2 = (replace terms with equivalents)
- L + N + M
- So: N = (x1+x2)(y1+y2) – L – M
So once we compute X and Y, we can compute Z using a single multiplication, two additions, and two subtractions. Then when we recombine all of these, we’ll end up doing an extra shift. But since shifts,
additions, and subtractions are cheaper than multiplication, the cost of multiplies dominates – and we can do this multiplication using 3 sub-multiplies instead of 4.
If we’re multiplying a really big number, say, one with 32 digits, we can do this recursively – three 16-digit sub-multiplies; 3 8-digit sub-sub-multiplies for each of those, for a total of 9 sub-sub-multiplies; and so on, until we get to 243 single digit multiplications. Compare that to the
conventional multiplication, which needs to multiply each digit in the first number, with each digit in the other number, for a total of 1024 multiplications.
So, we’ve got a nice fast algorithm for multiplying large numbers. Now, what does this have
to do with fractals? Let’s look at a bitmap (via Wolfram) that shows the basic pattern of
what digits get multiplied by what digits:
Voila! The rows represent bits from one number; the column represent bits from the other. The multiplication pattern of Katsuba arithmetic is a fractal. In fact, it’s very close to being the
classic T-square fractal. In fact, it is the inverse of the T-square fractal after a finite number of iterations, with the bottom right corner snipped out. Fractals are ubiquitous in describing mathematical patterns. There are a huge number of recursive algorithms (which are, by definition, self-similar), which correspond to a variety of simple fractals.