大整数

• 下载源代码 - 16.6 KB
• 下载演示 - 13.8 KB

概述

BigInt 是一个通用的无界整数实现，与 C# 和 .NET 数字类型约定一致：它是一个不可变的 ValueType，实现了 IComparable<BigInt>、IEquatable<BigInt> 和 IConvertable 接口，并提供算术运算符和各种隐式和显式转换运算符。

到目前为止，对于需要“大”数字的 C# .NET 开发人员来说，可用的选项非常少。Chew Keong TAN 的 C# BigInteger[^] 速度非常快，但专门用于密码学，而忽略了内存考虑（使用固定长度的 Array 实现，内存很快耗尽，并且当长度设置得稍高时，性能会降低）。 Microsoft 的 J# BigInteger[^] 也可用，但使用起来很笨拙（引用类型，没有运算符，Camel-case），并且还需要将 J# 运行时与您的应用程序一起分发。

BigInt 使用以 10 为基数的 LinkedList<byte> 实现。 因此，内存消耗和性能不如使用更高基数的 Array 实现那么优化。 话虽如此，BigInt 的性能相当好，并且内存占用足够轻，因此它应该适合许多应用程序。

算术运算

标准纸笔算法用于加法、减法、乘法和除法。 因此，加法和减法产生 m + n 的复杂度，其中 m 和 n 分别是每个操作数中的位数。 乘法和除法是 m * n 阶。 乘法在内部使用突变来提高性能（加法步骤使用 AddTo 累积在结果中，从而避免了为临时状态重复进行大量内存分配，否则我们将承担这些分配）。

常用算法

除了基本算术之外，还为 BigInt 提供了几种常用算法，包括 min、max、mod、pow 和截断平方根等等。

运算符

提供了通常与数字类型关联的所有二元和一元运算符； 但是，位运算和运算符尚未实现。

转换

为了避免冗余，同时冒着跨所有 .NET 语言的不兼容风险，我们避免使用非默认构造函数作为转换为 BigInt 的方法； 相反，我们依靠隐式转换运算符来实现来自数字 .NET 系统类型的无损转换，并依靠显式转换运算符来实现其他有用的类型。 BigInt.Parse 和 BigInt.TryParse 是从 string 构造 BigInt 的首选方法，但我们也例外地实现了一个显式的 string 到 BigInt 转换运算符以适应 Enumerable.Cast<string>(BigInt)。 此外，还提供了几个与 IConvertable 并行的有损显式转换运算符，用于从 BigInt 转换为其他类型。

序列化

BigInt 适用于二进制和 XML 序列化。 标记有 Serializable 属性，只有 BigInt 的 private 字段 (digits 和 isneg) 参与二进制序列化，这是合适的。 默认 XML 序列化，即序列化 public 字段和属性，是完全不合适的； 因此，我们实现了 IXmlSerializable 接口，通过 BigInt.ToString 表示 WriteXml，并通过 BigInt.Parse 反序列化 ReadXml。

属性

Divisors、ProperDivisors、DigitsLeftToRight 和 DigitsRightToLeft 被实现为对象流 (IEnumerable<BigInt>)，并且被选择用于描述整数的基本方面。 前两个公开整数内部结构。 后者支持在结构级别上操作整数。 PrimeFactorization 属性正在等待实现。

大数计算器

提供的示例应用程序由 BigInt 的 static Eval 方法驱动。 Eval 可以解析和评估许多简单的二元和一元 BigInt 表达式。 将来可能会扩展 Eval / BigCalculator 以支持处理复杂的表达式树和典型的计算器功能，例如变量赋值。

历史

版本	日期	描述
1.00	2009年5月10日	首次发布
1.01	2009年5月11日	通过使用平方求幂法提高了 Pow 的性能。 通过使用欧几里得算法提高了 Gcd（以及因此的 Lcm）的性能。 修改了 Range 以接受反向范围。
1.02	2009年5月16日	修复了余数错误。
1.03	2009年5月17日	改进了除法内存使用。