我应该使用什么数据结构来创建我自己的“BigInteger”类？ [英] What data-structure should I use to create my own "BigInteger" class?

问题描述

作为一个可选的作业，我正在考虑编写我自己的BigInteger类的实现，在这里我将提供自己的加法，减法，乘法等方法。

这将是任意长的整数，甚至数百位数字。

在对这些数字进行数学运算时，数字并不难，你认为最好的数据结构将是代表我的BigInteger？

起初我正在考虑使用一个数组，但是我以为我仍然可能会溢出在阵列插槽之后）经过大量的加法或乘法。使用链表可能是一个很好的例子，因为我可以用O（1）时间复杂度来处理数字？

是否有其他数据结构比一个链表更适合？我的数据结构所持有的类型是我可以使用的最小可能的整数类型吗？

另外，我应该如何保存我的进位变量？是否应该是我的BigInteger类型？

解决方案

查看这本书 C接口和实现 David R. Hanson。它有2章关于这个主题，涵盖了矢量结构，字大小和许多其他可能遇到的问题。

它是针对C编写的，但大部分是适用于C ++和/或Java。而且如果你使用C ++，那将会更简单一点，因为你可以使用类似 std :: vector 来管理你的数组分配。

As an optional assignment, I'm thinking about writing my own implementation of the BigInteger class, where I will provide my own methods for addition, subtraction, multiplication, etc.

This will be for arbitrarily long integer numbers, even hundreds of digits long.

While doing the math on these numbers, digit by digit isn't hard, what do you think the best datastructure would be to represent my "BigInteger"?

At first I was considering using an Array but then I was thinking I could still potentially overflow (run out of array slots) after a large add or multiplication. Would this be a good case to use a linked list, since I can tack on digits with O(1) time complexity?

Is there some other data-structure that would be even better suited than a linked list? Should the type that my data-structure holds be the smallest possible integer type I have available to me?

Also, should I be careful about how I store my "carry" variable? Should it, itself, be of my "BigInteger" type?

解决方案

Check out the book C Interfaces and Implementations by David R. Hanson. It has 2 chapters on the subject, covering the vector structure, word size and many other issues you are likely to encounter.

It's written for C, but most of it is applicable to C++ and/or Java. And if you use C++ it will be a bit simpler because you can use something like std::vector to manage the array allocation for you.

这篇关于我应该使用什么数据结构来创建我自己的“BigInteger”类？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！