问题标签 [bignum]

我有一个格式化为这样的字符串的 bignum：“123456789123456789123456789”，我需要检查是否设置了指定的位。此字符串中的组件是个位数。

如果我想检查是否设置了第 54 位，通常我会这样做：NyNumber&(1<<54)

问题是我正在使用的 bignum 库中没有 AND 或 SHIFT。

所以问题是；如何检查一个位是否设置为格式为任意大小的字符串的数字？

编辑：澄清一下：我正在使用一种名为Autoit3的小型脚本语言和以下库：http : //www.autoitscript.com/forum/topic/83529-bignum-udf 将 BigNums 表示为字符串。

我正在尝试计算 Ruby 中一个非常大的数字的平方根。我遇到的问题是 Math.sqrt 函数看起来像这样

sqrt(numeric) → float

如果我给它一个非常大的数字，它会给我 FloatDomainError: Infinity。

sqrt()返回 BigNum的最佳方法是什么？这可能有一个宝石，还是我必须编写自己的函数来计算平方根？

在这种情况下，最简单的方法是什么？泰勒级数？数字的平方根总是整数。

我正在尝试将 SHA-2 256 位校验和存储在列中：

我像这样存储值：

在将 big_num 分配给 c.value 时，我得到：

有人知道我在做什么错吗？

我正在解决一个简单的组合问题，其解决方案是 2^(n-1)。

唯一的问题是 1 <= n <= 2^31 -1（有符号 32 位整数的最大值）

我尝试使用 Java 的 BigInteger 类，但它对于 2^31/10^4 及更大的数字会超时，所以这显然行不通。

此外，我仅限于使用 Java 或 C++ 的内置类。

知道我需要速度，我选择用 C++ 构建一个对字符串进行算术运算的类。

现在，当我进行乘法运算时，我的程序的乘法类似于我们在纸上进行乘法以提高效率（而不是重复添加字符串）。

但即使这样，我也不能将 2 自身乘以 2^31 - 1 次，它只是不够有效。

因此，我开始阅读有关该问题的文本，并得出了...的解决方案

2^n = 2^(n/2) * 2^(n/2) * 2^(n%2)（其中 / 表示整数除法，% 表示模数）

这意味着我可以求解对数乘法的幂运算。但对我来说，我无法绕过如何将此方法应用于我的代码？如何选择下限以及跟踪最终乘法所需的各种数字的最有效方法是什么？

如果有人对如何解决此问题有任何了解，请详细说明（示例代码表示赞赏）。

更新

感谢大家的帮助！显然，这个问题应该以一种现实的方式来解决，但我确实设法java.math.BigInteger用只执行 ceil(log2(n)) 迭代的幂函数来超越。

如果有人对我生成的代码感兴趣，这里是......

编译器： MinGW/GCC
问题：不允许使用 GPL/LGPL 代码（GMP 或任何 bignum 库对于这个问题来说太过分了，因为我已经实现了该类）。

我已经构建了自己的128 位固定大小的大整数类（旨在用于游戏引擎，但可以推广到任何用例），我发现当前乘法和除法运算的性能非常糟糕（是的，我已经对它们进行了计时，见下文），并且我想改进（或更改）执行低级数字运算的算法。

当涉及到乘法和除法运算符时，与类中的其他所有内容相比，它们的速度慢得令人无法忍受。

这些是相对于我自己的计算机的近似测量值：

正如你所看到的，仅仅做乘法比加法或减法慢很多很多倍。除法比乘法慢大约 10 倍。

我想提高这两个运算符的速度，因为每帧可能要进行大量的计算（点积、各种碰撞检测方法等）。

结构（省略方法）看起来有点像：

乘法目前使用典型的长乘法方法（在汇编中以便我可以捕捉EDX输出）完成，同时忽略超出范围的单词（也就是说，我只做 10mull与 16 相比）。

除法使用移位减法算法（速度取决于操作数的位数）。但是，它不是在组装中完成的。我发现这有点难以收集，并决定让编译器对其进行优化。

我已经在谷歌上搜索了几天，查看描述算法的页面，例如Karatsuba 乘法、高基除法和牛顿-拉普森除法，但数学符号有点超出我的想象。我想使用其中一些高级方法来加速我的代码，但我必须先将“希腊语”翻译成可以理解的东西。

对于那些可能认为我的努力“过早优化”的人；我认为这段代码是一个瓶颈，因为非常初级的数学运算本身变得很慢。我可以忽略对高级代码的这种类型的优化，但是这个代码将被调用/使用到足以让它变得重要。

我想建议我应该使用哪种算法来改进乘法和除法（如果可能的话），以及对建议算法如何工作的基本（希望易于理解）解释将不胜感激。

编辑：乘以改进

我能够通过将代码内联到 operator*= 来改进乘法运算，并且它看起来尽可能快。

这是一些基本代码供您检查（请注意，我的类型名称实际上是不同的，为简单起见已对其进行了编辑）：

至于除法，检查代码是毫无意义的，因为我需要更改数学算法才能看到任何实质性的好处。唯一可行的选择似乎是高基数除法，但我还没有确定（在我看来）它是如何工作的。

我仍在研究 C++ 中任意长整数的例程。到目前为止，我已经为 64 位 Intel CPU 实现了加法/减法和乘法。

一切正常，但我想知道是否可以通过使用 SSE 来加快速度。我浏览了 SSE 文档和处理器指令列表，但找不到任何我认为可以使用的东西，原因如下：

• SSE 有一些整数指令，但大多数指令处理浮点数。它看起来不像是为使用整数而设计的（例如，是否有整数比较少？）

• SSE 的思想是 SIMD（同一指令，多数据），因此它提供了 2 或 4 个独立操作的指令。另一方面，我想要一个 128 位整数加法（128 位输入和输出）。这似乎不存在。（然而？也许在 AVX2 中？）

• 整数加法和减法既不处理输入也不处理输出进位。所以手工操作非常麻烦（因此很慢）。

我的问题是：我的评估是正确的还是我忽略了什么？长整数例程可以从 SSE 中受益吗？特别是，他们可以帮助我编写更快的 add、sub 或 mul 例程吗？

使用 iOS vecLib BigNum.h vU1024 数据类型，我应该如何使用一些数字进行初始化？

例如，我如何在其中获得大数字 938429845792837192837293487293458734985791823123918237？

谢谢。

我认为 Scheme 有一个内置类型 Bignum 用于处理任意大的数字，但是如果我想自己实现它，我该怎么做呢？

如果我没记错的话，它有以下语法：|n| = () 当 n=0 |n| = (r . |q|) 其中 n=qN+r, 0<=r

例如，当基数 N=16 时，|33| = (1 2) 其中 1 是余数，2 是商。

PS：使用 bignum 实现我怎么能去下一个数字（后继）和前一个数字（前任），这样successor |n| = |n+1|和predecessor |n+1| = |n|

我正在使用密码学，需要使用一些非常大的数字。我还在使用新的 Intel 指令进行需要 m128i 数据类型的无进位乘法，这是通过将浮点数据作为其参数的函数加载它来完成的。

我需要存储 2^1223 整数，然后将其平方并存储该值。

我知道我可以使用 GMP 库，但我认为创建两种存储值（如 2^1224 和 2^2448）的数据类型会更快。它的开销会更少。我将使用 karatsuba 将数字相乘，因此我需要对数据类型执行的唯一操作是加法，因为我将分解数字以适应 m128i。

有人可以指导我朝着可以帮助我创建所需整数大小的材料方向发展吗？

C# 是否支持任意精度算术（我认为这也称为 bignums）？

如果不支持，哪些库支持它？