Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Complex numbers


  • Please log in to reply
7 replies to this topic

#1 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1662 posts
  • Gender:Female

Posted 26 February 2014 - 05:26 PM

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?

  • -1

#2 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5575 posts
  • Gender:Male
  • Location:New York

Posted 27 February 2014 - 11:06 AM

I can do it with 3 multiplications and 4 additions. Still looking.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#3 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5575 posts
  • Gender:Male
  • Location:New York

Posted 04 March 2014 - 12:17 PM

Spoiler for How about


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#4 harey

harey

    Junior Member

  • Members
  • PipPip
  • 80 posts
  • Gender:Male

Posted 11 March 2014 - 10:02 PM

@bmad
As nobody found the solution, can you post it?
  • 0

#5 harey

harey

    Junior Member

  • Members
  • PipPip
  • 80 posts
  • Gender:Male

Posted 13 March 2014 - 12:48 PM

@bonanova - sorry, but I believe you have a sign error with the factor bd:
I = (a+b)(c+d) - R =ac+bc+ad+bd - (ac - bd) ... = ... +2*bd ....

Edited by harey, 13 March 2014 - 12:50 PM.

  • 0

#6 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5575 posts
  • Gender:Male
  • Location:New York

Posted 13 March 2014 - 04:14 PM

@bonanova - sorry, but I believe you have a sign error with the factor bd:
I = (a+b)(c+d) - R =ac+bc+ad+bd - (ac - bd) ... = ... +2*bd ....

 

Right. It's (a+b)(c+d) - ac - bd.


  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#7 BMAD

BMAD

    Senior Member

  • Members
  • PipPipPipPip
  • 1662 posts
  • Gender:Female

Posted 13 March 2014 - 04:46 PM

Spoiler for my solution

  • 0

#8 harey

harey

    Junior Member

  • Members
  • PipPip
  • 80 posts
  • Gender:Male

Posted 15 March 2014 - 03:27 PM

If our hardware uses fewer clock cycles to perform three additions than a single multiplication, we may well gain overall processing speed by using Eq. (2-4) and Eq. (2-5) instead of Eq. (1-2) for complex multiplication


If it worked, it would be great for fractal pictures. The bad news is that multiplications are in the processor heavily optimized, a fair guess 4-5 additions. Googling:

The latency is 1 cycle for an integer addition and 3 cycles for an integer multiplication. You can find the latencies and thoughput in Appendix C of the "Intel 64 and IA-32 Architectures Optimization Reference Manual", which is located on http://www.intel.com...cessor/manuals/.


The big question is how the 3 temporary variables were treated by the compiler. If we have to access the RAM...
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users