问题标签 [bigint]

我正在使用 gmp 执行复杂的操作。我想用 Botan 来执行密码学功能。问题是它们都有自己的 Bigint 函数。因此，将 gmp 函数中使用的 bigint 值提供给 Botan 函数会产生问题。

有人可以帮忙吗？

我正在研究一个阶乘程序，当试图找到 1000 的阶乘时，程序没有工作。我认为大整数是解决方案；他们是如何工作的？（在 C 或 C++ 中）

STL 有 BigInt 类实现吗？（包含在容器中的多个数字的数字）

我在考虑一个大数除法的算法：用余数除以 bigint C 除以 bigint D，我们知道 C 在基数 b 中的表示，而 D 的形式为 b^k-1。在示例中显示它可能是最容易的。让我们尝试将 C=21979182173 除以 D=999。

• 我们将数字写成三位数：21 979 182 173
• 我们取连续集合的总和（模 999），从左边开始：21 001 183 356
• 我们将 1 添加到我们“超过 999”之前的那些集合：22 001 183 356

实际上，21979182173/999=22001183 和余数 356。

我已经计算了复杂度，如果我没记错的话，算法应该在 O(n) 中工作，n 是基 b 表示中 C 的位数。我还在 C++ 中做了一个非常粗略和未优化的算法版本（仅适用于 b=10），针对 GMP 的通用整数除法算法对其进行了测试，它确实似乎比 GMP 更好。我在任何地方都找不到这样的实现，所以我不得不求助于对一般部门进行测试。

我发现几篇文章讨论了似乎非常相似的问题，但没有一篇文章专注于实际实现，特别是在不同于 2 的基础上。我想这是因为数字在内部存储的方式，尽管提到的算法似乎有用，比如说，b = 10，即使考虑到这一点。我也尝试联系其他人，但同样无济于事。

因此，我的问题是：是否有文章或书籍或其他东西描述了上述算法，可能讨论了实现？如果不是，那么我尝试在 C/C++ 中实现和测试这样的算法是否有意义，或者这个算法在某种程度上是天生不好的？

另外，我不是程序员，虽然我在编程方面相当不错，但我承认我对计算机“内部结构”知之甚少。因此，请原谅我的无知——这篇文章中很可能有一件或多件非常愚蠢的事情。再次抱歉。

非常感谢！

进一步澄清评论/答案中提出的观点：

谢谢大家——因为我不想用同样的东西评论所有很棒的答案和建议，我只想谈谈你们中很多人提到的一点。

我完全清楚，一般来说，在 2^n 基础上工作显然是最有效的做事方式。几乎所有 bigint 库都使用 2^32 或其他。但是，如果（而且，我强调，它只对这个特定的算法有用！）我们将 bigints 实现为以 b 为底的数字数组，该怎么办？当然，我们在这里要求 b 是“合理的”：b=10，最自然的情况，似乎足够合理。我知道考虑到内存和时间，考虑到数字是如何在内部存储的，我知道它或多或少是低效的，但我已经能够，如果我的（基本的和可能有某种缺陷的）测试是正确的，比 GMP 的一般部门更快地产生结果，这将对实现这样的算法有意义。

Ninefingers 注意到在这种情况下我必须使用昂贵的模运算。我希望不会：我可以通过查看 old+new+1 的位数来查看 old+new 是否交叉，例如 999。如果它有 4 位数字，我们就完成了。更重要的是，由于old<999和new<=999，我们知道如果old+new+1有4位（不能多），那么，(old+new)%999等于删除( old+new+1)，我认为我们可以便宜地做到这一点。

当然，我不是在争论这个算法的明显局限性，也不是我声称它不能被改进——它只能除以特定类别的数字，我们必须先验地知道以 b 为基数的被除数的表示。但是，例如，对于 b=10，后者似乎很自然。

现在，假设我们已经实现了我上面概述的 bignums。说以 b 为底的 C=(a_1a_2...a_n) 和 D=b^k-1。该算法（可能会更加优化）会像这样。希望没有太多错别字。

• 如果k>n，我们显然完成了
• 在 C 的开头添加一个零（即 a_0=0）（以防我们尝试将 9999 与 99 相除）
• l=n%k （“常规”整数的 mod - 不应该太贵）
• old=(a_0...a_l) （第一组数字，可能少于 k 位）
• for (i=l+1; i < n; i=i+k) （我们将有 floor(n/k) 次左右的迭代）
  • 新=(a_i...a_(i+k-1))
  • new=new+old （这是 bigint 加法，因此 O(k)）
  • aux=new+1 （再次，bigint 加法 - O(k) - 我不满意）
  • 如果 aux 有超过 k 个数字
    • 删除 aux 的第一个数字
    • old=old+1 (bigint 再次加法)
    • 在开头用零填充旧的，所以它应该有尽可能多的数字
    • (a_(ik)...a_(i-1))=旧（如果 i = l+1，( a_0 ... a_l )=旧）
    • 新=辅助
  • 在开头用零填充新的，所以它应该有尽可能多的数字
  • (a_i...a_(i+k-1)=新
• quot=(a_0...a_(n-k+1))
• rem=新

在那里，感谢您与我讨论这个问题 - 正如我所说，这在我看来确实是一个有趣的“特例”算法，如果没有人看到它有任何致命缺陷，可以尝试实施、测试和讨论。如果这是迄今为止尚未广泛讨论的事情，那就更好了。请让我知道你的想法。对不起，很长的帖子。

此外，还有一些个人评论：

@Ninefingers：我实际上对 GMP 的工作原理、它的作用以及一般的 bigint 除法算法有一些（非常基本的！）知识，所以我能够理解你的大部分论点。我也知道 GMP 是高度优化的，并且在某种程度上为不同的平台定制了自己，所以我当然不会试图“打败它”——这似乎与用尖头棍子攻击坦克一样富有成效。然而，这不是这个算法的想法——它适用于非常特殊的情况（GMP 似乎没有涵盖）。在不相关的说明中，您确定在 O(n) 中完成了一般划分吗？我见过的最多的是M（n）。（如果我理解正确，那在实践中（Schönhage-Strassen 等）可能不会达到 O(n)。如果我是正确的，Fürer 的算法仍然没有达到 O(n)，几乎纯粹是理论上的。）

@Avi Berger：尽管想法相似，但这实际上似乎与“淘汰九点”并不完全相同。但是，如果我没记错的话，上述算法应该一直有效。

我想知道是否有任何其他 SO 可以推荐一个好的轻量级固定大小整数类型（128 位甚至 256 位，甚至可能是模板参数化）库。

我看过 GMP 和 co，他们非常关心，但对于我的目的来说有点太大了，我现在对简单的仅标头解决方案感兴趣。性能很重要，目标架构将是 x86 和 x86-64，也是一个合理的许可证（也不是 GPL 或 LGPL）。

我正在使用 Rails 3.0.5。我使用 MySQL 作为数据库存储。我有一个模型，其中一列需要是 BIGINT。我在创建迁移文件中使用以下内容：

效果很好。

但是，当我跑步时

耙分贝：迁移

生成的“schema.rb”文件为特定列创建以下行：

这是不正确的。

我的问题是我哪里错了？为了获得正确的“schema.rb”文件，我应该做些什么？我可以更改“schema.rb”文件的生成方式吗？

请注意，“schema.rb”文件错误的事实会导致我的持续集成服务器出现问题，该服务器运行测试并使用“schema.rb”文件从头开始（在运行测试之前）创建数据库。

我有一个带有 bigint 类型字段的表。该字段存储时间戳。我想像这样对字段进行日期格式：

我收到以下错误：

我们想在一个巨大的（100 Mio.行）SQL Server 表中将一列从 FLOAT(8) 转换为 BIGINT。我们不关心浮点数和精度损失。

由于我没有 SQL Server，但在本地使用 mysql，我想知道此操作是否会导致整个表副本，就像它对我的数据库所做的那样！？另一方面，我读到这将是一种隐式转换，因此只需几秒钟而不是几小时。

而不是设置一个 SQL Server 并在本地复制它可能需要很长时间”。

谢谢你的帮助！

我有这样的课：

在我的主要工作中，我在使用指针时无法避免复制：

我想我在矢量设计中缺少/没有管理一些东西。即使没有实例化一个新的 largeInt，我可以实现指针的无副本分配吗？谢谢各位专家！

嗯...我遇到了一个问题，我通过一个名为 BIGFLOAT http://www.fractal- Landscapes.co.uk/bigint.html，

我需要计算什么 0.4 ^(1000 或 100000000) 这个问题需要很长时间 我还没有学习并行或分布式编程，但我需要一个快速且易于理解的解决方案在接下来的 6 小时内交付这个项目！！:D

这是代码：

其中 K 是 1000 ， N 是 1001