标签: arbitrary-precision

在阅读本文和本文后,我最近遇到了精确实算的主题.

我找到了许多论文,讨论使用有符号数字流实现精确算术的实现.使用无限流来获得任意精度可以在函数式语言(如Haskell)中使用惰性列表实现良好的实际实现.然而,在功能语言中讨论这种实现的论文似乎得出的结论是性能非常差.

现在,我理解与标准浮点表示相比,精确的非硬件实现通常具有相对较差的性能,但我有兴趣在命令式语言(特别是C++)和操作集合中提供更高效的实现./functions(算术运算,三角函数,exp,log等).

我的问题:是否存在导致性能不佳的签名数字/惰性流表示的内在缓慢,或者是Haskell？是什么让它变慢？是否有可能使用C++中的延迟流实现带符号的数字流表示,实现(显着)比其Haskell对应物更好的性能,或者这是徒劳的练习？也许重建为迭代？

我知道有两个C++库,RealLib和iRRAM,可以实现高效的实数计算.然而,这些似乎使用区间运算,将实数表示为缩小的嵌套区间,这似乎不像无限流那样"纯粹"(如果您不同意,请纠正我!).但也许这些是实现良好效率的唯一方法？

任何输入都表示赞赏!

有人能告诉我一个好的C++库,用于处理(执行操作等等)任意大数(它可以是一个处理任意精度浮点数的库,但处理整数更重要)？

请只引用您使用的资料库,并告诉我你是怎么设法设置它,并把它捡起来,也许一个非常简约的例子或东西(基本上,如果提到图书馆没有良好的文档提供一些自己的输入).

为了记录,我在x64机器上使用Windows 7,CodeBlocks作为我的IDE,最新的MinGW作为编译器.

我试过的图书馆:

• vlint(操作不够,但对于小东西工作正常)

• bigint(易于设置,编译错误和文档不多(可能从中导出错误))

• ttmath(看起来很有前途,编译了一些BIG示例程序,并且由于编译错误而导致一些修复后运行,因为几乎没有文档,所以语法难以理解)

• gmp(甚至无法设置)

ps删除了"问题的咆哮部分",基本上解释了为什么我在Stackoverflow上问了很多次问题,所以人们会把它读到最后.

- >更新

所以我选一个答案,这不是直接回答我最初的问题,但对我帮助很大,解决这一点,我会发布一些我的调查结果,以帮助其他的C++新手跟我一样开始使用非常大的数字,工作没有挣扎几天的图书馆像我一样一步一步地进行微观指导.

我正在使用的东西(请记住遵循指南):

• Windows 7旗舰版x64

• Amd k10 x64(有些库不适用于此,其他库的行为会有所不同,其他库会自定义为amd k10,因此这不仅可以帮助您使用我使用的库,还可以帮助您使用其他库)

• Code :: Blocks 10.05包含MinGW的版本,文件名"codeblocks-10.05-setup.exe"(安装在C:\ Program Files(x86)\ CodeBlocks上)

• MinGW包(binutils-2.15.91-20040904-1.tar.gz gcc-core-3.4.2-20040916-1.tar.gz gcc-g ++ - 3.4.2-20040916-1.tar.gz mingw-runtime- 3.11.tar.gz w32api-3.8.tar.gz)在C:\ MinGW上提取

• TTMath 0.9.2文件名"ttmath-0.9.2-src.tar.gz"解压缩并将文件夹"ttmath"复制到文件夹"C:\ CPPLibs"(这是我将我的c ++库放入的文件夹)

怎么做才能把它全部搞定

• 转到代码:Blocks> Settings> Compiler and Debugger(我的编译器在这里自动检测到.如果你没有这样做,请在"Selected Compiler"上选择"GNU GCC Compiler"并点击"Set as Default"然后点击"Toolchain" Exectables"on"编译器安装目录你可以选择编译器的安装目录或尝试自动检测"并在"C++编译器"上进行排序"选择或写入"mingw32-g ++.exe".如果发生这种情况,你只需要做在"Selected Compiler"中选择"GNU GCC Compiler"并单击"Set as Default").

• 在不离开"代码:块>设置>编译器和调试器"的情况下,按照上面的解决方法,转到"搜索目录",然后单击"添加",选择"存储库"或"放置"的位置. ttmath"文件夹(在我的情况下为C:\ CPPLibs)然后转到"链接器"并执行相同的操作.

• 首先,你必须把该行的"ttmath"编码库#include <ttmath/ttmath.h>的主要功能之前(注:如果您使用的是64位系统,你会得到很多的错误,如果你不还,就把这行#define TTMATH_DONT_USE_WCHAR 之前 …

我目前正试图弄清楚如何使用PHP中的任意精度数字.所以我想我的第一个问题是究竟什么是任意精度数学.我试着谷歌搜索一个很好的定义,但由于某种原因,没有人可以用简单的语言.

其次,PHP中的BCMath和GMP库有什么区别？我听说GMP的API是"更新鲜",但是我很高兴.一个更好吗？

我最后的问题是BCMath/GMP需要什么类型的数字.显然它需要字符串形式的正常整数(例如"5.34"),但我已经看到BCMath函数直接用于表示常规整数的八位字节字符串的实现(例如"\ x12\x23\x45\x67"),其中我听说被称为"bigint",但谷歌再也没有给我带来任何好处.

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

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

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

是否有一个简单的算法,因为乘法时间与操作数长度的平方成正比(如同java.math.BigInteger)？

第一个(也是唯一的)答案是完美的操作次数.

有趣的是,当应用于相当大BigInteger的时候,这部分根本不重要.即使在没有任何优化的情况下计算abbcccddddeeeee也需要大约相同的时间.

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

当我注意到Libre Office电子表格显示远远低于2 ^ 53的数字的错误值时,我正在做一些计算以计划我的主筛的改进实现,这是FoxPro中的精确整数计算的限制以及众多其他内部使用C double(即IEEE 754双)的语言.

一些快速检查显示数字低至2 ^ 50的错误结果.更糟糕的是,这个片状软件没有发出任何超出其操作限制的警告,并且显示的值只是近似值(即使手动输入了正确的值).我猜他们认为什么对于像Excel这样的POS来说足够好然后必须对他们足够好(但是他们应该把它命名为'Guesstimate'而不是'Calc'然后).

无论如何,是否有可能将电子表格放入某种精确模式,至少给出a的精度double,和/或当某些计算超出其数值能力时,它会显示某种警告？

或者是否有一些其他电子表格适用于甚至电话和烤面包机由64位芯片供电的时代的程序员？

背景:在这种特殊情况下,需要精确度,因为通过比较某些结果列和众所周知的数字列表(如最多2 ^ k的素数,可从OEIS获得)或数字来验证公式的精确性源自检测代码.我们的想法是通过检查它们的可行范围来获得正确的公式 - 最多在2 ^ 32和2 ^ 40之间 - 然后使用这些公式来研究范围最大为2 ^ 64的行为(这是不可能的通过详尽的测试获得完整的图片.

PS:我发现在"电子表格的数字准确性"(pdf)中已经对该问题进行了广泛的分析.似乎gnumeric比其他人更好一点,但更多的是盲人中的独眼人而不是真正的通过集合; 此外,它不适用于Windows,因此需要在我正在开发的平台上启动Linux VM以及...

UPDATE /替代方法

最多2 ^ 49没有问题,因此可以正常工作.这足以准确了解事物.在最终表格中,大数字和高精度结果(在其他地方计算)作为预格式化文本输入(或者更确切地说是导入/粘贴),以便Calc不会使显示屏变脏.仍然可以通过应用VALUE()函数来引用数字,对于许多内联计算,内部精度非常充足 - 尤其对于图形化.

下图显示了我在其中一条评论中发布的内容,即内部精度高于显示的内容.如果程序没有显示它们,我们如何才能找出实际值是什么？通过添加/减去小值,观察更改,创建和测试关于实际值的关系,假设的舍入行为和显示值的假设来解决问题？真正令人难以置信的是.

我正在为以下任何一项提供奖励:

• 一种实用的方法,在所见即所得的意义上恢复Calc的理智行为(你看到的是什么内部,或者更确切地说,如果它在里面然后它可以显示)而不降低内部精度并且不用分支整个血腥源树并自己修复它

• 指向电子表格的指针,其精度高于IEEE 754双倍(最好是任意精度,如GP/PARI,但作为电子表格),是公共域或共享软件; 在线/云计算的东西是可以接受的

第一项的原因有两个:一方面,当电子表格精度低于通用IEEE 754双精度时,这是一种血腥的麻烦,因为这意味着关于该基线水平的准确度/精度/稳定性的经验/知识不会延续.另一方面,如果我们不能相信显示的值是正确的,即使我们确切知道实际值是正确的,也会产生更大的麻烦.

第二个项目的原因很简单,在另一个程序中编写用于高精度计算事物或使用bignums的东西,或者为此目的编辑/编译/运行程序是相当麻烦的.除了笨拙地分成电子表格和一堆脚本或源文件之外,在电子表格内部工作更加自然和方便.

我正在为网站目的大量工作,我需要长时间的计算.当我回显一个很长的数字时,我得不到正确的输出.

例

// A random number
$x = 100000000000000000000000000;

$x = number_format($x);
echo "The number is: $x <br>";
// Result: 100,000,000,000,000,004,764,729,344 
// I'm not getting the value assigned to $x

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

如果您确定不存在此类库,请说明.

我正在研究很长整数的乘法运算(大约100,000个十进制数字).作为我的图书馆的一部分,我要添加两个长数字.

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

到目前为止,我的添加例程进行了一些设置,然后使用了8次展开的循环:

mov rax, QWORD PTR [rdx+r11*8-64]
mov r10, QWORD PTR [r8+r11*8-64]
adc rax, r10
mov QWORD PTR [rcx+r11*8-64], rax

然后是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寄存器交换字吗？

我非常感谢任何评论.

这是一个问题,从项目欧拉,而这个问题包括一些源代码,所以认为这您的扰流板警报,如果你有兴趣自己解决它.不鼓励为问题分配解决方案,这不是我想要的.我真诚地需要在正确的方向上进行一点点推动和指导.

问题如下:

2 ^ 15 = 32768,其数字之和为3 + 2 + 7 + 6 + 8 = 26.

数字2 ^ 1000的数字总和是多少？

我理解问题的前提和数学,但我一周前才开始练习C#,所以我的编程充其量只是摇摇欲坠.

我知道int,long和double绝对不足以准确地保持2 ^ 1000的300+(基数10)数字,所以需要一些策略.我的策略是设置一个逐个获取数字的计算,并希望编译器能够计算出如何计算每个数字而没有像overflow这样的错误:

using System;
using System.IO;
using System.Windows.Forms;

namespace euler016
{
    class DigitSum
    {
        // sum all the (base 10) digits of 2^powerOfTwo
        [STAThread]
        static void Main(string[] args)
        {
            int powerOfTwo = 1000;
            int sum = 0;

            // iterate through each (base 10) digit of 2^powerOfTwo, from right to left
            for (int digit = …

如果我想传输任意精度的十进制值，在我的 protobuf 定义文件中使用的正确标量类型是什么？

我在 Go 代码中使用shopspring/decimal而不是 float64 来防止数学错误。在编写我的 protobuf 文件以通过 gRPC 传输这些值时，我可以使用：

• double 转换为 float64
• string 这肯定会以自己的方式精确，但让我觉得笨拙
• 来自mgravell/protobuf-net 的十进制之类的东西？

传统智慧教会我在货币应用程序中避开浮动，但我可能过于小心，因为它是序列化的一个点。