current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
stack overflow careers
Sign up ×
Stack Overflow is a community of 4.7 million programmers, just like you, helping each other. Join them, it only takes a minute:
up vote 2 down vote favorite

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
share|improve this question
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 May 1 '12 at 1:34
2  
this code needs to be indented correctly. – deebee May 1 '12 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 May 1 '12 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 May 1 '12 at 2:54
2  
@MartyGriffin: Post your solution as an answer. You can and should answer your own questions. – Joel Cornett May 1 '12 at 3:50

2 Answers 2

up vote 1 down vote

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 ?
share|improve this answer
up vote 0 down vote accepted

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))
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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