大整数运算代码c#
//==============================================================================
=
// 大整数乘法 C#实现院 最大支持 2147483647 位结果运算
//
// 此实现方式大此如下:
// 数字以字符串方式存储，在C#中字符串
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
示的最大长度为32整型最大值是 2147483647, // 所以要求计算的结果，不能超过这个范围。
//
// 乘法计算采用分治法 二进制整数X和Y各分为2段，每段的长为n/2位(假设n是2的幂)
// 由此，X=A2n/2+B，Y=C2n/2+D。这样，X和Y的乘积为:
// XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD 时间复杂度: T(n)=O(nlog3)=O(n1.59)。 // 利用此公式进行递归调用
//
// 在此实现中，以十进制进行计算。为满足非2的整次幂长度的数的计算，先对要计算的数用0进二的整
// 次幂长度填充后，再进行计算。
//
//==============================================================================
=
// 作者:郭真林
// Emial:enin_dqc@163.com
// QQ:366110836
// 日期: 2007 / 10 / 19
//==============================================================================
=
using System;
using System.Collections.Generic;
using System.Text;
namespace BigNumMultiply
...{
public sealed class Number
...{
static void Main(string[] args)
...{
try
...{
Console.WriteLine("Please input two numbers:");
string x = Console.ReadLine();
string y = Console.ReadLine();
Console.WriteLine(new Number(x) * new Number(y));
}
catch (Exception ex)
...{
Console.WriteLine("An Error occurd. Exception Messgae: {0}",
ex.Message);
}
Console.ReadLine();
}
public Number()
: this(false, string.Empty)
...{ }
/**////
/// 构造一个数的Number实例
///
///
数值
public Number(long num)
: this(false, num.ToString())
...{ }
/**////
/// 构造一个数字串的Number实例
///
///
public Number(string numStr)
...{
if (numStr.StartsWith("-"))
...{
this.isNegative = true;
numStr = numStr.Substring(1);
}
else
...{
this.isNegative = false;
}
this.Val = numStr;
}
/**////
/// 构造一个数的Number实例
///
///
是否为负数
///
数字串
public Number(bool negative, string num)
...{
this.isNegative = negative;
this.Val = num;
}
/**////
/// 计算数的被拆的最小长度，必须为2的整次幂，且小于等于8
///
private static readonly int part = 4;
/**////
/// 计算两数之差，要求两数必须为正。且大数在前，小数在后
///
///
被减数
///
减数
///
private static Number Sub(Number n1, Number n2)
...{
if (n1.isNegative || n2.isNegative)
throw new ArgumentException("Number cant't be negative.");
string a = Fill(n1.Val, Math.Max(n1.Length, n2.Length));
string b = Fill(n2.Val, Math.Max(n1.Length, n2.Length));
switch (CompareStr(a, b))
...{
case 0:
return new Number(0);
case 1:
...{
Number reNum = new Number();
reNum.isNegative = false;
string result = string.Empty;
bool sf = false;
int i = 1;
while (i <= a.Length)
...{
int r = Convert.ToInt32(a.Substring(a.Length - i, 1))
-
Convert.ToInt32(b.Substring(a.Length - i, 1)) -
(sf ? 1 : 0);
result = Convert.ToString(r < 0 ? r + 10 : r) + result;
sf = r < 0;
i++;
}
reNum.Val = result;
return reNum;
}
case -1:
...{
Number reNum = Sub(new Number(false, b), new Number(false,
a));
reNum.isNegative = true;
return reNum;
}
default:
throw new ArgumentException("Inerrorct compareStr value.");
}
}
/**////
/// 计算两数之和，要求两数必须为正。
///
///
///
///
private static Number Add(Number n1, Number n2)
...{
if (n1.isNegative || n2.isNegative)
throw new ArgumentException("Number cant't be negative.");
string a = Fill(n1.Val, Math.Max(n1.Length, n2.Length));
string b = Fill(n2.Val, Math.Max(n1.Length, n2.Length));
string result = string.Empty;
bool sf = false;
int i = 1;
while (i <= a.Length)
...{
int r = Convert.ToInt32(a.Substring(a.Length - i, 1)) +
Convert.ToInt32(b.Substring(a.Length - i, 1)) + (sf ? 1 : 0);
result = Convert.ToString(r >= 10 ? r - 10 : r) + result;
sf = r >= 10;
i++;
}
if (sf) result = "1" + result;
return new Number(false, result);
}
/**////
/// 把一个数拆成两个数，被拆数长度必须为偶数
///
///
被拆数
///
高位
///
低位
private static void DevideTo(Number sou, out Number a, out Number b)
...{
if (sou.Length == 0 || sou.Length % 2 == 1)
throw new ArgumentException("Devided num not a valid value.");
string value = sou.val;
a = new Number(sou.IsNegative, value.Substring(0, value.Length / 2));
b = new Number(sou.IsNegative, value.Substring(value.Length / 2));
}
/**////
/// 按2的整次幂，用0进行填充。
///
///
被填充数
///
希望被填充的大小，若不为2的整次幂，则长度为大小此数的下一个2的整次幂数
///
private static Number PowerFill(Number nm, int maxLeng)
...{
int p = 1;
while (p < maxLeng)
...{
p *= 2;
}
Number re = new Number();
re.IsNegative = nm.IsNegative;
re.val = Fill(nm.val, p);
return re;
}
/**////
/// 计算两数相乘
///
///
///
///
///
private static Number Multiply(Number x, Number y, int n)
...{
if ((x.Val.Length + y.Val.Length) > Int32.MaxValue)
throw new ArgumentOutOfRangeException("The length of the result
exceeds maxinum value:2147483647}");
if (x == Number.Zero || y == Number.Zero)
return Number.Zero;
Number a, b, c, d;
if (x.Length > part) //x.length = y.length
...{
DevideTo(x, out a, out b);
DevideTo(y, out c, out d);
Number ac = Multiply(a, c, n / 2);
Number bd = Multiply(b, d, n / 2);
//Number a_b_d_c = (a - b) * (d - c);
//Number n1 = PowTen(ac, n);
//Number n2 = PowTen(a_b_d_c + ac + bd, n / 2);
//return n1 + n2 + bd;
return PowTen(ac, n) + PowTen((a - b) * (d - c) + ac + bd, n / 2)
+ bd;
}
else
...{
Number result = new Number(Convert.ToInt32(x.val) *
Convert.ToInt32(y.val));
return result;
}
}
/**////
/// 计算一个数的与10的l次幂的积
///
///
被乘数
///
10的L次方
///
private static Number PowTen(Number num, int l)
...{
if (num == Number.Zero) return Number.Zero;
Number re = new Number();
re.IsNegative = num.IsNegative;
re.val = num.val;
while (l > 0)
...{
re.val += "0";
l--;
}
return re;
}
operator override#region operator override
public static Number operator *(Number x, Number y)
...{
if (x == Number.Zero || y == Number.Zero)
return Number.Zero;
Number a = PowerFill(x, Math.Max(x.Length, y.Length));
Number b = PowerFill(y, Math.Max(x.Length, y.Length));
a.IsNegative = b.IsNegative = false;
Number nm = Multiply(a, b, a.Length);
nm.IsNegative = x.IsNegative == y.IsPasstive;
return nm;
}
public static bool operator ==(Number a, Number b)
...{
if (a.isNegative != b.isNegative)
return false;
if (CompareStr(a.Val, b.Val) == 0)
return true;
return false;
}
public static bool operator !=(Number a, Number b)
...{
return !(a == b);
}
public static bool operator >(Number a, Number b)
...{
if (a.isNegative && b.IsPasstive)
return false;
if (a.IsPasstive && b.isNegative)
return true;
int cs = CompareStr(Trim(a.val), Trim(b.val));
switch (cs)
...{
case 0:
return true;
case 1:
return !a.isNegative;
case -1:
return a.isNegative;
default:
throw new ArgumentException("Inerrorct compareStr value.");
}
}
public static bool operator >=(Number a, Number b)
...{
return (a == b) || (a > b);
}
public static bool operator <(Number a, Number b)
...{
return !(a > b);
}
public static bool operator <=(Number a, Number b)
...{
return (a == b) || (a < b);
}
public static Number operator +(Number a, Number b)
...{
Number re;
a = a.Clone();
b = b.Clone();
if (a.IsNegative && b.IsNegative)
...{
a.isNegative = b.isNegative = false;
re = Add(a, b);
re.isNegative = true;
}
else if (a.IsPasstive && b.IsPasstive)
...{
re = Add(a, b);
}
else if (a.IsNegative && b.IsPasstive)
...{
a.IsPasstive = true;
re = Sub(b, a);
}
else// if(a.IsPasstive && b.IsNegative)
...{
b.IsPasstive = true;
re = Sub(a, b);
}
return re;
}
public static Number operator -(Number a, Number b)
...{
b = b.Clone();
b.isNegative = !b.isNegative;
return a + b;
}
#endregion
/**////
/// 把一个数字串，按leng长度用0进行填充
///
///
被埴数字串
///
最大长度
///
private static string Fill(string val, int leng)
...{
if (val.Length == leng)
return val;
else if (val.Length > leng)
throw new OverflowException("The length of val can't above leng.");
else
while (val.Length != leng)
val = "0" + val;
return val;
}
/**////
/// 检查字符串是否为合法的数字串
///
///
///
private bool Check(string val)
...{
val = val.Trim();
for (int i = 0; i < val.Length; i++)
...{
if (!char.IsNumber(val[i]))
return false;
}
return true;
}
public override string ToString()
...{
if (IsNegative) return "-" + this.Val;
return Val;
}
/**////
/// 删除数字串前多余的0填充
///
///
///
private static string Trim(string valNum)
...{
int i = 0;
while (i < valNum.Length && (char.GetNumericValue(valNum, i) == 0)) i++;
valNum = valNum.Substring(i);
if (valNum.Length == 0 || (valNum.Length == 1 && valNum == "0"))
return "0";
return valNum;
}
/**////
/// 比较两数串表示的数的大小
///
///
///
///
1 大于，0 相等， -1 小于
private static int CompareStr(string des, string sour)
...{
string a = Trim(des);
string b = Trim(sour);
if (a.Length == b.Length)
...{
if (a.Length == 0) return 0;
for (int i = 0; i < a.Length; i++)
...{
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
else continue;
}
return 0;
}
if (a.Length > b.Length)
return 1;
else
return -1;
}
/**////
/// 返回该数的一个副本
///
///
public Number Clone()
...{
return new Number(this.isNegative, this.Val);
}
public override int GetHashCode()
...{
return base.GetHashCode();
}
public override bool Equals(object obj)
...{
return base.Equals(obj);
}
private bool isNegative;
private string val;
public bool IsPasstive
...{
get ...{ return !this.IsNegative; }
set ...{ this.IsNegative = !value; }
}
public bool IsNegative
...{
get ...{ return isNegative; }
set ...{ isNegative = value; }
}
/**////
/// 该数的数字
///
public string Val
...{
get
...{
return Trim(val);
}
set
...{
if (Check(value))
val = value;
else
throw new ArgumentException("Num is not a valid value.");
}
}
/**////
/// 该数的位数
///
public int Length
...{
get ...{ return this.val.Length; }
}
/**////
/// 数字0的Number实例
///
public static Number Zero
...{
get ...{ return new Number(0); }
}
}
浙公网安备 33021202002483