大整数到 1e18

• 下载源代码 - 34.42 KB

引言

该下载是一个小的大整数函数库，以 Visual Studio 2008 项目的形式提供。它目前设置为 .NET 3.5，但可能可以编译并与任何早期版本一起正常工作。

这些子程序提供了任意大小的非负整数的表示形式，并提供了对它们进行简单算术运算的功能。有一个名为form_comma_grouped_numeric_string的函数，用于将整数从内部形式转换为传统的十进制数字字符序列以进行显示。

整数在内部由 C# 63 位长整数的 C# 数组表示。 数组长度目前受到 C# 默认数组索引的限制，该索引允许数组长度约为 2^31，但如果将来有动机这样做，C# 有一种方法可以消除该限制。算术运算以 1e18 为底执行，以便

1. 利用 x86 和 x64 处理器的算术能力
2. 实现非常大的整数在磁盘上的合理存储效率，以及
3. 方便内部和外部十进制表示之间的转换

尚未包含平方根函数。有一个函数开始提供 2、3、4、5、6、8、9 和 10 的自然对数的有理近似值，但尚未完成。（我在其他事情上太忙了。）

乘法和除法使用小学算法完成；目前没有任何数论增强。尚未探索通过 Booth 算法或 FFT 整数卷积加速乘法的可能性。 CodePlex 站点提供了一个名为IntX的包，它是一个纯 C# 中的任意精度整数库，实现了快速的 - O(N * log N) - 乘法和除法算法。

背景

作者在该领域没有专业知识，也不知道任何现有位整数包是如何工作的。

Using the Code

有一个名为test_big_dec( )的函数，可用于测试各种其他函数，并且可以作为示例来参考其他函数是如何调用的。 可以注释掉或注释掉test_big_dec( )的各个部分。

用户可能调用的函数是构造函数cl_big_dec，它实例化新的big_dec实体，以及函数load_long_into_big_dec、sum、dif_pos_and_compare、prod、power、div、mult_by_long和div_by_long，其角色应从它们的名称中清楚地看出，但div_by_long除外，它给出余数和商，并将它们都作为big_decimals给出。

以下是函数test_big_dec( )中的一个片段 [带有前导句点char以限制站点软件的重新格式化本能。]

const long base_1e18 = 1000000000000000000L;
...
cl_big_dec bd_numer = new cl_big_dec( 10 );
cl_big_dec bd_denom = new cl_big_dec( 6 );
...
cl_big_dec bd_quotient, bd_remainder, bd_whole, bd_reconstructed_numerator ;
...
bd_numer.long_array[ 0 ] = base_1e18 - 1;
bd_numer.long_array[ 1 ] = base_1e18 - 1;
bd_numer.long_array[ 2 ] = base_1e18 - 1;
bd_numer.long_array[ 3 ] = base_1e18 - 1;
bd_numer.long_array[ 4 ] = base_1e18 - 1;
bd_numer.long_array[ 5 ] = base_1e18 - 2;
bd_numer.long_array[ 6 ] = base_1e18 - 1;
bd_numer.long_array[ 7 ] = base_1e18 - 1;
bd_numer.long_array[ 8 ] = base_1e18 - 1;
bd_numer.long_array[ 9 ] = base_1e18 - 2;
...
bd_denom.long_array[ 0 ] = base_1e18 - 1;
bd_denom.long_array[ 1 ] = base_1e18 - 1;
bd_denom.long_array[ 2 ] = base_1e18 - 1;
bd_denom.long_array[ 3 ] = base_1e18 - 1;
bd_denom.long_array[ 4 ] = base_1e18 - 1;
bd_denom.long_array[ 5 ] = base_1e18 - 1;
...
div( bd_numer, bd_denom, out bd_quotient, out bd_remainder );
prod( bd_denom, bd_quotient, out bd_whole );
sum( bd_whole, bd_remainder, out bd_reconstructed_numerator );
if ( compare( bd_numer, bd_reconstructed_numerator ) != 0 )
{
...throw new Exception( string.Format
......( " {0} "
......, "test_big_dec( ) failed the test of div with large multi_element denominator"
......) );
}

关注点

该软件包中可能被认为有趣的一部分是用于在长除法运算中找到下一个以 1e18 为底的商“数字”的过程。（参见代码。）

历史

• 2009_01_07，ltkj，将一些解释性信息从消息移动到上面的“使用代码”部分，并添加了对IntX库的提及