整数集和进位制 (1-1F)
我们知道，有理数的算术运算可以归结为整数的算术运算。有理数可以被表示为\(\frac p q\)的形式，在不涉及到乘幂小于一的情况下，整数运算的结果还是整数。研究高精度计算的基础是研究整数的运算。
整数
在基于硬件的整数指令中,计算机能够处理的整数是有界的,在目前典型的计算机中整数的溢出界都不超过\(2^{64}\),而符号计算中常常需要处理更大的整数,例如阶乘,斐波拉契数列这样简单的数论函数计算,另一个例子是所谓的中间表示膨胀,例如采用 Euclid 算法（在多项式及其因子中的计算算法） 计算两个整系数多项式的最大公约数时,即使输入的两个多项式和输出的最大公约数多项式都具有较小的系数,计算过程中的中间结果仍然很可能出现非常大的系数.设
\[\begin{align*} F&=7x^7+2x^6-3x^5-3x^3+x+5,\\ G&=9x^5-3x^4-4x^2+7x+7, \end{align*}\]
在计算过程中将有理数化为整数,我们将得到如下的多项式序列
\[\begin{align*} &1890x^4-4572x^3-6930x^2-846x+4527,\\ &294168996x^3+257191200x^2-20614662x-142937946,\\ &-103685278369841305200x^2-32576054233115610000x\\ &+122463167842311670000,\\ &2956790833503849546789342057565207098291763520000x\\ &+555325261806247996966034784074025291687620160000,\\ &1092074685733031219201041602791259862659169966184593803518\\ &602418777140682884334769647063543607737698426880000000000, \end{align*}\]
最后的那个整数达到了118位.除此之外,高精度浮点数的表示和运算也是直接依赖于高精度整数的.
整数的表示
如果没有明确指出,本节所说的整数都是正整数.关于高精度整数的表示方法,一个简单的想法是选定进制\(B\),用整数的\(B\)进制来表示整数。
记号\((a_n\ldots a_1a_0)_B\)为\(B\)进制整数,如果\[a_k\in\{0,1,\ldots,B-1\},a_n\ne 0,0\le k\le n.\] 下面有整数 \((a_n\ldots a_1a_0)_B\)，则有:
\[(a_0)_B = a_0\] \[(a_n\ldots a_1a_0)_B = B\cdot(a_n\ldots a_1)_B+a_0\] \[(a_n\ldots a_1a_0)_B=\sum_{k=0}^na_k\cdot B^k.\]
规定整数的类
下面的几个参数是规定整数所必须的（以后的内容中还会不断补加）
public class DecimalInteger
{
public byte[] Data;
public bool Reversed = false;
public int Count;
public DecimalInteger(byte[] data)
{
this.Data = data;
this.Count = data.Length;
}
public static implicit operator DecimalInteger(string data)
{
DecimalInteger inte = new DecimalInteger(new byte[1]);
if (data[0] == '-')
{
inte.Reversed = true;
data = data.Remove(0, 1);
}
int count = data.Length;
inte.Data = new byte[count];
for (int i = 0; i < count; i++)
{
byte parse = 0;
switch (data[i])
{
case '0': parse = 0; break;
case '1': parse = 1; break;
case '2': parse = 2; break;
case '3': parse = 3; break;
case '4': parse = 4; break;
case '5': parse = 5; break;
case '6': parse = 6; break;
case '7': parse = 7; break;
case '8': parse = 8; break;
case '9': parse = 9; break;
default: throw new Exceptions.StringedIntegerInvalidException(data[i].ToString());
}
if (parse >= 10)
throw new Exceptions.StringedIntegerInvalidException();
inte.Data[count - i - 1] = parse;
}
inte.Count = count;
return inte;
}
public static implicit operator DecimalInteger(Int32 value)
{
return value.ToString();
}
public static implicit operator DecimalInteger(Int64 value)
{
return value.ToString();
}
public static implicit operator DecimalInteger(Int16 value)
{
return value.ToString();
}
public static implicit operator DecimalInteger(byte value)
{
return value.ToString();
}
public override string ToString()
{
string expr = "";
if (Reversed) expr = "-";
string abs = "";
foreach (byte b in Data)
{
abs = abs.Insert(0, b.ToString());
}
return expr + abs.Trim();
}
}其中，定义 DecimalInteger 类为无损运算的十进制整数类。Data 储存了整数数字的绝对值，通过上面的公式可以算出和表示任意大小的整数（正整数）。 Reversed 是符号位。指示是否为负数，而 Count 代表在当前进制下整数的位数。 接下来，我们还需要初始化和转换的函数。注：如果开头就定义一个完备的，支持任意进位制的整形数 Integer ，就要求 Data, CarrySystem, Count 等类型都必须为 Integer 自己，初始化找不到入口。
static void Main(string[] args)
{
Console.WriteLine("Hypothesis : Insider Testing Command.");
Types.DecimalInteger dec = "-12320100293102938912839973248012948329490129843240921389134240293482394923408234732409212903843029491872491";
Console.WriteLine(dec.ToString());
dec = long.MaxValue;
Console.WriteLine(dec.ToString());
}显然，例中非常大的整数 \(-12320100293102938912839973248012948329490129843240921389134240293482394923408234732409212903843029491872491\) 是无法在哪怕最大的计算机默认数据类型中显示的，但通过定义 DecimalInteger 类型和隐式转换我们可以表示这样的数。 运行结果如下
Hypothesis : Insider Testing Command.
-12320100293102938912839973248012948329490129843240921389134240293482394923408234732409212903843029491872491
9223372036854775807进位制转换
在\(B\)进制下除以\(B'\)
 |
本文归属于 Project Formula 文档。 本文和本系列的所有页面的文本内容签署在 GNU Free Documentation License 1.3 下；所有代码和代码片段签署在 GNU General Public License 2.0 下。 请务必附加许可证的引用。 |
