4
\$\begingroup\$

I am working my way through an algorithms course online, and the assignment is to implement Karatsuba's multiplication algorithm. I am also trying to practice C++, so I wanted to implement it in that language. Looking online, I notice a lot of people solve this using strings.
Is there a benefit to doing that?
If so, can somebody please explain how my code might be optimized or improved by doing that?

I've included my unit tests below, which I wrote using the catch framework.

#include <math.h>
#include <cmath>
#include <stdlib.h>
#include <stdio.h>
#include "catch.hpp"

int left (int num, int n) {
    if (n < 2) {
        printf("left received n < 2");
        exit (EXIT_FAILURE);
    }
    return num / pow(10, n / 2);
}

int right (int num, int left, int n) {
    if (n < 2) {
        printf("right received n < 2");
        exit (EXIT_FAILURE);
    }
    return num - (left * pow(10, n / 2));
}

int karatsuba_multiply (int x, int y) {
    if (x < 1 || y < 1) {
        return 0;
    }
    // base case: x and y are single digits, multiply normally
    int num_digits = int(log10(x)) + 1; 
    if (num_digits == 1) {
        return x * y;
    }

    int a = left(x, num_digits);
    int b = right(x, a, num_digits);
    int c = left(y, num_digits);
    int d = right(y, c, num_digits);

    int p = a + b;
    int q = c + d;

    int ac = karatsuba_multiply(a, c);
    int bd = karatsuba_multiply(b, d);
    int pq = karatsuba_multiply(p, q);

    int adbc = pq - ac - bd;

    return pow(10, num_digits) * ac + pow(10, num_digits / 2) * adbc + bd;
}

TEST_CASE("multiplies numbers", "[karatsuba]") {
    REQUIRE(karatsuba_multiply(3, 4) == 12);
    REQUIRE(karatsuba_multiply(0, 5) == 0);
    REQUIRE(karatsuba_multiply(12, 12) == 144);
    REQUIRE(karatsuba_multiply(10, 15) == 150);
    REQUIRE(karatsuba_multiply(1234, 1473) == 1817682);
}

TEST_CASE("helpers", "[karatsuba_helpers]") {
    SECTION("left") {
        REQUIRE(left(53, 2) == 5);
        REQUIRE(left(1555, 4) == 15);
        REQUIRE(left(123456, 6) == 123);
    }

    SECTION("right") {
        REQUIRE(right(53, 5, 2) == 3);
        REQUIRE(right(1555, 15, 4) == 55);
        REQUIRE(right(123456, 123, 6) == 456);
    }
}
\$\endgroup\$
10
  • \$\begingroup\$ Is there a benefit to [using strings for "bignums"]? (C++) string length is not "artificially" limited. Note that 1) if the multiplication was the only operation to perform, conversion of the product from binary to decimal looks something to avoid: use an even power of 10 handled easily by the target processor 2) with multiplication speed an issue, that processor may be much smaller than a contemporary computer CPU. \$\endgroup\$
    – greybeard
    Mar 6, 2022 at 11:59
  • \$\begingroup\$ (I spot one all-too-common error in "the final scaling".) \$\endgroup\$
    – greybeard
    Mar 6, 2022 at 12:01
  • \$\begingroup\$ @greybeard What is the error? And would you expand more on your earlier comment, please? I’m not sure I understand. \$\endgroup\$
    – nickhealy
    Mar 6, 2022 at 12:16
  • 1
    \$\begingroup\$ For bases not powers of a common divisor, the most common conversion uses division - by a smallish number (the target base), but not that simpler compared to multiplication. I'm not current regarding C++ bignum support. \$\endgroup\$
    – greybeard
    Mar 6, 2022 at 13:38
  • 2
    \$\begingroup\$ my solution doesn’t really account for numbers of different length The main problem is (num_digits / 2) * 2 != num_digits for odd num_digits. Note you get different length easily: 1001*1111. \$\endgroup\$
    – greybeard
    Mar 6, 2022 at 21:26

1 Answer 1

4
\$\begingroup\$

Avoid mixing C and C++

You say you are practicing C++, but you use a lot of C code. While you can use most of C in a C++ program, try to avoid it.

  • Instead of printf("hello\n"), write std::cout << "hello\n". If you want to use printf()-like formatting, then since C++20 you can use std::format().
  • Prefix the math functions with std::. This will get you the C++ versions of these functions, which often have overloads for different types that might make them more efficient, for example by exploiting the fact that you are trying to raise something to an integer power.
  • If you do need C functions, use the header files that are prefixed with a c, like <cmath> instead of <math.h>, <cstdlib> instead of <stdlib.h>, and so on.

Avoid using floating point functions if all you need is integers

Your code is multiplying integer numbers, but pow() and log10() are returning doubles. This causes a lot of unnecessary conversions between integers and floating point numbers, which is relatively cheap on modern processors, but still not free.

pow(10, n) can be replaced by an array lookup into a precomputed table of powers of 10. log10() is trickier, but see this StackOverflow question for possible solutions.

Even better is not to have to need these functions at all:

Avoid working in base-10

Humans typically use the decimal numeral system, but this is actually not nice for computers, which due to their binary nature, likes to see things in powers of 2. If you would implement your multiplication algorithm using hexadecimal digits, then you can do the equivalent of pow(16, n) using 1 << (n * 4), which is just two bit shift operations, which are very efficient on most CPUs. The equivalent of int(log16(x)) would be (std::bit_width(x) - 1) / 4.

However, even better would be to leave multiplying whole ints to the CPU, which is very good at that, and use the Karatsuba algorithm to multiply even larger numbers.

What about negative numbers?

Your function accepts two int values. An int can be negative. However, trying to multiply two numbers of which at least one is negative will always result in 0 with your code. This might surprise a user. Either decide not to allow negative numbers at all, which you can do by using unsigned ints instead, or allow it but then ensure you handle them correctly.

Use assert() to check for things that should never happen

In left() and right(), you check if n < 2, and exit immediately if so. It looks like this situation should never occur though, and these checks are just there to guard against programming errors. This is a good practice, but in that case, use assert(). Apart from being more compact to write, it signals that this is intended to check for programming errors, and the checks can be easily disabled by defining NDEBUG while compiling. So:

assert(n < 2);

Note that assert() will actually call abort() instead of exit(EXIT_FAILURE), which is better since it can trigger a core dump, or if it is run inside a debugger, the debugger will see that this is an error instead of a regular program exit.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Interestingly, the code does include <cmath> - in addition to <math.h>! That suggests some confusion over the role of the C and C++ headers, and the differences between them. \$\endgroup\$ Mar 7, 2022 at 13:49

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.