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?

6
  • 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). Nov 15, 2014 at 9:31
  • So you touched getting rid of multiplication in favor of squaring using (a+b)² - (a-b)²?
    – greybeard
    Nov 15, 2014 at 9:42
  • I have the grade school multiplication method handling the small cases. What do you mean? @greybeard
    – Chaz
    Nov 15, 2014 at 9: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, 2014 at 15:01
  • 1
    @Chaz look here: stackoverflow.com/q/18465326/2521214 and here: stackoverflow.com/a/26603589/2521214 for more ideas ...
    – Spektre
    Nov 15, 2014 at 17:06

0

Your Answer

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

Browse other questions tagged or ask your own question.