hi,

If I dont have a HW multiply instruction, will I need to use looped ADD instruction, or is there a more efficient way of doing it?

thanks Ivan

- posted
16 years ago

hi,

If I dont have a HW multiply instruction, will I need to use looped ADD instruction, or is there a more efficient way of doing it?

thanks Ivan

Loading thread data ...

- posted
16 years ago

Yes, shift and conditionally add is one possibility.

Jon

- posted
16 years ago

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

- posted
16 years ago

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

- posted
16 years ago

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.

- posted
16 years ago

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]=- &

Click to see the full signature

- posted
16 years ago

"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

- posted
16 years ago

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

- posted
16 years ago

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

- posted
16 years ago

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

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:

- posted
16 years ago

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

Click to see the full signature

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.