From d63d6998124603a07ca7de1ffa3fea7d3d737983 Mon Sep 17 00:00:00 2001
From: Rodrigo Kumpera <kumpera@gmail.com>
Date: Sat, 6 Mar 2010 15:40:38 +0000
Subject: [PATCH] 2010-03-05 Rodrigo Kumpera  <rkumpera@novell.com>

	* BigInteger.cs: Mul.

svn path=/trunk/mcs/; revision=153174
---
 .../System.Numerics/BigInteger.cs             | 59 +++++++++++++++++++
 .../System.Numerics/System.Numerics/ChangeLog |  4 ++
 2 files changed, 63 insertions(+)

diff --git a/mcs/class/System.Numerics/System.Numerics/BigInteger.cs b/mcs/class/System.Numerics/System.Numerics/BigInteger.cs
index 5e447bf1514..f0d3db21bf3 100644
--- a/mcs/class/System.Numerics/System.Numerics/BigInteger.cs
+++ b/mcs/class/System.Numerics/System.Numerics/BigInteger.cs
@@ -40,6 +40,7 @@ Optimization
 	For bitwise operators, hoist the conditionals out of their main loop
 	Optimize BitScanBackward
 	Use a carry variable to make shift opts do half the number of array ops.
+	Schoolbook multiply is O(n^2), use Karatsuba /Toom-3 for large numbers
 */
 namespace System.Numerics {
 	public struct BigInteger : IComparable, IComparable<BigInteger>, IEquatable<BigInteger>
@@ -469,6 +470,59 @@ namespace System.Numerics {
 			return new BigInteger (left.sign, CoreAdd (left.data, right.data));
 		}
 
+		public static BigInteger operator* (BigInteger left, BigInteger right)
+		{
+			if (left.sign == 0 || right.sign == 0)
+				return new BigInteger (0, ZERO);
+
+			if (left.data [0] == 1 && left.data.Length == 1) {
+				if (left.sign == 1)
+					return right;
+				return new BigInteger ((short)-right.sign, right.data);
+			}
+
+			if (right.data [0] == 1 && right.data.Length == 1) {
+				if (right.sign == 1)
+					return left;
+				return new BigInteger ((short)-left.sign, left.data);
+			}
+
+			uint[] a = left.data;
+			uint[] b = right.data;
+
+			uint[] res = new uint [a.Length + b.Length];
+
+            for (int i = 0; i < a.Length; ++i) {
+                uint ai = a [i];
+                int k = i;
+
+                ulong carry = 0;
+                for (int j = 0; j < b.Length; ++j) {
+                    carry = carry + ((ulong)ai) * b [j] + res [k];
+                    res[k++] = (uint)carry;
+                    carry >>= 32;
+                }
+
+                while (carry != 0) {
+                    carry += res [k];
+                    res[k++] = (uint)carry;
+                    carry >>= 32;
+                }
+            }
+
+			int m;
+			for (m = res.Length - 1; m >= 0 && res [m] == 0; --m) ;
+			if (m < res.Length - 1)
+				res = Resize (res, m + 1);
+
+			short sign = 1;
+			if (left.sign != right.sign)
+				sign = -1;
+
+			return new BigInteger (sign, res);
+		}
+
+
 		public static BigInteger operator- (BigInteger value)
 		{
 			if (value.sign == 0)
@@ -1098,6 +1152,11 @@ namespace System.Numerics {
 			return left - right;
 		}
 
+		public static BigInteger Multiply (BigInteger left, BigInteger right)
+		{
+			return left * right;
+		}
+
 		public static BigInteger Negate (BigInteger value)
 		{
 			return - value;
diff --git a/mcs/class/System.Numerics/System.Numerics/ChangeLog b/mcs/class/System.Numerics/System.Numerics/ChangeLog
index 2b814a88c9a..7fba8582fe2 100644
--- a/mcs/class/System.Numerics/System.Numerics/ChangeLog
+++ b/mcs/class/System.Numerics/System.Numerics/ChangeLog
@@ -1,3 +1,7 @@
+2010-03-05 Rodrigo Kumpera  <rkumpera@novell.com>
+
+	* BigInteger.cs: Mul.
+
 2010-03-05 Rodrigo Kumpera  <rkumpera@novell.com>
 
 	* BigInteger.cs: coersion operators for short, ushort,
-- 
2.25.1