2

So I am implementing Karatsuba's multiplication algorithm in python. Right now I have infinite recursion and cannot figure it out. Any ideas? I will provide more code if needed.

  def multiply(self, other):


  # helper function
    def split(largeInt, n):
     least = largeInt._least_significant_digits(n/2)
     most = largeInt._right_shift(n/2)
     if debug: assert least.to_int() + (most.to_int() << (LargeInt.base_bits*(n/2))) == largeInt.to_int()
     return least, most
  n = max(len(str(self)),len(str(other)))
  if (n==1):
     return self.to_int() * other.to_int()
  else:
     aR, aL = split(self,n)
     bR , bL = split(other, n)
     x1 = aL.multiply(bL)
     x2 =aR.multiply(bR)
     a = aL.add(bL)
     b = aR.add(bR)
     x3=a.multiply(b)
  # code for recursive step here
  #return 1 # change this line with your implementation
  return  x1 * 10**n + (x3-x1-x2) * 10**(n/2) + x2
Improve this question
6
  • 1
    The code has comments like "TODO: your implementation here" and "code for base case here" in it. It also has return 2 immediately before the actual Karatsuba code. Have you posted the correct code here?
    – Gareth McCaughan
    Commented May 1, 2012 at 1:34
  • 2
    this code needs to be indented correctly.
    – deebee
    Commented May 1, 2012 at 1:38
  • I see you've put some diagnostic print statements in the code. What do they show? What values are being passed into multiply once you get deep into the infinite recursion? Are you certain that the large-integer methods you're calling do what you want? Is n/2 producing an integer or a float, and if the latter is it bad?
    – Gareth McCaughan
    Commented May 1, 2012 at 1:38
  • 1
    I figured it out, n = max(len(str(self)),len(str(other))) needed to be n = max(len(self.digits),len(other.digits)), casting it to a string broke the largeInt class I am using.
    – Marty Griffin
    Commented May 1, 2012 at 2:54
  • 2
    @MartyGriffin: Post your solution as an answer. You can and should answer your own questions.
    – Joel Cornett
    Commented May 1, 2012 at 3:50

2 Answers 2

Reset to default
1

Some hints:

  • I don't think your values for a, b, are what you want them to be.
  • A common error is often that split doesn't return strictly smaller numbers : please provide source for _least_significant_digits, _right_shift.
  • What happens when one of your inputs is of length 1, but not the other ? What does split return for the 1-digit number in that case ?
Improve this answer
0

I was calculating the max length of the number being passed in, doing it this way fixed it. 

   n = max(len(self.digits),len(other.digits))
Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.