Multiplying with divide and conquer

Question

Below I've posted the code to a non-working "divide and conquer" multiplication method in ruby(with debug prints). I cannot tell if its broken code, or a quirk in Ruby like how the L-shift(<<) operator doesn't push bits into the bit-bucket; this is unexpected compared to similar operations in C++.

Is it broken code (doesn't match the original algorithm) or unexpected behavior?

Pseudo code for original algorithm

def multiply(x,y,n, level)
    #print "Level #{level}\n"
    if n == 1
        #print "\tx[#{x.to_s(2)}][#{y.to_s(2)}]\n\n"
        return x*y
    end
    mask = 2**n - 2**(n/2)

    xl = x >> (n / 2)
    xr = x & ~mask
    yl = y >> (n / 2)
    yr = y & ~mask


    print "  #{n} | x =  #{x.to_s(2)} = L[#{xl.to_s(2)}][#{xr.to_s(2)}]R \n"
    print "  #{n} | y =  #{y.to_s(2)} = L[#{yl.to_s(2)}][#{yr.to_s(2)}]R \n"
    #print "\t[#{xl.to_s(2)}][#{yr.to_s(2)}]\n"
    #print "\t[#{xr.to_s(2)}][#{yr.to_s(2)}]\n"
    #print "\t([#{xl.to_s(2)}]+[#{xr.to_s(2)}])([#{yl.to_s(2)}]+[#{yr.to_s(2)}])\n\n"

    p1 = multiply(  xl,     yl,     n/2,    level+1)
    p2 = multiply(  xr,     yr,     n/2,    level+1)
    p3 = multiply(  xl+xr,  yl+yr,  n/2,    level+1)

    return p1 * 2**n + (p3 - p1 - p2) * 2**(n/2) + p2
end


x = 21
y = 22
print "x = #{x} = #{x.to_s(2)}\n"
print "y = #{y} = #{y.to_s(2)}\n"

print "\nDC_multiply\t#{x}*#{y} = #{multiply(x,y,8, 1)} \nregular\t#{x}*#{y} = #{x*y}\n\n "

Answer 1

I am not familiar with the divide and conquer algorithm but i don't think it contains parts you can't do in Ruby.

Here is a quick attempt:

def multiplb(a,b)
  #Break recursion when a or b has one digit
  if a < 10 || b < 10
    a * b
  else
    #Max number of digits of a and b
    n = [a.to_s.length, b.to_s.length].max

    # Steps to split numbers to high and low digits sub-numbers
    # (1) to_s.split('') => Converting digits to string then arrays to ease splitting numbers digits 
    # (2) each_slice => Splitting both numbers to high(left) and low(right) digits groups
    # (3) to_a , map, join, to_i => Simply returning digits to numbers
    al, ar = a.to_s.split('').each_slice(n/2).to_a.map(&:join).map(&:to_i)
    bl, br = b.to_s.split('').each_slice(n/2).to_a.map(&:join).map(&:to_i) 

    #Recursion
    p1 = multiplb(al, bl)
    p2 = multiplb(al + ar, bl + br)
    p3 = multiplb(ar, br)

    p1 * (10**n) + (p2 - p1 - p3) * (10**(n/2)) + p3
  end

end
#Test
puts multiplb(1980, 2315)
# => 4583700  yeah that's correct :)

Here are some references to further explain part of the code:

1. Finding max of numbers => How do you find a min / max with Ruby?

2. Spliting an array to half => Splitting an array into equal parts in ruby

3. Turning a fixnum into array => Turning long fixed number to array Ruby

Hope it hepls !