Re: sw multiply
 From: CBFalconer <cbfalconer@xxxxxxxxx>
 Date: Fri, 13 Oct 2006 06:59:08 0400
Bill Davy wrote:
"Charles Marslett" <cdeletethismarslett@xxxxxxxxx> wrote in message
"ivan" <wolfsafety@xxxxxxxxxxxxx> wrote:
I am very tight on time here. I have lots of long moltiplications
to do in e very short time. I needed to roughly estimate how
wastefull would be a moltiplication without a HW multiplier. But
found out that the safest option (with HW multiplier) is also the
cheapest (at least using PICs).
Depending on the architecture, and assuming you have space for a
table of arguments, the following pseudocode can make a really
fast software multiplier:
mul(a, b)
return (sqr(a+b)(sqr[a] + sqr[b])) >> 1
It costs a table of squares from the minimum argument value to the
sum of the two largest argument values, though, and that can eat a
lot of memory. Otherwise, it involves 3 table lookups, 2 adds, 2
subtracts and a right shift.
And if (a+b) goes over the (let's say byte) boundary and so makes
indexing hard, then (d+256)^2 is "easily" computed with some
simples sums too: sqr(d) + 2.256.d + 1.256.256 where d = (a+b) %
256 (and this only happens about a quarter of the time)
Or, once you have a byte multiplier, you can use the relationship:
A = (a + b)**2 = a**2 + 2ab + b**2
B = (a  b)**2 = a**2  2ab + b**2
so
A  B = 4ab
i.e.
ab = (A  B) / 4
requiring 3 one byte multiplications, an add, and a shift. Here a
is the high byte, and b is the low byte. There are some factors of
256 to consider in the rhs of the equation.
Another method that has worked out very well is to build a 8 by 16
bit multiplier, giving a 24 bit product, and call it twice with the
halves of one 16 bit operand. After which a 3 byte add and a carry
propagation gives you the full product. I used this effectively on
an 8080, where everything could be done in registers with a push
and pop or two between the 8*16>24 bit multiplications.
These are unsigned methods.

Some informative links:
<news:news.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smartquestions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>
.
 FollowUps:
 Re: sw multiply
 From: CBFalconer
 Re: sw multiply
 References:
 sw multiply
 From: ivan
 Re: sw multiply
 From: Jonathan Kirwan
 Re: sw multiply
 From: Joerg
 Re: sw multiply
 From: ivan
 Re: sw multiply
 From: Charles Marslett
 Re: sw multiply
 From: Bill Davy
 sw multiply
 Prev by Date: Re: MSP430F2013 documentation frustration
 Next by Date: Re: As a "general rule"?
 Previous by thread: Re: sw multiply
 Next by thread: Re: sw multiply
 Index(es):
Relevant Pages
