sharp-biginteger/BigUIntMath.cs

using System;
using sharp.extensions;
namespace BigInt
{
	public static class BigUIntMath
	{
		/* Public Interface */


		public static void add(UInt32[] a, UInt32[] b)
		{
			UInt32 c = 0;

			for (int n = 0; n < a.Length; n++)
			{
				a[n] = add(a[n], (n < b.Length) ? b[n] : 0, ref c);
			}
		}

		public static void sub(UInt32[] a, UInt32[] b)
		{
			UInt32 c = 0;

			for (int n = 0; n < a.Length; n++)
			{
				a[n] = sub(a[n], (n < b.Length) ? b[n] : 0, ref c);
			}
		}

		public static UInt32[] mul(UInt32[] a, UInt32[] b)
		{
			UInt32[] result = new UInt32[a.Length + b.Length];

			for (int l1 = 0; l1 < a.Length; l1++)
			{
				for (int l2 = 0; l2 < (b.Length); l2++)
				{
					int target = l1 + l2;
					UInt64 ui64 = ((UInt64)a[l1] * b[l2]);
					for (int ct = target; (ct < result.Length) && (ui64 != 0); ct++){
						ui64 += result[ct];
						result[ct] = (UInt32)ui64;
						ui64 >>= 32;
					}
				}
			}

			return result;
		}

		/**
		 * @brief Calulate a / b.
		 * @returns Result of division. a[] will contain reminder.
		 **/
		public static UInt32[] div(UInt32[] a, UInt32[] b)
		{
			if (cmp(a, b) < 0)
			{
				return new UInt32[a.Length];
			}

			UInt32[] result = new UInt32[a.Length];
			UInt32[] d = b.Segment(0).Extend(a.Length);

			int lg2a, lg2b, shift;

			lg2a = log2(a);
			lg2b = log2(d);
			shift = lg2a - lg2b;

			if (shift > 0)
			{
				shl(d, shift);
			}

			for (int n = 0; n <= (shift); n++)
			{
				shl(result, 1);

				if (cmp(d, a) <= 0)
				{
					result[0] |= 1;
					sub(a, d);
				}

				shr(d, 1);
			}
			return result;
		}

		public static int log2(UInt32[] a)
		{
			for (int n = a.Length << 5; n > 0; n--)
			{
				if ((a[(n - 1) >> 5] & (1 << ((n - 1) & 0x1F))) != 0)
				{
					return n - 1;
				}
			}
			return 0;
		}

		/**
		 * @brief Logical Shift Left
		 **/
		public static void shl(UInt32[] a, int n)
		{
			if (n > 0)
			{
				int step = n >> 5;
				n &= 0x1F;

				for (int i = a.Length; i > 0; i--)
				{
					int b1 = i - 1 - step;
					int b2 = b1 - 1;

					if (b1 >= 0){
						a[i - 1] = (a[b1] << n);
						if ((n != 0)&&(b2 >= 0))
						{
							a[i - 1] |= ((a[b2] >> (32 - n)));
						}
					} else {
						a[i - 1] = 0;
					}
				}
			}
		}
		/**
		 * @brief Logical Shift Right
		 **/
		public static void shr(UInt32[] a, int n)
		{
			if (n > 0)
			{
				int step = n >> 5;
				n &= 0x1F;

				for (int i = 0; i < a.Length; i++)
				{
					int b1 = i + step;
					int b2 = b1 + 1;

					if (b1 < a.Length)
					{
						a[i] = (a[b1] >> n);
						if ((n != 0) && (b2 < a.Length))
						{
							a[i] |= ((a[b2] << (32 - n)));
						}
					}
					else
					{
						a[i] = 0;
					}
				}
			}
		}

		/**
		 * @brief Compare
		 * @returns Negative Value if a<b, Positive Value if a>b,0 if equal
		 **/
		public static int cmp(UInt32[] a, UInt32[] b)
		{
			int start = a.Length > b.Length ? a.Length : b.Length;

			for (int n = start; n > 0; n--)
			{
				Int64 diff = (n <= a.Length ? (Int64)a[n - 1] : 0) - (n <= b.Length ? (Int64)b[n - 1] : 0);
				if (diff != 0)
				{
					return (diff < 0) ? -1 : 1;
				}
			}
			return 0;
		}






		/* Helper Functions */

		private static UInt32 add(UInt32 a, UInt32 b, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)carry + (UInt64)a + (UInt64)b;
			carry = (UInt32)(ui64 >> 32);
			return (UInt32)(ui64 & 0xffffffff);
		}
		private static UInt32 add(UInt32 a, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)carry + (UInt64)a;
			carry = (UInt32)(ui64 >> 32);
			return (UInt32)(ui64 & 0xffffffff);
		}

		private static UInt32 sub(UInt32 a, UInt32 b, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)a - (UInt64)b - (UInt64)carry;
			carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
			return (UInt32)(ui64 & 0xffffffff);
		}
		private static UInt32 sub(UInt32 a, ref UInt32 carry)
		{
			UInt64 ui64 = (UInt64)a - (UInt64)carry;
			carry = (ui64 & (1UL << 63)) != 0 ? (UInt32)1 : (UInt32)0;
			return (UInt32)(ui64 & 0xffffffff);
		}

		private static UInt32 shl(UInt32 a, int n, ref UInt32 carry)
		{
			UInt64 result = (UInt64)((UInt64)a << n) | carry;
			carry = (UInt32)(result >> 32);
			return (UInt32)result;
		}
		private static UInt32 shr(UInt32 a, int n, ref UInt32 carry)
		{
			UInt64 result = (UInt64)((UInt64)a << (32 - n)) | ((UInt64)carry << 32);
			carry = (UInt32)result;
			return (UInt32)(result >> 32);
		}







	}
}