C++ BigInt 乘法概念问题
我正在用 C++ 构建一个小型 BigInt 库，以便在我的编程语言中使用。
结构如下：
short digits[ 1000 ];
int len;
我有一个函数，通过将字符串拆分为单个字符并将它们放入数字中，将字符串转换为bigint。
数字中的数字全部颠倒过来，因此数字 123 如下所示：
digits[0]=3 digits[1]=3 digits[2]=1
我已经成功编写了添加函数，该函数运行良好。
它的工作原理有点像这样：（
overflow = 0
for i ++ until length of both numbers exceeded:
add numberA[ i ] to numberB[ i ]
add overflow to the result
set overflow to 0
if the result is bigger than 10:
substract 10 from the result
overflow = 1
put the result into numberReturn[ i ]
在这种情况下，溢出是当我将 1 加到 9 时发生的情况：从 10 中减去 10，将 1 添加到溢出，溢出添加到下一个数字）
所以想想如何存储两个数字，就像那些：
0 | 1 | 2
---------
A 2 - -
B 0 0 1
上面表示 bigint 2 (A) 和 100 (B) 的数字。 - 表示未初始化的数字，无法访问它们。
所以添加上面的数字效果很好：从 0 开始，加 2 + 0，转到 1，加 0，转到 2，加 1
但是：
当我想用上面的结构进行乘法时，我的程序最终执行以下操作：
从 0 开始，将 2 与 0 相乘（eek），转到 1，...
所以很明显，对于乘法，我必须得到这样的顺序：
0 | 1 | 2
---------
A - - 2
B 0 0 1
然后，一切都会是明确：从 0 开始，将 0 与 0 相乘，转到 1，将 0 与 0 相乘，转到 2，将 1 与 2 相乘
- 我如何设法将
数字放入乘法的正确形式？ - 我不想做任何阵列移动/翻转 - 我需要性能！
I'm building a small BigInt library in C++ for use in my programming language.
The structure is like the following:
short digits[ 1000 ];
int len;
I have a function that converts a string into a bigint by splitting it up into single chars and putting them into digits.
The numbers in digits are all reversed, so the number 123 would look like the following:
digits[0]=3 digits[1]=3 digits[2]=1
I have already managed to code the adding function, which works perfectly.
It works somewhat like this:
overflow = 0
for i ++ until length of both numbers exceeded:
add numberA[ i ] to numberB[ i ]
add overflow to the result
set overflow to 0
if the result is bigger than 10:
substract 10 from the result
overflow = 1
put the result into numberReturn[ i ]
(Overflow is in this case what happens when I add 1 to 9: Substract 10 from 10, add 1 to overflow, overflow gets added to the next digit)
So think of how two numbers are stored, like those:
0 | 1 | 2
---------
A 2 - -
B 0 0 1
The above represents the digits of the bigints 2 (A) and 100 (B).- means uninitialized digits, they aren't accessed.
So adding the above number works fine: start at 0, add 2 + 0, go to 1, add 0, go to 2, add 1
But:
When I want to do multiplication with the above structure, my program ends up doing the following:
Start at 0, multiply 2 with 0 (eek), go to 1, ...
So it is obvious that, for multiplication, I have to get an order like this:
0 | 1 | 2
---------
A - - 2
B 0 0 1
Then, everything would be clear: Start at 0, multiply 0 with 0, go to 1, multiply 0 with 0, go to 2, multiply 1 with 2
- How can I manage to get
digitsinto the correct form for multiplication? - I don't want to do any array moving/flipping - I need performance!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
short在[0..9]中存储数字char就足够了B与A中的每个数字相乘，并将它们按正确的 10 次方移位求和。编辑：由于一些匿名者在没有评论的情况下对此投了反对票，这基本上是乘法算法：
B与A[i]的乘法是通过一个额外的 for 循环，您还可以在其中跟踪进位。(10 ^ i)是通过偏移目标索引来实现的，因为 bigint 以 10 为基数。shortto store digits in the[0..9]acharwould sufficeBwith each digit inAand sums them up shifted with the correct power of ten.EDIT: Since some anonymous downvoted this without a comment this is basically the multiplication algorithm:
The multiplication of
BwithA[i]is done by an extra for loop where you also keep track of the carry. The(10 ^ i)is achieved by offseting the destination indices since bigint is in base 10.在我看来，你在问题中的例子是过度设计的。由于涉及乘法和加法的剪切次数，您的方法最终将比正常的长乘法更慢。当您一次可以乘以大约 9 时，不要限制自己一次只计算一位基数！。将 base10 字符串转换为一个巨大的值，然后对其进行操作。 不要直接对字符串进行操作。你会发疯的。这是一些演示加法和乘法的代码。更改
M以使用更大的类型。您也可以使用 std::vector，但是您会错过一些优化。Your example in the question is over-engineering at its best in my opinion. Your approach will end up even slower than normal long multiplication, because of the shear number of multiplications and additions involved. Don't limit yourself to working at one base digit at a time when you can multiply approximately 9 at a time!. Convert the base10 string to a hugeval, and then do operations on it. Don't do operations directly on the string. You will go crazy. Here is some code which demonstrates addition and multiplication. Change
Mto use a bigger type. You could also use std::vector, but then you miss out on some optimizations.好吧，看到这个问题大约 11 年前就得到了回答，我想我将为正在编写自己的 BigInt 库的人提供一些指导。
首先，如果您想要的是纯粹的性能而不是研究如何实际编写高性能代码，请学习如何使用 GMP 或 OpenSSL。要达到 GMP 的性能水平，有一个非常陡峭的学习曲线。
好吧，让我们开始吧。
CPU 擅长加减乘除，所以要充分利用它们。
假设您有两个 BigInt，
当它们可以对基数 2^32 进行 1 次计算时，不要让它们以基数 10 进行 50 次计算：
如果您的计算机可以表示的最大数字是 2^64-1，则使用 2^32-1 作为BigInt 的基数，因为它将解决乘法时实际溢出的问题。
使用支持动态内存的结构。扩展你的程序来处理两个一百万位数的乘法可能会破坏你的程序，因为它在堆栈上没有足够的内存。在 C 中使用 std::vector 代替 std::array 或 raw int[] 来利用内存。
了解SIMD以提升您的计算性能。菜鸟代码中的典型循环无法同时处理多个数据。学习这一点应该可以将速度提高 3 到 12 倍。
了解如何编写自己的内存分配器。如果您使用 std::vector 来存储无符号整数，那么稍后您可能会遇到性能问题，因为 std::vector 仅用于一般目的。尝试根据自己的需要定制分配器，以避免每次执行计算时都进行分配和重新分配。
了解计算机的体系结构和内存布局。编写自己的汇编代码来适应特定的 CPU 架构肯定会提高您的性能。这也有助于编写您自己的内存分配器和 SIMD。
算法。对于小型 BigInt，您可以依靠小学乘法，但随着输入的增加，一定要好好看看 Karatsuba、Toom-Cook，最后是 FFT，以便在您的库中实现。
如果您遇到困难，请访问我的 BigInt 库。它没有自定义分配器、SIMD 代码或自定义汇编代码，但对于 BigInteger 的初学者来说应该足够了。
Alright seeing that this question is answered almost 11 years ago, I figure I'll provide some pointers for the one who is writing their own BigInt library.
First off, if what you want is purely performance instead of studying how to actually write performant code, please just learn how to use GMP or OpenSSL. There is a really really steep learning curve to reach the level of GMP's performance.
Ok, let's get right into it.
CPUs are god-level good at addition, subtraction, multiplication, and division, so take advantage of them.
Suppose you have two BigInt
Don't make them do 50 calculations in base 10 when they could do 1 calculations of base 2^32:
If the biggest number your computer can represent is 2^64-1, use 2^32-1 as the base for your BigInt, as it will solve the problem of actually overflowing when doing multiplication.
Use a structure that supports dynamic memory. Scaling your program to handle the multiplication of two 1-million digits numbers would probably break you program since it doesn't have enough memory on the stack. Use a std::vector instead of std::array or raw int[] in C to make use of your memory.
Learn about SIMD to give your calculation a boost in performance. Typical loops in noobs' codes can't process multiple data at the same time. Learning this should speed things up from 3 to 12 times.
Learn how to write your own memory allocators. If you use std::vector to store your unsigned integers, chances are, later on, you'll suffer performance problems as std::vector is only for general purposes only. Try to tailor your allocator to your own need to avoid allocating and reallocating every time a calculation is performed.
Learn about your computer's architecture and memory layout. Writing your own assembly code to fit certain CPU architecture would certainly boost your performance. This helps with writing your own memory allocator and SIMD too.
Algorithms. For small BigInt you can rely on your grade school multiplication but as the input grows, certainly take a good look at Karatsuba, Toom-Cook, and finally FFT to implement in your library.
If you're stuck, please visit my BigInt library. It doesn't have custom allocator, SIMD code or custom assembly code, but for starters of BigInteger it should be enough.
安德烈亚斯是对的，你必须将一个数字乘以另一个数字的每一位，然后将结果相加。我认为最好将较长的数字乘以较短的数字。如果您在数组 char 中存储十进制数字确实就足够了，但是如果您想要性能，也许您应该考虑更大的类型。我不知道您的平台是什么，但例如在 x86 的情况下，您可以使用 32 位整数和硬件支持来给出 32 位乘法的 64 位结果。
Andreas is right, that you have to multiply one number by each digit of the other and sum the results accordingly. It is better to multiply a longer number by digits of the shorter one I think. If You store decimal digits in Your array char would indeed suffice, but if you want performance, maybe you should consider bigger type. I don't know what Your platform is, but in case of x86 for example You can use 32 bit ints and hardware support for giving 64 bit result of 32 bit multiplication.
为什么？有一些优秀的现有 bigint 库（例如 gmp、gmp、tommath），您可以直接使用，而不必从头开始编写自己的。自己制作需要大量工作，而且结果在性能方面不太可能那么好。 （特别是，编写快速代码来执行乘法和除法比乍一看要困难得多。）
Why? There are some excellent existing bigint libraries out there (e.g., gmp, tommath) that you can just use without having to write your own from scratch. Making your own is a lot of work, and the result is unlikely to be as good in performance terms. (In particular, writing fast code to perform multiplies and divides is quite a lot trickier than it appears at first glance.)