0

I am currently working on an implementation of a recursive karatsuba multiplication method in C. I have all of the code working, and I have already optimized various aspects in my code (mostly memory). The only thing I have not touched are my addition and subtraction methods. I am currently just using the grade school method in base 2 ^ 32 (as is the rest of my code). Are there any faster algorithms for addition and subtraction that I could use?

Chaz
  • 73
  • 1
  • 7
  • No, that algorithm is already single-pass O(n). There's no faster algorithm. You might want to take advantage of hardware-flags and special instructions (carry: add adc sub sbc rsb). – Deduplicator Nov 15 '14 at 09:31
  • So you touched getting rid of multiplication in favor of squaring using (a+b)² - (a-b)²? – greybeard Nov 15 '14 at 09:42
  • I have the grade school multiplication method handling the small cases. What do you mean? @greybeard – Chaz Nov 15 '14 at 09:57
  • 1
    In my general Karatsuba implementation I have separate methods for (x * y) and (x * x). You can do a lot of further optimizing if you are squaring a number. – rossum Nov 15 '14 at 15:01
  • 1
    @Chaz look here: http://stackoverflow.com/q/18465326/2521214 and here: http://stackoverflow.com/a/26603589/2521214 for more ideas ... – Spektre Nov 15 '14 at 17:06
  • That didn't even cross my mind. That's a great idea! Thanks! – Chaz Nov 15 '14 at 19:30

0 Answers0