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 "

right because it just shift things to the left(forever) so I made a mask and 'anded' off the upper half — Aage Torleif, Oct 17 '14 at 06:23
Your code outputs a lot of debug data. What's the expected output / behavior? — Stefan, Oct 17 '14 at 06:35
Ultimately is should do multiplication. The algorithm is recursive, so it creates a tree-like "pattern" through the call stack, which can also be seen by the amount of bits (n) and the right/left split of each x and y. — Aage Torleif, Oct 17 '14 at 06:38
Sure, but how does the debug output differ from a C++ implementation? — Stefan, Oct 17 '14 at 06:40
There is no c++ implementation I have. There is a difference about how the language implements value types, the << was one oddity I found. I'm looking to see if things of a similar nature are causing bad results, or the code is just bonked which may be the case. I had a textbook with pseudo code next to me, I thought it looked much like ruby and decided to copy it, rather verbatim. — Aage Torleif, Oct 17 '14 at 06:53

score 1 · Accepted Answer · edited May 23 '17 at 12:20

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:

Finding max of numbers => How do you find a min / max with Ruby?
Spliting an array to half => Splitting an array into equal parts in ruby
Turning a fixnum into array => Turning long fixed number to array Ruby

Hope it hepls !

Oh, right. Yea this doesn't work but here's the problem. ``if a.to_s.length == 1 || b.to_s.length == 1 a * b`` because p2 can have a carry bit. Mine wasn't catching the carry and shifting it off. I guess the proper way would be to check the to_s(2) length to get n. — Aage Torleif, Oct 17 '14 at 07:57
p1 * (10**n) + (p2 - p1 - p3) * (10**(n/2)) + p3 but that's perfect, thank you — Aage Torleif, Oct 17 '14 at 08:01

Multiplying with divide and conquer

1 Answers1