5
\$\begingroup\$

I was using Karatsuba algorithm to multiply two polynomials and return the coefficients and I am using java, we are asked to use arraylists here, however, my code is too complicated and it takes much longer to run than I expected, can anyone help me with reducing the running time and simplify my code? Thanks a lot!

public static List<Long> smellCosmos(List<Long> a, List<Long> b) {
    int n = a.size();
    int n1 = a.size() / 2;

    List<Long>c = new ArrayList<Long>();

    if (n == 1) {
        c.add(0, a.get(0) * b.get(0));
        return c;
    };

    List<Long>ahigh = new ArrayList<Long>(n1);

    List<Long>alow = new ArrayList<Long>(n1);

    List<Long>amed = new ArrayList<Long>(n1);

    List<Long>bhigh = new ArrayList<Long>(n1);

    List<Long>blow = new ArrayList<Long>(n1);

    List<Long>bmed = new ArrayList<Long>(n1);

    for (int i = 0; i < n1; i++) {
        ahigh.add(a.get(i));
        alow.add(a.get(i + n1));
        amed.add(alow.get(i) + ahigh.get(i));
        bhigh.add(b.get(i));
        blow.add(b.get(i + n1));
        bmed.add(blow.get(i) + bhigh.get(i));
    }

    List<Long>chigh = smellCosmos(ahigh, bhigh);
    List<Long>clow = smellCosmos(alow, blow);
    List<Long>cmed = smellCosmos(amed, bmed);

    for (int j = 0; j < n1; j++)
        c.add(chigh.get(j));

    for (int m = 0; m < cmed.size(); m++)
        c.add(cmed.get(m) - chigh.get(m) - clow.get(m));

    for (int g = cmed.size() - n1; g < clow.size(); g++)
        c.add(clow.get(g));

    for (int i = n1; i < chigh.size(); i++)
        c.set(i, c.get(i) + chigh.get(i));

    for (int i = 0; i < cmed.size() - n1; i++)
        c.set(n1 * 2 + i, c.get(n1 * 2 + i) + clow.get(i));


    return c;

}
```
\$\endgroup\$
7
  • \$\begingroup\$ @RolandIllig Title has been edited. \$\endgroup\$
    – pacmaninbw
    Jun 11, 2020 at 0:35
  • 2
    \$\begingroup\$ In case a is guaranteed to be no shorter than b: document it in the code! \$\endgroup\$
    – greybeard
    Jun 11, 2020 at 2:55
  • 3
    \$\begingroup\$ (Can you please add/hyperlink test cases/input&expected output?) There is subList​(int fromIndex, int toIndex). \$\endgroup\$
    – greybeard
    Jun 11, 2020 at 3:07
  • 1
    \$\begingroup\$ en.wikipedia.org/wiki/Karatsuba_algorithm ; \$\endgroup\$ Jun 11, 2020 at 12:35
  • 1
    \$\begingroup\$ I tried with example from wikipedia and seems not working with it. I join greybeard's request : please provide test cases/input & expected output. \$\endgroup\$ Jun 11, 2020 at 15:50

2 Answers 2

1
\$\begingroup\$

Reduce running time

  • Maybe you can use subList to prevent new lists that are basically a copy of a part of the input? This saves a lot of autoboxing (which I assume is the bottle neck, if the algorithm is implemented correctly). You could profile your application to see where most time is spend.

For example: ahigh = a.subList(0,n1);

  • You can initialize List c with a size, as you know the length it will be.

  • Use addAll whenever you can, it will use the faster System.arrayCopy internally if possible.

\$\endgroup\$
0
\$\begingroup\$

As it happens, there is already an implementation of Karatsuba multiplication in the implementation of BigInteger. Of course that's integer multiplication instead of polynomial multiplication, but they're very similar, apart from how they handle carries. You can read the source here, look for multiplyKaratsuba. It's more of a high-level implementation, delegating the details of extracting the high/low halves and addition and the base-case multiplication. There are some things to learn from it, for example:

  • It uses int[], not ArrayList<Long>. int[] instead of long[] is used because multiplying two longs is actually difficult, the lowest 64 bits of the result are easy enough to get, but what about the upper 64 bits? That detail is not important for polynomial multiplication, as there is no carry propagation to worry about. You could use long[], which is a flat array of data, whereas ArrayList<Long> is an array of pointers to individually allocated Longs, that's a significant amount of size overhead (2x to 3x) and is also associated with hard-to-profile time overhead (the cost of loading more data and following more pointers and allocating/GC-ing more objects is diffuse, it does not show up as a hot spot during profiling).
  • The base case is not "a single element". Karatsuba multiplication is asymptotically faster than standard quadratic-time multiplication, but also has more overhead. For small inputs Karatsuba is slower, so it should only be used above some size threshold (which can be found experimentally).

Bugs

The current implementation does not deal with different-sized a and b. If b is longer, the extra part is cut off. If a is longer, well, that's a problem.

Even if the original input a and b were the same size, the algorithm would normally be able to create different sized inputs to its recursive calls: when the size is uneven that would naturally happen, unless you add padding. That does not happen here, if the size of a is uneven one element is dropped.

Unusual ordering

It seems that the name high is given to the start of the array/list. Normally the low part would be there, so that polynomial[i] corresponds to the coefficient of xi. That way it is for example easier to add two polynomials, because the coefficients at the same index in the array have the same index in the polynomials - that would not be true in the flipped order and all sorts of offset-arithmetic needs to happen, it's confusing and easy to get wrong. Also, "leading zero coefficients" appear at the end of the array where it would be easier to drop/ignore them. It's not necessarily wrong to flip it around, but normally less convenient.

I expect there are bugs due to this, but it's hard to tell.

Using the usual ordering, naive (quadratic time) polynomial multiplication would look like this:

static long[] multiplyPolynomials(long[] a, long[] b) {
    long[] c = new long[a.length + b.length - 1];
    for (int i = 0; i < a.length; i++)
        for (int j = 0; j < b.length; j++)
            c[i + j] += a[i] * b[j];
    return c;
}

Which you can also use to test the more advanced implementations against.

Repeated in-line operations

Extracting the low and high parts, as well as creating the "low + high" polyomial, could be put in their own functions, to clean up the main function.

Some of the loops can be written as System.arrayCopy.

Suggested implementation

Putting those things together, the code might end up like this:

static long[] getLow(long[] a, int half)
{
    long[] low = new long[half];
    System.arraycopy(a, 0, low, 0, low.length);
    return low;
}

static long[] getHigh(long[] a, int half)
{
    long[] high = new long[a.length - half];
    System.arraycopy(a, half, high, 0, high.length);
    return high;
}

static long[] addPolynomials(long[] a, long[] b) {
    if (a.length < b.length) {
        long[] t = a;
        a = b;
        b = t;
    }
    long[] result = new long[a.length];
    for (int i = 0; i < b.length; i++)
        result[i] = a[i] + b[i];
    System.arraycopy(a, b.length, result, b.length, a.length - b.length);
    return result;
}

public static long[] multiplyPolynomialsKaratsuba(long[] a, long[] b) {
    
    long[] c = new long[a.length + b.length - 1];
    if (a.length * b.length < 1000) {
        
        for (int i = 0; i < a.length; i++)
            for (int j = 0; j < b.length; j++)
                c[i + j] += a[i] * b[j];
        return c;
    }

    int half = (Math.max(a.length, b.length) + 1) / 2;
    long[] alow = getLow(a, half);
    long[] blow = getLow(b, half);
    long[] ahigh = getHigh(a, half);
    long[] bhigh = getHigh(b, half);
    long[] amed = addPolynomials(alow, ahigh);
    long[] bmed = addPolynomials(blow, bhigh);

    long[] clow = multiplyPolynomialsKaratsuba(alow, blow);
    System.arraycopy(clow, 0, c, 0, clow.length);
            
    long[] chigh = multiplyPolynomialsKaratsuba(ahigh, bhigh);
    System.arraycopy(chigh, 0, c, 2 * half, chigh.length);
    
    long[] cmed = multiplyPolynomialsKaratsuba(amed, bmed);
    for (int j = 0; j < cmed.length; j++)
        c[j + half] += cmed[j] - (j < chigh.length ? chigh[j] : 0) - (j < clow.length ? clow[j] : 0);

    return c;
}

I did some minor benchmarking, choosing both polynomials to be the same size, and a power of two size, which is the only case in which the old implementation does the right thing (or the right amount of work at least). The new code was tested with a threshold of 2 and with a threshold of 1000 (which looked like a good value to choose).

         Old  Thr2 Thr1000
  256    2ms 0.7ms  0.1ms
  512    5ms   1ms  0.5ms
 1024   14ms   4ms    1ms
 2048   40ms  11ms    3ms
 4096  125ms  32ms   10ms
 8192  360ms 100ms   29ms
16384 1100ms 270ms   85ms

So I think we safely conclude that about a factor of 3 is thanks to not applying Karatsuba all the way down single elements, and about an other factor of 4 is thanks to everything else.

The times are plotted below on a log-log plot so you can see the scaling is about right.

time plot

\$\endgroup\$

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.