标签: bigint

在C中处理大量数字的最简单方法是什么？我需要在区域1000 ^ 900中存储值...

有人知道一个简单的方法吗？真的很感激任何帮助!

我正在考虑一个大数除法的算法:用bigint D除以余数bigint C,我们知道基数b中C的表示,D是b ^ k-1的形式.在一个例子中展示它可能是最容易的.让我们尝试将C = 21979182173除以D = 999.

• 我们将数字写成三位数的集合:21 979 182 173
• 我们从左边开始采用连续集合的总和(模999):21 001 183 356
• 我们在"超过999"之前的那些集合中加1: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或其他.但是,如果(并且,我强调,它仅对这个特定算法有用!)我们将bigint实现为基数b中的数​​字数组？当然,我们要求b在这里"合理":b = 10,最自然的情况,似乎足够合理.我知道考虑到内存和时间,考虑到内部存储数字的方式或多或少效率不高,但我能够,如果我的(基本的和可能有些缺陷的)测试是正确的,产生的结果比GMP的一般部门更快,这对于实现这样的算法是有意义的.

Ninefingers通知我必须在这种情况下使用昂贵的模运算.我希望不是:我只能通过查看old + new + 1的位数来看看是否旧的+新交叉,比如说999.如果它有4位数字,我们就完成了.更重要的是,由于旧<999和新<= 999,我们知道如果旧+新+ 1有4位数(它不能有更多),那么,(旧+新)%999等于删除最左边的数字(老+新+ 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 …

我想要计算100!

我正在寻找使用C来实现这一目标的最简单方法.我已阅读但未找到具体答案.

如果你必须知道,我在Mac OS X中用Xcode编程.

谢谢!

当我解析这一小块JSON时

{ "value" : 9223372036854775807 }

这就是我得到的

{ hello: 9223372036854776000 } 

有没有办法正确解析它？

尝试使用bigint列创建表会创建一个标准整数列.怎么可能出错？我不知道从哪里开始寻找.

我在迁移中使用它:

create_table :table_name do |t|
  t.integer :really_big_int, limit: 8
end

我正在使用Ruby 1.9.2,PostgreSQL 9.0.3和Rails 3.0.9.我已经删除了数据库并多次运行迁移,但它仍然没有创建bigint列.

根据MySQL网站,签名的bigint可以达到18446744073709551615.如果我需要一个大于自动递增主键的数字怎么办？

我正在寻找一种方法来强制JSON.stringify始终打印BigInts 而不会抱怨。

我知道它是非标准的，我知道有一个纯 JavaScript 的包；但它不符合我的需求。我什至知道通过设置 来修复原始 JavaScript BigInt.prototype.toJSON。我需要的是某种方法来JSON.stringify在我的 TypeScript 代码中全局覆盖正常函数。

大约一年前，我发现了以下代码：

declare global
{
    interface BigIntConstructor
    {
        toJSON:()=>BigInt;
    }
}

BigInt.toJSON = function() { return this.toString(); };

在某些网页上我无法再次找到。它曾经在我的另一个项目中工作过，但现在似乎不再工作了。我不知道为什么。

无论我对上面的行做什么，如果我尝试打印包含 BigInt 的 JSON，我会得到：TypeError: Do not know how to serialize a BigInt。

如有任何帮助，我们将不胜感激 - 非常感谢。

我想将C#.NET存储ulong到T-SQL数据库中.我没有看到任何相关的规定,因为SQL bigint具有与正常相同的最小/最大值long.

有什么方法可以做到这一点吗？还是抓住了OverflowException我唯一的希望？

我正在寻找一个很好的基础BigInt类在C++中,我发现很多实现,但大多数时候,它是加密库的复杂实现...

基本上,我的意思是BigInt可以处理BigInt,long long和带有运算符重载的字符串.如果我有时间,我已经完成了自己,但我没有时间创建一个完整的BigInt类.

我有一个组合学问题,我希望能够在0和一个大整数之间随机选择一个整数.

我目前做法的不足之处

现在对于常规整数,我通常会写一些类似的东西int rand 500;并完成它.

但对于大整数来说,它看起来rand并不适合这个.

使用以下代码,我运行了200万次调用的模拟rand $bigint:

$ perl -Mbigint -E 'say int rand 1230138339199329632554990773929330319360000000 for 1 .. 2e6' > rand.txt

结果集的分布远非理想:

• 0(56计数)
• 幅度1e + 040(112计数)
• 幅度1e + 041(1411计数)
• 幅度1e + 042(14496计数)
• 幅度1e + 043(146324计数)
• 幅度1e + 044(1463824计数)
• 幅度1e + 045(计算373777)

因此,该过程永远无法选择一个类似的数字999,或者5e+020,这使得这种方法不适合我想要做的事情.

看起来这与任意精度有关rand,在测试过程中它永远不会超过15位数:

$ perl -E 'printf "%.66g", rand'
0.307037353515625

我怎样才能克服这个限制？

我最初的想法是,可能有一种方法可以影响精度rand,但感觉就像是一个更大问题的创可贴(即无法rand处理大整数).

无论如何,我希望有人之前走过这条路,并知道如何纠正这种情况.