6
\$\begingroup\$

I've written an algorithm for integer multiplication using the Karatsuba method in C++. This implementation is far from ideal, so any comments are welcome.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cstring>

const int MAX_LENGTH = 50000 * 2 + 1;

void add_leading_zeros(char* a, int n) {
  int lena = strlen(a);
  for (int i = lena - 1 + n; i >= n; --i) {
    a[i] = a[i - n];
  }
  a[lena + n] = 0;
  for (int i = 0; i < n; ++i) {
    a[i] = '0';
  }
}

void remove_leading_zeros(char* a) {
  int lena = strlen(a);
  int ind = 0;
  while (ind < lena && a[ind] == '0') {
    ++ind;
  }

  for (int i = ind; i < lena; ++i) {
    a[i - ind] = a[i];
  }
  a[lena - ind] = 0;
}

void sum(char* a, char* b, char* res) {
  int lena = strlen(a);
  int lenb = strlen(b);

  if (lena < lenb) {
    std::swap(a, b);
    std::swap(lena, lenb);
  }

  int toAdd = 0;
  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {
    int x = a[inda] - '0';
    int y = indb >= 0 ? b[indb] - '0' : 0;

    int cur = x + y + toAdd;

    if (cur >= 10) {
      toAdd = 1;
      cur -= 10;
    } else {
      toAdd = 0;
    }

    res[inda] = cur + '0';
  }

  if (toAdd == 1) {
    add_leading_zeros(res, 1);
    res[0] = '1';
  }
}

// assume that a > b
void sub(char* a, char* b, char* res) {
  int lena = strlen(a);
  int lenb = strlen(b);

  //assert(lena >= lenb);

  int toSub = 0;
  for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {
    int x = a[inda] - '0';
    int y = indb >= 0 ? b[indb] - '0' : 0;

    if (toSub == 1) {
      x--;
    }
    int cur;
    if (x < y) {
      cur = x + 10 - y;
      toSub = 1;
    } else {
      cur = x - y;
      toSub = 0;
    }

    res[inda] = cur + '0';
  }
}

// returns a * 10^n
void mult10(char* a, int n) {
  int lena = strlen(a);

  if (lena == 1 && a[0] == '0') {
    return;
  }

  for (int i = lena; i < lena + n; ++i) {
    a[i] = '0';
  }
  a[lena + n] = 0;
}

char* CreateArray(int len) {
  char* res = new char[len];
  memset(res, 0, len);
  return res;
}

// add leading zeros if needed
void make_equal_length(char* a, char* b) {
  int lena = strlen(a);
  int lenb = strlen(b);

  int n = std::max(lena, lenb);

  add_leading_zeros(a, n - lena);
  add_leading_zeros(b, n - lenb);
}

void karatsuba(char* x, char* y, char* res) {
  make_equal_length(x, y);

  int len = strlen(x);
  if (len == 1) {
    int val = (x[0] - '0') * (y[0] - '0');
    if (val < 10) {
      res[0] = val + '0';
    } else {
      res[0] = (val / 10) + '0';
      res[1] = (val % 10) + '0';
    }
  } else {
    char* xl = CreateArray(len);
    char* xr = CreateArray(len);
    char* yl = CreateArray(len);
    char* yr = CreateArray(len);

    int rightSize = len / 2;
    int leftSize = len - rightSize;

    strncpy(xl, x, leftSize);
    strcpy(xr, x + leftSize);
    strncpy(yl, y, leftSize);
    strcpy(yr, y + leftSize);

    int maxl = 3 * len;
    char* P1 = CreateArray(maxl);
    char* P2 = CreateArray(maxl);
    char* P3 = CreateArray(maxl);

    karatsuba(xl, yl, P1);
    karatsuba(xr, yr, P2);

    char* tmp1 = CreateArray(maxl);
    char* tmp2 = CreateArray(maxl);

    sum(xl, xr, tmp1);
    sum(yl, yr, tmp2);
    karatsuba(tmp1, tmp2, P3);

    sub(P3, P1, P3);
    sub(P3, P2, P3);
    mult10(P3, rightSize);

    mult10(P1, 2 * rightSize);

    sum(P1, P2, res);
    sum(res, P3, res);

    remove_leading_zeros(res);

    delete[] xl;
    delete[] xr;
    delete[] yl;
    delete[] yr;
    delete[] tmp1;
    delete[] tmp2;
    delete[] P1;
    delete[] P2;
    delete[] P3;
  }
}

int main() {
  char a[MAX_LENGTH], b[MAX_LENGTH];
  scanf("%s\n%s", a, b);

  char* res = CreateArray(MAX_LENGTH);
  karatsuba(a, b, res);

  printf("%s\n", res);

  scanf("%d", 1);

  return 0;
}
\$\endgroup\$
  • 5
    \$\begingroup\$ This mostly looks like C, especially with all this dynamic memory allocation. Is this intentional? \$\endgroup\$ – Jamal Oct 3 '14 at 20:33
  • \$\begingroup\$ @Jamal, yes, because I prefer using C strings. \$\endgroup\$ – pfedotovsky Oct 3 '14 at 20:35
  • 1
    \$\begingroup\$ @pfedotovsky, you can check this one habrahabr.ru/post/124258 code goes below description \$\endgroup\$ – outoftime Oct 3 '14 at 20:54
  • \$\begingroup\$ en.wikipedia.org/wiki/Karatsuba_algorithm \$\endgroup\$ – bhathiya-perera Oct 4 '14 at 3:54
  • 2
    \$\begingroup\$ Why are you doing biginteger arithmetic in base10 instead of binary? \$\endgroup\$ – CodesInChaos Oct 4 '14 at 8:23
12
\$\begingroup\$

If you prefer programming in C-style, I suggest to use C. If you want to use any part of C++, I suggest to embrace it fully.

I'll review only the main method for now, I'm sure a lot more reviews will come from others.


You don't need the \n here. You can just drop it, it will work the same way:

  scanf("%s\n%s", a, b);

The C++ equivalent:

std::cin >> a >> b;

This generates a compiler warning, for good reason: the arguments of scanf should be pointers, but it's an int. Why is this line there at all? I suggest to remove it.

  scanf("%d", 1);
\$\endgroup\$
  • 4
    \$\begingroup\$ "If you want to use any part of C++, I suggest to embrace it fully." ... +1 ... I always ask the C heads to consider the points made in Learning Standard C++ as a New Language for starters. \$\endgroup\$ – HostileFork Oct 4 '14 at 12:21
8
\$\begingroup\$

Some random observations:

  • toAdd and toSub are traditionally called carry. Consider renaming.

  • sub assumes that a > b. Does this assumption hold? In general, I don't see any provision to deal with negative numbers.

  • Keeping digits as ascii, and converting them back and forth at each operation seems wasteful, both time and space wise.

  • By using C-style arrays you are forced to track the length separately. I strongly recommend to switch to std::vector.

  • sum would fail when adding strings of the same length (inda becomes -1 after the loop termination). In general I don't think the decision to keep most significant digit at the index 0 is justified.

  • sum apparently doesn't let its parameters to be aliased (you can't sum(x, y, x)), which leads to many unnecessary allocations.

\$\endgroup\$
6
\$\begingroup\$

Separate your #includes by type and order them alphabetically if possible. E.g.: Put all the C library headers together and all the C++ headers together (the C library ones are those starting with a c: <cstdlib>, <cstdio>, etc).


Your naming convention is not fully consistent. Most of the code uses snake_case, but you have some camelCase as well:

int toSub;
CreateArray();

You should be fully consistent with your choice:

int to_sub;
create_array();

You don't have to return 0 from main(). The compiler will add that for you if you don't explicitly do so.


Currently, your code uses very few C++ features. I would suggest moving completely to plain C (basically just replacing new/delete with malloc/free).

\$\endgroup\$
6
\$\begingroup\$

One problem with combining C and C++ is that others may not know for sure if you're really trying to combine both for whatever reason, or if you think they're the same (some aren't aware that they're two separate languages). The use of delete signifies C++, but then you have several lines of deletes in one of the functions, which is not good practice in C++ as you have the standard library that manages the memory for you. You could fail to deallocate something yourself, causing a memory leak.

Actually, it already happens with res that gets allocated in CreateArray(). Who is responsible for its deletion now? Certainly not CreateArray(), as it returns the array and leaves scope. You should just allocate the arrays within the calling function and then deallocate from there. Yes, this is a concern when you have to manage your own memory in non-garbage-collected languages like C and C++.

It's also hard to tell what karatsuba() is doing algorithmic-wise. It lacks commenting and appears to do a lot of memory management. If you cannot improve it in C, then you may have to do it only in C++ while utilizing the standard library.

\$\endgroup\$
  • \$\begingroup\$ the char *x = CreateArray(n); lines can be replaced by vector<char> x(n); at practically no cost. It's easy to transition step-by-step since x.data() returns a char * pointer the C-style code can use. \$\endgroup\$ – pascal Oct 4 '14 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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