Pagina's

2010/09/25

Toom-Cook 2, Random BigIntegers, bit length BigInteger

In the previous, the first blog, Toom Cook 2, TC2, was to fast. A lot of 1's were mutiplied with a lot of 1's.
1111 1111 * 1111 1111 =  1111 1110 0000 0001
If the numbers are cut into pieces, limbs, a lot of multiplications by one and zero are done.
To get realistic results, random BigIntegers have to be used.
Other gadgets in the code below are the bitlength of a BigInteger, and the bitlength of a byte.


//---------RaNDom----------bitLength--------------TC2---------------------
using System;
using System.Numerics;
using System.Diagnostics;

class TC2_test
{
    private static Stopwatch sw = new Stopwatch();

    static void Main()
    {
        Console.WindowHeight = Console.LargestWindowHeight;
        test_RND();
        test_MTP();

        Console.ReadLine();
    }

    private static void test_RND()
    {
        BigInteger U, V;
        for (int i = 1; i < 200; i += 20)
        {
            U = RND(i); V = RND(i);
            Console.WriteLine(i + "  " + bitLength(U) + "  " + U);
            Console.WriteLine(i + "  " + bitLength(V) + "  " + V);
        }
    }

    private static void test_MTP()
    {
        BigInteger U, V;
        for (int i = 0; i < 10; i++)
        {
            U = RND(100000);
            V = RND(100000);
            sw.Start();
            BigInteger P1 = MTP(U, V);
            sw.Stop();
            Console.WriteLine("MTP " + sw.ElapsedMilliseconds);
            sw.Restart();
            BigInteger P2 = U * V;
            sw.Stop();
            Console.WriteLine("U*V " + sw.ElapsedMilliseconds);
            if (P1 != P2) Console.WriteLine("MTP WRONG");
            sw.Reset();
        }
    }

    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;
    }

    private static int seed;
    private static BigInteger RND(int n)
    {
        if (n == 0) return 0;
        if (seed == int.MaxValue) seed = 0; else seed++;
        Random rand = new Random(seed);
        byte[] bytes = new byte[((n - 1) >> 3) + 2];
        rand.NextBytes(bytes);
        bytes[bytes.Length - 1] = 0;
        n = ((bytes.Length - 1) << 3) - n;
        bytes[bytes.Length - 2] >>= n;
        bytes[bytes.Length - 2] |= (byte)(128 >> n);
        return new BigInteger(bytes);
    }

    private static int bitLength(BigInteger U)
    {
        byte[] bytes = BigInteger.Abs(U).ToByteArray();
        int i = bytes.Length - 1;
        return (i << 3) + bitLength(bytes[i]);
    }

    private static int bitLength(byte b)
    {
        return b == 0 ? 0 : b < 16 ? b < 4 ? b < 2 ? 1 : 2 : b
        < 8 ? 3 : 4 : b < 64 ? b < 32 ? 5 : 6 : b < 128 ? 7 : 8;
    }

}
//---------RaNDom----------bitLength--------------TC2---------------------

No comments:

Post a Comment