A89: Shifting/Multiplying. . .

To: <assembly-89@lists.ticalc.org>
Subject: A89: Shifting/Multiplying. . .
From: "Scott Noveck" <noveck@pluto.njcc.com>
Date: Mon, 13 Sep 1999 19:06:03 -0400
Reply-To: assembly-89@lists.ticalc.org


Another optimization (note: "optomization" is spelled with a _z_ =)
question:  If I'm multiplying one variable number by a constant that is the
sum of several powers of two, is it better to flat-out multiply or to
perform several left shifts (multiplying by the powers of two) and adding
those numbers?

For example:  I want to multiply an arbitrary variable value contained in d0
by 12.  Ten is the sum of 2 powers of two: 8 (2^3) and 4 (2^2).  I can use a
simple "mulu.w #12,d0" or I can use the following little algorithm:

mul_d0_12:
 move.w d0,d1    ;arbitrary value is a word
 lsl.w #2,d0     ;d0 = (4 * d0)
 lsl.w #3,d1     ;d1 = (8 * d0)
 add.w d1,d0     ;d0 = ((8 * d0) + (4 * d0))
                 ;   = (d0 * (8 + 4))
                 ;   = (d0 * 12)
                 ;[via distributive property of multiplication]

I'm pretty sure that the algorith is a good deal faster and not too much
larger, although Motorola never did send me my manual so I could tally this
stuff up myself (Olle, how do I request it again?).  If somone could just
give me a count of the size/speed of the algorith compared to the
multiplication (or even show me a better way to do it -- Zoltan =) I'd
appreciate it.

Also, to what point is this more efficient?  If I were to expand upon this
to multiply by 31 -- 2^4 + 2^3 + 2^2 + 2^1 + 2^0 (w/ 2^0 not requiring any
shifting), would it still be more efficient than multiplying?  It's
beginning to seem to me like the 68k's multiplication/division operations
are more or less wasteful. . .

    -Scott

Follow-Ups:

Re: A89: Shifting/Multiplying. . .

From: Cody R Maggard <ravenloft_15@juno.com>

A89: Shifting/Multiplying. . .

From: Zoltan Kocsi <zoltan@bendor.com.au>