Edit Question - KnowledgeHub

Title Body

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,

Tags (comma-separated) Cancel