Author |
Topic: Complex Multiplication (Read 720 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Complex Multiplication
« on: Dec 5th, 2002, 8:58pm » |
 Quote  Modify
|
Consider computing the product of two complex numbers (a + bi) and (c + di). By foiling the polynomials as we learned in grade school, we get
a + bi
c + di
----------
adi - bd
ca + cbi
---------------
(ca - bd) + (ad + cb)i
Note that this standard method uses 4 multiplications and 2 additions to compute the product. (The plus sign in between (ca - bd) and (ad + cb)i does not count as an addition. Think of a complex number as simply a 2-tuple.)
It is actually possible to compute this complex product using only 3 multiplications and 3 additions. From a logic design perspective, this is preferable since multiplications are more expensive to implement than additions. Can you figure out how to do this?
Note: If you've heard of the algorithm already, don't give it away too soon; let others think about it for a while.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: Complex Multiplication
« Reply #1 on: Dec 6th, 2002, 2:45pm » |
Quote Modify
|
This is a nice problem, but do you think it belongs in "hard"?? I recall it as the first problem of the first problem set of an algorithms class I took in college. If I ever have time, I should try to bring some of the later problems here. They get much harder...
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
Jonathan Derrryberry
Guest
|
|
Re: Complex Multiplication
« Reply #3 on: Aug 11th, 2004, 12:11pm » |
Quote Modify
 Remove
|
I can't find a better way than 3 multiplications and 5 additions (even with googling). Can anyone give a hint, or is 3 multiplications and 3 additions a mistake?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Complex Multiplication
« Reply #4 on: Aug 13th, 2004, 10:55am » |
Quote Modify
|
William's question - posted more than 1.5 years ago - brings to my mind several related ones:
1. Multiply two square matrices A, B with as few multiplications as possible.
2. Evaluate a general n-degree polynomial (in one variable) with as few multiplications as possible.
3. Invert matrix A with as few divisions as possible.
Hope they will raise some interest.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Complex Multiplication
« Reply #5 on: Aug 14th, 2004, 11:23am » |
Quote Modify
|
This question has been in my unsolved list for a long time, unfortunate as it is .... i kinda feel embarassed at not solving this one by now 
I would like to keep Barukh's questions in buffer for a while till i see a way of doing the original question which seems like a long time affair to me.
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
amstrad
Newbie
Gender:
Posts: 10
|
|
Re: Complex Multiplication
« Reply #6 on: Dec 9th, 2004, 12:03pm » |
Quote Modify
|
I concur with Jonathan. I can find 3 and 5, but not 3 and 3.
consider:
if
( a + bi ) * ( c + di ) = (ac - bd) + (ad + bc)i
and
(a+b) * (c+d) = (ac + ad + bc + bd)
then:
(a + bi) * (c + di) = (ac - bd) +
( (a + b)*(c + d) - ac - bd )
written in pseudo-assembley:
add $a, $b, $100 # a + b
add $c, $c, $101 # c + d
mul $100, $101, $102 # (a + b)*(c + d)
mul $a, $c, $103 # a*c
mul $b, $d, $104 # b*d
sub $103, $104, $105 # real part: (ac - bd)
sub $102, $103, $106 # (a + b)*(c + d) - ac
sub $106, $104, $107 # imag part: (a + b)*(c + d) - ac - bd
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print