logo标签列表

我应该使用哪种数据结构来创建自己的“BigInteger”类？

javac++data-structuresbiginteger
14
作为一项可选任务，我想写一个自己的BigInteger类的实现，其中我将提供自己的加法、减法、乘法等方法。
这将用于任意长的整数，甚至可以达到数百位。
尽管对这些数字进行按位数的计算并不难，但您认为最好的数据结构是什么来表示我的“BigInteger”呢？
一开始我考虑使用一个数组，但随后我认为在大量的加法或乘法后，我仍然有可能会溢出（用完数组槽）。这是否是使用链表的好时机，因为我可以使用O(1)时间复杂度添加数字？
除了链表之外，还有其他更适合的数据结构吗？我的数据结构所持有的类型应该是我可用的最小整数类型吗？
此外，我应该注意如何存储我的“进位”变量吗？它本身应该是我的“BigInteger”类型吗？
2
(a) 我认为你不应该使用链表，因为一些操作需要（或者受益于）随机访问。此外，由于内存分配过多，链表的速度很慢。 (b) 如果你使用最小的整数，则使用的内存最少，但如果使用与字（即“int”）大小匹配的内容，则速度更快。因此，这取决于你最关心的问题。一个明显的可能性是将整数类型作为类的模板参数。 (c) 检查GNU MP库，如果复制他们的设计决策，你不会错。 - Manuel
1
这是Java的BigInteger类的源代码：http://kickjava.com/src/java/math/BigInteger.java.htm - Manuel
10个回答
3
请查看David R. Hanson所著的书籍《C Interfaces and Implementations》，其中有两章关于此主题，涵盖了向量结构、字长和许多其他可能遇到的问题。
这本书是为C语言编写的，但大部分内容也适用于C++和/或Java。如果您使用C ++，则会更简单一些，因为您可以使用像std :: vector 这样的东西来管理数组分配。
http://code.google.com/p/cii/source/browse/trunk/src/ap.chttp://code.google.com/p/cii/source/browse/trunk/examples/calc.c - slf
1

始终使用最小的 int 类型来完成所需的工作（字节）。链表应该很好地工作，因为您不必担心溢出。

我会用2 **（machine_word-1）（32位机器为65536进制）来编写它。为什么要浪费时间处理单个字节，当你可以一次处理整个字？ - Tadeusz A. Kadłubowski
溢出并不是一个真正的问题，他可以使用向量或双端队列，这两种数据结构对于此应用程序来说比链表更高效。 - Manuel
4
我不相信2的31次方等于65536。 - Ponkadoodle
1
一个std::list每个节点使用两个链接指针。在64位系统上，这将是16字节的链接和1字节的数据...这会被填充到8字节。这项工作的适当类型是int，它可以是64位、32位（甚至16位）——类应该检测并在必要时进行调整。此外，链表完全不合适。 - Potatoswatter
为什么需要一个列表呢？为什么不只使用一个整数和一个计数器，当整数达到最大值时，将其设置为0并增加计数器...例如："integer + counter * Max_Integer"。这将作为字符串输出。 - Anthony Raimondo
1

如果您使用二叉树（其叶子为整数），则可以通过更简单的分治算法获得链表的所有优点（无限数量的数字等）。在这种情况下，您没有单个基数，而是取决于您所工作的级别。

如果您这样做，需要使用BigInteger来进行进位。您可能认为“整数链表”方法的优点是，进位始终可以表示为int（对于任何基数都是如此，而不仅仅是基数10，因为大多数答案似乎假定您应该使用基数10...在任何基数下，进位始终是一个数字）

我不妨说一下：如果您可以使用2^30或2^31，那么使用基数10将是一种可怕的浪费。

1

访问链表元素速度较慢。我认为数组是更好的选择，需要进行大量的边界检查和运行时数组调整。

澄清：遍历链表和遍历数组都是O(n)操作。但是，遍历链表需要在每一步中解引用指针。仅仅因为两个算法具有相同的复杂度，并不意味着它们运行所需的时间相同。在链表中分配和释放n个节点的开销也比单个大小为n的数组的内存管理要重得多，即使该数组需要调整大小几次。

1
它们为什么慢？我没有对任何这些操作进行随机访问，只是顺序访问。这将使链表在顺序访问时与向量一样快，并且在插入方面速度更快。 - Fifa89
@Fifa89 - 链表在中间插入元素的速度更快，但根据您想要做的事情，在末尾添加元素时，向量或双端队列的速度同样快。 - Manuel
@Manuel，我一直看到你这么说，但你能否提供一个展示它的答案？据我所知，链表提供O(1)的插入时间，而向量提供摊销的O(1)插入。你能详细说明一下是什么使向量更快吗？ - Fifa89
@Fifa89 - 我假设你只会在结尾添加元素（使用push_back）。链表会在每次push_back时分配内存，而向量则是每N个push_backs分配一次。对于像BigNum这样性能敏感的类，这将产生巨大的差异。 - Manuel
@Fifa89 - 你确定链表的遍历速度和向量上的相同操作一样快吗？我确信对于大型BigNums，向量会导致更少的缓存未命中。 - Manuel
@Fifa89，@Manuel：只要数字适合缓存，两者都将是线性时间，没有缓存未命中。然而，链表将受到所需遍历它的L1 命中 数量的限制，因为您必须访问所有链接。此外，由于链表使用指针填充缓存，因此链表将在较小的数字下填满缓存并导致未命中。 - Potatoswatter
1

哇，这里有一些……有趣的答案。我建议阅读一本书，而不是尝试整理所有这些矛盾的建议。

话虽如此，C/C++也不适合这个任务。大整数是一种扩展精度数学。大多数CPU提供处理扩展精度数学的指令，速度（每指令位数）与正常数学相当或相同。当你加上2^32+2^32时，答案是0……但处理器ALU还有一个特殊的进位输出，程序可以读取和使用。

C++无法访问该标志，在C中也没有办法。你必须使用汇编语言。

只是为了满足好奇心，您可以使用标准布尔运算来恢复进位位等。但是最好下载现有库。

1
如果他想使用现有的库，他只需使用他在帖子中提到的BigInteger类。有时人们做事是为了学习而不是投入某些生产环境中。我认为这是一个很好的计算机科学作业，每个计算机科学专业的学生都应该在某个时候完成它。 - mmcdole
@simucal：还有学习一些扩展乘法和加法所需的汇编语言，这也是很有教育意义的... - Potatoswatter
0

我会说是一个整数数组。

2
你能否至少解决我提到的有关那个实现的问题吗？ - Fifa89
0

如果你打算使用BCD，我会建议使用std :: vector of char（因为它只需要保存0-9）

如果不是BCD，则使用int的vector（你没有明确说明）

与链接列表相比，空间开销要小得多

所有建议都说“除非你有充分的理由不这样做，否则请使用vector”

嗯...我认为在这里使用二进制数学会比使用十进制数字更好... - Inverse
嗯 - BCD 是一个常见的大整数实现方式。他没有说他打算做什么。 - pm100
0

数组确实是一个自然的选择。当你在内存中没有足够的空间时，抛出OverflowException是可以接受的。老师会注意到细节。

乘法大致将数字加倍，加法最多增加1。很容易创建一个足够大的数组来存储你的操作结果。

在乘法中，进位最多只有一位数（9*9 = 1，进位8）。一个int就足够了。

乘法的结果大约是digits_a + digits_b + [0-2]位数字，这个积不会超过较大输入数的两倍，但可能远远小于这个值。 - dmckee --- ex-moderator kitten
0

std::vector<bool>或std::vector<unsigned int>可能是你想要的。在需要更多空间进行乘法等操作时，你需要使用push_back()或resize()。此外，如果你使用的是补码，请记得推入正确的符号位。

2
说实话，我不认为std::vector<bool>是一个好的选择。 - Manuel
0

通常情况下，除非你需要经常在序列中间插入元素，否则使用std::vector而不是std::list。向量往往更快，因为它们是连续存储的，从而受益于更好的空间局部性（这是现代平台上的一个主要性能因素）。

确保使用对平台自然的元素。如果您想要平台无关性，请使用long。请记住，除非您有一些特殊的编译器内置函数可用，否则您需要一个至少两倍大的类型来执行乘法。

我不明白为什么你想让进位成为一个大整数。对于加法，进位是一个单独的比特，对于乘法，进位是元素大小的。

确保阅读Knuth的《计算机程序设计艺术》，其中描述了与任意精度算术相关的算法。

我可以问一下为什么是long类型吗？这是否有保证能够映射到架构的字长上？ - Manuel
没有确切的答案，这只是一个有根据的猜测（在Intel上使用MSVC和GCC时，它映射到自然字大小）。 - avakar
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接