如何编写解决方案以处理大量数字？ [英] How to Code a Solution To Deal With Large Numbers?

问题描述

我在做一些欧拉计画的问题，并且大多数时候，计算涉及到除int，float，double等之外的大量数字。

I'm doing some Project Euler problems and most of the time, the computations involve large numbers beyond int, float, double etc.

首先，我知道我应该寻找更有效的计算方法，以避免出现大量问题。 我听说过Bignum库。

Firstly, I know that I should be looking for more efficient ways of calculation so as to avoid the large number problem. I've heard of the Bignum libraries.

但是，为了学术界的利益，我会想知道如何编写自己的解决方案。

请问有什么专家可以帮助我吗？ （我的语言是C）

推荐答案

您需要将大数字存储在计算机可以轻松存储的基础上处理其本机类型，然后将数字存储在可变长度数组中。为了简单起见，我建议您先将数字存储在10以内，以了解如何执行此操作。

You need to store the big numbers in a base that your computer can easily handle with its native types, and then store the digits in a variable length array. I'd suggest that for simplicity you start by storing the numbers in base 10 just to get the hang of how to do this. It will make debugging a lot easier.

一旦有了一个可以以这种形式存储数字的类，则只需实现加，减，乘运算即可。等等。每个操作都必须遍历其操作数的位数并进行组合，请小心正确地进行携带，以使您的位数永远不会大于基数。加减法很简单。乘法需要更多的工作，因为朴素的算法需要嵌套循环。然后，一旦完成工作，就可以尝试以有效的方式实现幂运算（例如重复平方）。

Once you have a class that can store the numbers in this form, it's just a matter of implementing the operations add, subtract, multiply, etc. on this class. Each operation will have to iterate over digits of its operands and combine them, being careful to carry correctly so that your digits are never larger than the base. Addition and subtraction are simple. Multiplication requires a bit more work as the naive algorithm requires nested loops. Then once you have that working, you can try implementing exponentiation in an efficient manner (e.g. repeated squaring).

如果您打算编写 serious bignum实现，以10为底的数字将不会减少。这会浪费内存，而且速度会很慢。您应该选择计算机的自然基准，例如256或字长（2 ** 32）。但是，这会使简单的操作变得更加困难，因为如果您天真地将两位数字相加，就会溢出，因此您将需要非常小心地处理它。

If you are planning to write a serious bignum implementation, base 10 won't cut it. It's wasteful of memory and it will be slow. You should choose a base that is natural for the computer, such as 256 or the word size (2**32). However this will make simple operations more difficult as you will get overflows if you naively add two digits, so you will need to handle that very carefully.

这篇关于如何编写解决方案以处理大量数字？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！