1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Binary multiplication

Discussion in 'C' started by Croatoan, Nov 14, 2010.

  1. Croatoan

    Croatoan New Member

    Joined:
    Nov 12, 2010
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    Can sb give me a tip for recursive multiplication of two binary numbers (their lenght is 2^n)! I need only recursive to implement it in c++ code,
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    What's recursive multiplication? Could you outline the algorithm, i.e. how would you do it on paper?
     
  3. Croatoan

    Croatoan New Member

    Joined:
    Nov 12, 2010
    Messages:
    3
    Likes Received:
    0
    Trophy Points:
    0
    x=xl * 2^(n/2)+xr (n=2^k, k e 1,2,3)
    y=yl * 2^(n/2)+yr

    x*y=xl * 2^(n/2) * yl * 2^(n/2) + xl * 2^(n/2) * yr +
    xr*yl * 2^(n/2) + xr*yr

    how to implement that in c++
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Where are you stuck?
    2^(n/2) appears to be a constant (let's say you put that in c), so the first equation
    x=xl*c+xr
    translates into C++ as
    x=xl*c+xr;

    You should be able to take it from there.
     

Share This Page