# Binary multiplication

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

1. ### CroatoanNew Member

Joined:
Nov 12, 2010
Messages:
3
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. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
63
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. ### CroatoanNew Member

Joined:
Nov 12, 2010
Messages:
3
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. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,012
203
Trophy Points:
63
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.