sw multiply

Yes, shift and conditionally add is one possibility.

Jon

Hello Jon,

In case of fixed multiplication coefficients: If the processing resources are already stretched Ivan might want to consider to re-write the coefficients using the canonical signed digit (CSD) representation, to see if that will increase the number of zeroes. Usually it does. The thought behind this is that a subtract typically does not require more CPU cycles than an add. So one can use both to save resources.

Probably he can't use a higher level language such as C here. I would only know how to do that in assembler.

--
Regards, Joerg

http://www.analogconsultants.com

Or use the library function from a programming language runtime library and let someone else worry about how it's done.

The latter. Which is the most efficient depends on what you consider 'efficiency', ie. what you count as expense, and what as gain.

Under various interpretations, the most efficient solution might be any of the following:

0) don't do it: avoid having to actually multiply in the first place 1) don't do it again: use existing code e.g. your compiler's runtime library 2) don't do it yourself: get someone else to do it (preferrably someone who knows how) 3) don't do it yet: get yourself some background education on low-level tricks first. A textbook should help. 4) don't discount what you know: remember how you learned to do multi-digit muliplication on decimals using memorized single-digit tables? Shouldn't be too hard to port to binary, right? The result would be called "iterated shifting and addition".

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

In one particular test and measurement project I coded on, it turned out to be quicker, simpler and less codespace to directly convert input values to packed BCD base 10 logarithms via a lookup table then do the required multiplications and divisions by adding and subtracting the BCD logs. All they then neeeded was unpacking for the LCD.

--
Ian Malcolm.   London, ENGLAND.  (NEWSGROUP REPLY PREFERRED)
ianm[at]the[dash]malcolms[dot]freeserve[dot]co[dot]uk [at]=@, [dash]=- & 
[dot]=.
*Warning* SPAM TRAP set in header, Use email address in sig. if you must.

"Joerg" ha scritto nel messaggio news:5jbVg.19716$ snipped-for-privacy@newssvr14.news.prodigy.com...

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).

thanks everyone for their useful inputs ivan

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.

--Charles

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)

Bill

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:

To expand, here is the well tested, but retyped, 8080 code for the fast multiplication, dated 1982. Should be adaptable to other architectures. The routines are marked with registers disturbed as a comment. bmult is organized to keep multiplication time nearly constant.

; unsigned integer multiply ; operand range 0 to 65535, product 0 to 4295 * 10^6 (approx) ; d,e,h,l .imul: push psw mov a,e; low order multiplier byte push d; save h multiplier byte call bmult; do 1 byte mult xthl; save low order product, get multiplier push psw; store hi byte of 1st product mov a,h; hi order byte of multiplier call bmult; 2nd 1 byte multiply mov d,a; position hi order product byte pop psw hi order byte of 1st product add h; update 3rd byte of product mov e,a; to e jnc imul1 inr d; propagate carry imul1: mov a,l; low byte, 2nd product pop h; low 2 bytes, 1st product add h; combine mov h,a jnc poppsw inx d; propagate carry ; " " ; pop psw and exit poppsw: pop psw ret ; ; 8 bit by 16 bit unsigned multiplication ; (ahl) := (a) * (bc) ; (d) := (e) := 0 ; a,f,d,e,h,l bmult: lxi d,8; d := 0, e := bit ctr mov h,d mov l,d; clear hl add a; 1st multiplier bit to carry jnc bmult2; zero bit bmult1: dad b; 1 bit, add to partial product adc d; carry to (a) rh bit bmult2: dcr e rz; done dad h; left shift product adc a; into (a), mul bit to carry jc bmult1; bit is 1 jmp bmult2; bit is 0

--
"The mere formulation of a problem is far more often essential
 than its solution, which may be merely a matter of mathematical
 or experimental skill. To raise new questions, new possibilities,
 to regard old problems from a new angle requires creative
 imagination and and marks real advances in science."
                                               -- Albert Einstein