大数字，通用算法？
我想知道什么是大数字，以及用于处理它们的一些常见算法是什么。我在《Coders at Work》中听到这个术语，其中有人在采访中被要求创建一个库来处理大数字。
I was wondering what big numbers are, and what are some common algorithms used to handle them. I heard this term mentioned in Coders at Work, where one was asked in an interview to create a library to work with big numbers.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
大数字通常是全精度整数或小数，而不是浮点数（浮点数也可以存储非常大的数字，但精度非常有限）。它们主要用于密码学。以 RSA 密钥为例：这些密钥是 1024 或 2048 位的整数（大约 300 或 600 位十进制数字）。它们需要很长才能使用暴力计算破解加密。
库需要提供的是支持存储这些数字并对它们执行计算（例如加法、乘法、整数除法）
Big numbers are usually full-precision integers or decimals, as opposed to floating point numbers (which can also store very large numbers, but with a very limited precision). They are mostly used in cryptography. Take for example RSA keys: Those are integers with 1024 or 2048 bits (roughly 300 or 600 decimal digits). They need to be long to make it unfeasible to break the encryption using brute-force calculations.
What a library needs to provide is support to store these numbers and perform calculations on them (e.g. addition, multiplication, integer division with rest)
有像 gmp 这样的 bignum 库 - 有些提供任意精度（...只要你的内存可以处理），有些有简单荒谬的限制 - 256 字节基数、256 字节尾数的浮点变量。
这些方法与 FPU 的普通软件模拟非常相似，只是为每次计算迭代更多字节的数据，操作类似于纸上的计算方式。如果你有 256 字节整数，它可以被视为普通的 256 base256 位数字...
简单的 256 字节整数加法（完全未优化...数字应该保持长度等）
There are bignum libraries like gmp - some provide arbitrary precision (...as much as your memory can handle), some have simply ridiculous limits - floating point variables of 256 bytes base, 256 bytes mantissa.
The methods are very similar to normal software emulation of FPU, simply iterating over way more bytes of data for each calculation, operations resembling how you calculate it on paper. If you have 256-byte integer, it can be treated as a normal 256 base256 digits number...
simple 256-byte integer addition (totally unoptimized... the numbers should keep lengths etc)
这些是具有可变位长度的数字，与具有预定义大小的数字（例如，4 位整数类型）不同。
处理大数的快速 C++ 库的一个示例是 NTL，也专门用于数论和密码学应用。另一个著名的工具是 unix bc 计算器，默认情况下其精度不受限制。一些函数式语言（例如 Haskell）也使用这种类型的数字。
用于处理大数算术的方法示例是用于乘法的 Karatsuba 算法。如果您感兴趣的话，您可以在 NTL 的文档中找到更多内容；）
These are numbers with variable bit-length, unlike numbers with predefined size (e.g. 4-bit integer type).
An example of a fast C++ library working with big numbers is NTL, also used especially for number theory and cryptography application. Another well-known tool is the unix bc calculator that by default works with unlimited precision. Some functional languages like Haskell use this type of numbers as well.
Example of approaches used for dealing with large number arithmetics is Karatsuba algorithm used for multiplication. In the docs of NTL you can find much more if you're interested ;)