Optimizing Karatsuba Implementation (C#)

Question

So, I'm trying to improve some of the operations that .net 4's BigInteger class provide since the operations appear to be quadratic. I've made a rough Karatsuba implementation but it's still slower than I'd expect.

The main problem seems to be that BigInteger provides no simple way to count the number of bits and, so, I have to use BigInteger.Log(..., 2). According to Visual Studio, about 80-90% of the time is spent calculating logarithms.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Test
{
    class Program
    {
        static BigInteger Karatsuba(BigInteger x, BigInteger y)
        {
            int n = (int)Math.Max(BigInteger.Log(x, 2), BigInteger.Log(y, 2));
            if (n <= 10000) return x * y;

            n = ((n+1) / 2);

            BigInteger b = x >> n;
            BigInteger a = x - (b << n);
            BigInteger d = y >> n;
            BigInteger c = y - (d << n);

            BigInteger ac = Karatsuba(a, c);
            BigInteger bd = Karatsuba(b, d);
            BigInteger abcd = Karatsuba(a+b, c+d);

            return ac + ((abcd - ac - bd) << n) + (bd << (2 * n));
        }

        static void Main(string[] args)
        {
            BigInteger x = BigInteger.One << 500000 - 1;
            BigInteger y = BigInteger.One << 600000 + 1;
            BigInteger z = 0, q;

            Console.WriteLine("Working...");
            DateTime t;

            // Test standard multiplication
            t = DateTime.Now;
            z = x * y;
            Console.WriteLine(DateTime.Now - t);

            // Test Karatsuba multiplication
            t = DateTime.Now;
            q = Karatsuba(x, y);
            Console.WriteLine(DateTime.Now - t);

            // Check they're equal
            Console.WriteLine(z == q);

            Console.Read();
        }
    }
}

So, what can I do to speed it up?

Answer 1

The fastest uses a lookup table - 8 bit should be sufficient:

    private UInt32 popcount_fbsd2(UInt32 v) {
        v -= ((v >> 1) & 0x55555555);
        v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
        v = (v + (v >> 4)) & 0x0F0F0F0F;
        v = (v * 0x01010101) >> 24;
        return v;
    }

    static Byte[] lut = new Byte[256];

    void initlut() {
        for (UInt32 i = 0; i < 256; ++i) {
            lut[i] = (Byte)popcount_fbsd2(i);
        }
    }

    UInt32 BitCount3(BigInteger n) {
        Byte[] ba = n.ToByteArray();
        UInt32 bitct = 0;

        foreach (Byte aByte in ba) {
            bitct += lut[aByte];
        }

        return bitct;
    }

However, this isn't too much slower:

    UInt32 BitCount2(BigInteger n) {
        Byte[] ba = n.ToByteArray();
        UInt32[] uia = new UInt32[ba.Length / 4 + 1];

        int j = 0;
        for (int i = 0; i < ba.Length-4; i += 4) {
            uia[j++] = BitConverter.ToUInt32(ba, i);
        }

        Byte[] ba2 = new Byte[4];

        for (int i = (ba.Length / 4) * 4, j2 = 0; i < ba.Length; ++i) {
            ba2[j2++] = ba[i];
        }
        uia[j] = BitConverter.ToUInt32(ba2, 0);

        UInt32 bitct = 0;
        foreach (UInt32 aUI in uia) {
            bitct += popcount_fbsd2(aUI);
        }

        return bitct;
    }

Both are much faster than counting a BitArray's set members.

BTW, did you mean to have

BigInteger x = (BigInteger.One << 500000) - 1;
BigInteger y = (BigInteger.One << 600000) + 1;

in your test code?