[A83] Re: Faster Multiplication
[Prev][Next][Index][Thread]
[A83] Re: Faster Multiplication
The routine functions based on the binary representation of the number in h.
Let's consider the breakdown if you're multiplying 12 by x, with h = 12 and e
= x. We'll use a symbol for e just to demonstrate how it doesn't matter :-)
Given that 12 = %00001100, let's step through the routine. For the first
four add hl,hl's, it would skip the add hl,de and thus simplify to just:
add hl,hl
add hl,hl
add hl,hl
add hl,hl
At this point, h = %11000000 and l still equals 0. The next time it adds,
however, it sets the carry and so adds de:
add hl,hl
add hl,de
Now h = %10000000 and l = x. The next time it adds, it multiplies l by 2 and
sets the carry again:
add hl,hl
add hl,de
Now h = 0 and l = 3*x (we added x, multiplied by 2, then added x again).
This means hl = 3*x.
We've done 6 add hl,hl's so far, and have two left to do since we're going
through all 8 bits of h:
add hl,hl
add hl,hl
This effectively multiplies hl by 4, and since hl was 3*x before, hl now
equals 12*x. Voila :-)
The principle behind this is that 12 is comprised of 8 and 4, so we add de*8
and de*4, which are achieved by adding de to hl at the right times as we
shift hl to the left. This method works for any values for the
multiplicands, with very little variability in speed. You'd have a hard time
coming up with a faster algorithm without resorting to precalculated
multiplication tables.
In a message dated 5/30/2001 3:59:54 PM Eastern Daylight Time,
Mike3465@aol.com writes:
> I don't know of a multiplication function that would be very fast at all for
> large values for the smaller number. *trying to figure out the code*
> uh....
> *inputting some variables to see....* *still not getting it*
> Wouldn't you have problems with adding hl to it self when h is the value
> you
> want to multiply by?
> can you explain that a bit better? *still rather confused*
> Does that work for any number you input into it?
>
----
Jonah Cohen
<ComAsYuAre@aol.com>
http://jonah.ticalc.org