问题标签 [arbitrary-precision]

我正在编写一个 c++ 任意整数库作为作业。我在内部将数字表示为无符号整数的向量，以 10^n 为基数，其中 n 尽可能大，同时适合单个无符号整数数字。

我做出这个选择是为了在空间、性能和数字访问之间进行权衡（它允许我获得比使用 base 10 更好的性能，而在转换为人类可读字符串时不会增加任何复杂性）。

例如：

base10(441243123294967295) 18 位

base1000000000(441243123,294967295) 2 位（逗号分隔）

使用 uint32 的内部表示

[00011010 01001100 11010101 11110011] [00010001 10010100 11010111 11111111]

为了完成作业，我必须实现位移和其他位运算符。对具有这种内部表示的数字实施移位是否有意义？

我应该更改为基数 2^n 以便内部表示的所有位都有意义吗？

我想为任意整数创建 boost::spirit::qi::grammar 。将整数存储到字符串只是感觉非常浪费内存，尤其是当整数以二进制格式表示时。如何在结构中使用任意精度整数类（例如 GMP 或 llvm::APInt）？

So of course I know there are simple solutions to this such as using the GMP library or numerous other arbitrary-precision libraries. This is for class work so I am not allowed to take any of these routes. After we build up all our operations we are leading up to be able to do a RSA encryption scheme.

I am using vectors to store n-bit numbers represented in binary. I have conversions to decimal later but I must operate on the binary and only convert for display.

I have successfully implemented addition, subtraction, and multiplication. I am stuck on division and modular operations... specifically modular exponentiation. I understand the algorithms at least at a basic level but cant seem to translate it into code that will work on arbitrary length numbers. I cant seem to find any examples of this type of work done in c++ without external libraries.

Some specific questions:

is there a better way to do modulus on a n-bit number besides just calling the division function I am writing and using the remainder returned?

I really would love to see some good c++ examples as I cant follow the GMP source code well at all.

Any good resources to study or some help would be greatly appreciated. Thanks

使用此代码时，我遇到了一些奇怪的问题：

i此 for 循环的每次迭代都应计算在给定频率的情况下事件发生次数的二项式概率。每次迭代也会总结结果。这应该会导致prob变量永远不会超过 1，但是在 7 次左右的循环迭代之后，一切都变得糟糕并prob超过 1。

我认为这可能是数字精度的问题，所以我尝试使用Rmpfr但无济于事——同样的问题仍然存在。

我想知道是否有任何技巧或包来克服这种情况，或者我是否坚持这一点。

我正在寻找 C/C++ 的任意精度浮点库（首选纯 C）。我需要任意精度指数。GMP 和 MPFR 使用固定大小的指数，因此它们不符合条件（我有一些解决方法的想法，但我更喜欢开箱即用的解决方案）。如果可以自动调整指数精度以防止无穷大值，那将是一个很好的功能。

如果您确定不存在这样的库，请说出来。

计算产品的最有效方法是什么

a ¹ b ² c ³ d ⁴ e ⁵ ...

假设平方的成本大约是乘法的一半？操作数的数量小于 100。

对于乘法时间与操作数长度的平方成正比（如java.math.BigInteger）的情况，是否还有一种简单的算法？

第一个（也是唯一的）答案是完美的操作数量。

有趣的是，当应用于 sizable 时BigInteger，这部分根本无关紧要。即使在没有任何优化的情况下计算abbcccddddeeeee 也需要大约相同的时间。

大部分时间花在最后的乘法上（BigInteger没有实现更智能的算法，如 Karatsuba、Toom-Cook 或 FFT，所以时间是二次的）。重要的是确保中间被乘数的大小大致相同，即给定数字p, q, r, s的大小大致相同，计算(pq) (rs)通常比((pq) r) s快。对于几十个操作数，速度比似乎约为 1:2。

更新

在 Java 8 中，在BigInteger.

I know there are a couple of thread on similar topics ( What's the best (for speed) arbitrary-precision library for C++? and The best cross platform (portable) arbitrary precision math library ) and I take from these threads than GMP or something based on it like MPFR is the fastest lib available, but I am specifically wondering: if I only wanted say 30 dec places would __float128 of the quadmath lib be faster?

Also how does MAPM stack up against MPFR?

It looks from this website:

http://pari.math.u-bordeaux.fr/benchs/timings-mpfr.html

that MPFR does pretty well, but there are also CLN and apfloat?

我想将e计算为 2 万亿（2,000,000,000,000）位。这大约是 1,8 TiB 的纯e。我刚刚使用GMP实现了一个泰勒级数展开算法（代码可以在这里找到）。

不幸的是，在我的计算机上汇总超过 4000 个术语时它会崩溃，可能是因为内存不足。

计算e的当前最新技术是什么？哪种算法最快？有什么值得一看的开源实现吗？请不要提及y-cruncher，它是封闭源代码。

我正在研究非常长的整数（大约 100,000 个十进制数字）的乘法运算。作为我图书馆的一部分，我要添加两个长数字。

分析表明，我的代码在 add() 和 sub() 例程中运行的时间高达 25%，因此它们尽可能快很重要。但我还没有看到很大的潜力。也许你可以给我一些帮助、建议、见解或想法。我会测试它们并回复你。

到目前为止，我的 add 例程做了一些设置，然后使用了 8 次展开循环：

接下来还有 7 个具有不同偏移量的块，然后循环。

我之前尝试从内存中加载值，但这没有帮助。我想这是因为良好的预取。我使用 Intel i7-3770 Ivy Bridge 4 核 CPU。但我想编写适用于任何现代 CPU 的代码。

编辑：我做了一些计时：它在大约 2.25 个周期/字中增加了 1k 个字。如果我移除 ADC，那么只剩下 MOV，它仍然需要大约 1.95 个周期/字。所以主要的瓶颈似乎是内存访问。一个库的memcpy()工作周期约为 0.65 个周期/字，但只有一个输入，而不是两个。不过，我猜，由于它使用了 SSE 寄存器，它的速度要快得多。

一些问题：

• 使用“加载、加载、添加、存储”结构有用还是“加载、添加到内存”有帮助？到目前为止，我的测试没有显示出任何优势。
• 像往常一样，SSE(2,3,4) 没有帮助？
• 寻址（缩放索引加基数加偏移量）影响严重吗？我可以ADD r11, 8改用。
• 循环展开怎么样？我读到展开对 Sandy Bridge 架构不利（Agner Fog http://www.agner.org/optimize/）。是首选还是避免？
• （编辑）我可以使用 SSE 寄存器从内存中以更大的块加载和存储字，并有效地与通用寄存器和 SSE 寄存器交换字吗？

我非常感谢任何评论。

在我处理快速 ADD 循环（加速 x64 汇编器 ADD 循环）时，我正在使用 SSE 和 AVX 指令测试内存访问。要添加，我必须读取两个输入并产生一个输出。所以我写了一个虚拟例程，它将两个 x64 值读入寄存器并将一个写回内存而不做任何操作。这当然没用，我只是为了进行基准测试。

我使用一个展开的循环，每个循环处理 64 个字节。它由 8 个块组成，如下所示：

然后我将其升级到 SSE2。现在我使用 4 个这样的块：

后来我使用了 AVX（每个寄存器 256 位）。我有两个这样的块：

到目前为止，还没有那么壮观。有趣的是基准测试结果：当我对 1k+1k=1k 64 位字（即两次 8 kb 输入和一次 8kb 输出）运行三种不同的方法时，我得到了奇怪的结果。以下每个时序用于将两次 64 字节输入处理为 64 字节输出。

• x64 寄存器方法以大约 15 个周期/64 字节运行
• SSE2 方法以大约 8.5 个周期/64 字节运行
• AVX 方法以大约 9 个周期/64 字节运行

我的问题是：为什么 AVX 方法比 SSE2 方法慢（虽然不是很多）？我预计它至少会达到同等水平。使用 YMM 寄存器会花费这么多额外的时间吗？内存是对齐的（否则你会得到 GPF）。

有人对此有解释吗？