three numbers multiplied simultaneously ?

[legacy]

so,  I have already implemented the MAC booth aka multiplier and accumulate, a very useful algorithm that takes three parameters (A,B,C) and gives back the result result=A+(B*C)

now, you still have three numbers

fixed-point32bit_t A;
fixed-point32bit_t B;
fixed-point32bit_t C;

fixed-point32bit_t result;

and if want to multiply them A*B*C, then you would usually implement HDL code to calculate 

tmp=MUL(A,B)

... 35 clock's ticks later ...

 result=MUL(tmp,C)

but, in my case, I am looking for a trick (if it exists) to multiply one-shot, simultaneously

result=MUL(A,B,C)


Something magic like the MAC booth 

[Kalvin]

Have you tried that using a pen and paper? You may figure out how to do that, I guess.

[T3sl4co1l]

A*B*C would have to be done on each set of bits, then all the terms (there are O(N^3) of them now) summed.  That's going to be expensive not just in the number of gate inputs, but very much so in the number of full adders.  And, I think, about doubling the number of reduction stages (for a Wallace/Dadda multiplier architecture)?

Or repeating the operation serially, using twice as many cycles.  Maybe a little overlap can be saved (or pipelined), but I doubt a lot.

Since you've already implemented a MAC operation, why not cascade two, (A*B)*C = 0+(0+(A*B))*C?

Note that a triple product is extremely likely to overflow, given random possible input values.  Ideally you would have a 96 bit output!

35 clocks sounds rather inefficient/slow, unless this is something like a RISC CPU or FPGA, with no built in multiplier.  Or you're trying to save as much hardware as possible with serial logic.  In any case, the architecture matters very much, and it would be prudent to say what it is you're working on.

Tim

[legacy]

unless this is something like a RISC CPU or FPGA, with no built in multiplier

yup, this is the case.

[Tomorokoshi]

Oddball solution:

Depending on how clean the source data is, it's range, and how accurate the output data needs to be, a fast  10^(log(A) + log(B) + log(C)) converter would turn it into table look-ups and additions.

[legacy]

Oddball solution:

Depending on how clean the source data is, it's range, and how accurate the output data needs to be, a fast  10^(log(A) + log(B) + log(C)) converter would turn it into table look-ups and additions.

bingo! 

our(1) BKM-modified algorithm is perfectly able to compute the Log_10(x) as well as Log_e(x) in 40 clock's ticks for 32bit fixedpoint numbers.

the only problem is the range where it converges ... here I have to triple check


(1) developed by a Bulgarian girl employed at Google Switzerland. She is a great mathematician. I got her work described on paper and re-implemented in hardware.

[Kalvin]

Correct me if I am wrong, but performing the multiplication as test, add, and shift you will get an lsb out after first clock and subsequent bits after each clock cycle. Thus you should be able to construct some sort of chained multiplier which will take the lsb of the first multiplier as an input to the second multiplier with very little penalty in clock cycles.
Disclaimer: I didn't try this with pen and paper, so I may be terribly wrong here.

[asmi]

Have you tried using DSP tiles? They are specifically designed for fast MADDs (among other things).

[hamster_nz]

I discovered this paper: http://i.stanford.edu/pub/cstr/reports/csl/tr/94/617/CSL-TR-94-617.pdf

Very good coverage of fast multiplication for two numbers. But not at all relevant to your question

[legacy]

glad to see the "Booth" got mentioned and analyzed in the paper

[Kalvin]

Correct me if I am wrong, but performing the multiplication as test, add, and shift you will get an lsb out after first clock and subsequent bits after each clock cycle. Thus you should be able to construct some sort of chained multiplier which will take the lsb of the first multiplier as an input to the second multiplier with very little penalty in clock cycles.
Disclaimer: I didn't try this with pen and paper, so I may be terribly wrong here.

If one looks at figure 2.1 on page 29 in http://i.stanford.edu/pub/cstr/reports/csl/tr/94/617/CSL-TR-94-617.pdf one can see that my idea should be applicable.

[David Hess]

Oddball solution:

Depending on how clean the source data is, it's range, and how accurate the output data needs to be, a fast  10^(log(A) + log(B) + log(C)) converter would turn it into table look-ups and additions.

I was considered suggesting this but most people dismiss it.

In the distant past, I wrote a floating point library which worked this way for 8-bit microcontrollers.  It did lazy conversion between A and log(A).  The log and exponential conversions can be done completely with shifts and adds (so all multiplications, divisions, powers, and roots are reduced to shifts and adds) but I assume an FPGA would handle it in a different way.

[legacy]

The log and exponential conversions can be done completely with shifts and adds

with which algorithm?
Cordic-hybrid? BKM-modified?

our BKM-modified is unstable for certain sub-range (e.g. |teta|<pi/8) due to the range reduction's request for convergence.

[David Hess]

The log and exponential conversions can be done completely with shifts and adds

with which algorithm?
Cordic-hybrid? BKM-modified?

our BKM-modified is unstable for certain sub-range (e.g. |teta|<pi/8) due to the range reduction's request for convergence.

I used the algorithms Knuth described and simulated them first in Mathematica with integer math to verify proper operation.  It was so long ago that I do not remember any details other than having no problems with them and that they always produced one bit per loop so terminated just fine.  I do not remember a table being needed but the link I gave mentions one.

We never used the library although I rewrote it for myself later for use on PIC.