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

问题描述

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

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.

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

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"?

一开始我考虑使用一个数组，但是我想我仍然可能溢出出阵列槽）在大的加或乘之后。这是一个很好的情况下使用链表，因为我可以处理数字与O（1）时间复杂性？

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?

推荐答案

查看 C Interfaces and Implementations by David R. Hanson。它有2章关于这个主题，涵盖了向量结构，字大小和许多其他问题，你可能会遇到。

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.

它是为C写的，但大部分是适用于C ++和/或Java。如果你使用C ++，它会更简单一些，因为你可以使用 std :: vector 来管理你的数组分配。

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屋！