Pagina's

2010/09/21

BigInteger Long Multiplication and Division

It's 2010, I used VB.Net 2005 Express and the Java BigInteger Library (vjslib.dll),
and wrote the classical multiplication, Knuth section 4.3.1, and division algorithms.
It's still 2010, downloaded C# 2010 Express.
Wrote them again, and found out it's useless, C# has them.
Next step: Karatsuba Multiplication (Toom Cook 2).
Still have to test it, but the blog is started.
TC2 is about 30 times faster in the example code below,
squaring seems to be 10% faster.
2E85TTGXQJHZ

//---------------------------------------------------------------
using System;
using System.Numerics;
using System.Diagnostics;
namespace TC2Blog
{
    class Program
    {
        static void Main()
        {
            Stopwatch sw = new Stopwatch();
            BigInteger U = (BigInteger.One << 1000000) - 1;
            BigInteger V = -U;
            sw.Start();
            BigInteger P1 = MTP(U, V);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
            sw.Restart();
            BigInteger P2 = U * V;
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
            sw.Restart();
            BigInteger P3 = BigInteger.Pow(U, 2);
            sw.Stop();
            Console.WriteLine(sw.ElapsedMilliseconds);
            if (P1.CompareTo(P2) != 0)
                Console.WriteLine("MTP WRONG");
            if (BigInteger.Abs(P1).CompareTo(P3) != 0)
                Console.WriteLine("SQUARE WRONG");
            Console.WriteLine("Ready");
            Console.ReadLine();
        }

        private static BigInteger MTP(BigInteger U,BigInteger V)
        {
            int n = BigInteger.Max(U, V)
                              .ToByteArray().Length << 3;
            if (n > 2500)
                return TC2(U, V, n);
            else
                return U * V;
        }

        private static BigInteger TC2
            (BigInteger U1, BigInteger V1, int n)
        {
            n = n >> 1;
            BigInteger Mask = (BigInteger.One << n) - 1;
            BigInteger U0 = U1 & Mask; U1 >>= n;
            BigInteger V0 = V1 & Mask; V1 >>= n;
            BigInteger P0 = MTP(U0, V0);
            BigInteger P2 = MTP(U1, V1);
            BigInteger P1 = MTP(U0 + U1, V0 + V1) - (P0 + P2);
            return (((P2 << n) + P1) << n) + P0;
        }
    }
}
//---------------------------------------------------------------

No comments:

Post a Comment