complex number multiplication
Author
Normally complex number multiplication use 4 multiply and 2 addition.
I heard there is a way to multiply it with 3 multiply and 3 addition.
Anybody know about it? Thanks in advance.
I can't imagin that being true, unless there is some sort of constraint on the number. could be wrong tho..
I guess if they are in polar form you can get away with 1 multiply and 1 add. Otherwise I don't know...
Don't know with 3 additions, but for 4 instead, you can use this formula.
Note than ac, bd and (ac - bd) can be calculated once and reused.
e = (a + ib)(c + id)Re(e) = ac - bdIm(e) = (a+b)(c+d) - ac - bdNote than ac, bd and (ac - bd) can be calculated once and reused.
IMHO, in cartesian co-ordinates
(a + ib) (c + id) = (ac - bd) + i (ad + bc)
what means 4 MUL and 3 ADD
or else in polar co-ordinates
a ei φ * b ei ψ = ab ei (φ + ψ)
what means 1 MUL and 1 ADD (but possibly with conversion overhead that beats the effort of cartesian multiplication largely)
or else similarly in trig. representation
a ( cos(φ) + i sin(φ) ) * b ( cos(ψ) + i sin(ψ) ) = ab ( cos(φ + ψ) + i sin(φ + ψ) )
what makes, no surprise, also 1 MUL and 1 ADD.
The way Brother Bob shows is a variation of the one shown at top here, that replaces 1 MUL by 2 ADDs.
IMHO it shows 3 MULs and 5 ADDs in total and not 3 MULs and 4 ADDs, as Brother Bob stated, since
- ac - bd != ac - bd = Re(e)
and hence the difference could not be re-used.
(a + ib) (c + id) = (ac - bd) + i (ad + bc)
what means 4 MUL and 3 ADD
or else in polar co-ordinates
a ei φ * b ei ψ = ab ei (φ + ψ)
what means 1 MUL and 1 ADD (but possibly with conversion overhead that beats the effort of cartesian multiplication largely)
or else similarly in trig. representation
a ( cos(φ) + i sin(φ) ) * b ( cos(ψ) + i sin(ψ) ) = ab ( cos(φ + ψ) + i sin(φ + ψ) )
what makes, no surprise, also 1 MUL and 1 ADD.
The way Brother Bob shows is a variation of the one shown at top here, that replaces 1 MUL by 2 ADDs.
IMHO it shows 3 MULs and 5 ADDs in total and not 3 MULs and 4 ADDs, as Brother Bob stated, since
- ac - bd != ac - bd = Re(e)
and hence the difference could not be re-used.
Quote:Original post by haegarr
The way Brother Bob shows is a variation of the one shown at top here, that replaces 1 MUL by 2 ADDs.
IMHO it shows 3 MULs and 5 ADDs in total and not 3 MULs and 4 ADDs, as Brother Bob stated, since
- ac - bd != ac - bd = Re(e)
and hence the difference could not be re-used.
Correct, I was wrong on that point. It should be 5 additions, not 4.
A complex multiplication method which I have seen uses 3 mul and 3 add is specialised for usage in Fast Fourier transform.
There is another method which is called Buneman's method which in rotating a complex number by theta, uses 3 mul and 3 add.
Both the above methods use lookup tables of some sort.
The 3 mul 5 add which brother bob showed is called Golub's method.
There is another method which is called Buneman's method which in rotating a complex number by theta, uses 3 mul and 3 add.
Both the above methods use lookup tables of some sort.
The 3 mul 5 add which brother bob showed is called Golub's method.
Quote:
There is another method which is called Buneman's method which in rotating a complex number by theta, uses 3 mul and 3 add.
Of course, you'd need some trig to extract the angles.
I'd think the traditional way is quickest if your numbers are changing or unpredictable. I'd think any other method would need trig to extract angles? I guess it depends on the application. if you can always represent them in that way(like ee stuff) then it's cool.
Tim
Author
Thank you very much for all your response.
Aryabhatta is correct i have seen it mention in fft paper but i can't access it reference. Do you guys have any link to it? Or could you explane a little more? Thanks in advanced.
BTW. Big thanks to Brother Bob I never though that method exist ^_^" that's something new for me.
Aryabhatta is correct i have seen it mention in fft paper but i can't access it reference. Do you guys have any link to it? Or could you explane a little more? Thanks in advanced.
BTW. Big thanks to Brother Bob I never though that method exist ^_^" that's something new for me.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
