简单处理大数

Fun@learn

1.50/5 (7投票s)

2007年11月23日

CPOL

2分钟阅读

29122

372

本文展示了如何使用长整型数组进行大数算术运算。该程序版本处理加法、减法和乘法运算。

引言

本文展示了如何操作非常大的数字。本文的目的是说明处理大数背后的基本逻辑。在阅读本文并浏览代码后，您将能够回答以下问题：

如何操作非常大的数字
如何添加、减去和乘以非常大的数字
将大型计算分解为更小的片段，轻松处理较小的问题，然后组合结果以获得大型问题的解决方案

背景

大数以 64 字节整数数组的形式表示。比如 12345678 存储为 element[0] =5678, element[1]=1234, element[2]=0000, element[3]= 0000

要添加两个这样的数字，使用以下逻辑：

BigNum1 = 0000 1234 1111 2222 
BigNum2 = 1111 2222 3333 4444 
---------------------------------------- 
BigNum1+BigNum2 = 1111 3456 4444 666

要乘以两个这样的数字，使用以下逻辑：
```
(a₁x +b₁)(a₂x+b₂) = a₁a₂x² + (a₁b₂+b₂a₁)x + b₁b₂ 
```

该逻辑可以进一步扩展到 x 的更多幂。

Using the Code

源代码由单个文件BigNum.cpp组成。代码中有一个BigNum 类。此类表示一个大于 64 位且小于 10³²- 1 的大数。有用于运算符 Addition(+)、Subtraction(-) 和 Multiplication(*) 的重载方法。还有一个名为void Normalize(BigNum)的方法。它将任何未以正确表示形式存在的BigNum 转换为 4 个长数字的数组，其中每个元素存储该数字的 8 位数字。

Addition 和 Subtraction 操作如下进行：

要添加和减去的两个BigNum 对象都已标准化。
Addition/subtraction 操作应用于相应的数组元素以形成新的BigNum。
再次标准化生成的BigNum 。这包含addition 或 subtraction的结果。

以下是addition的代码：

friend BigNum operator + (BigNum b1, BigNum b2 )
        { 
               BigNum b3;
               b1.Normalize();
               b2.Normalize();
 
               for( int i=0;i<4;i++)
               {
                       b3.no[i] = b1.no[i] + b2.no[i];
               }
               
               for( int i=0;i<3;i++)
               {
                       if ( b3.no[i] < b2.no[i])
                        b3.no[i] = b3.no[i] + 1;
               }
               b3.Normalize();
               return b3;
        }

Multiplication 操作如下进行：

要添加和减去的两个BigNum 对象都已标准化。
线性交叉乘法方法用于计算结果BigNum 变量中的每个单个数组元素。
结果BigNum 变量已标准化。

以下是multiplication的代码：

friend BigNum operator * (BigNum b1, BigNum b2 )
        {
               BigNum b3;
               b1.Normalize();
               b2.Normalize();
               
               b3.no[3] = b2.no[3]*b1.no[3];
               b3.no[2] = b2.no[2]*b1.no[3] + b2.no[3]*b1.no[2];
               b3.no[1] = b2.no[1]*b1.no[3] + b2.no[2]*b1.no[2] + b2.no[1]*b1.no[3];
               b3.no[0] = b2.no[0]*b1.no[3] + b2.no[1]*b1.no[2] + 
		b2.no[2]*b1.no[1] + b2.no[3]*b1.no[0];
    
               b3.Normalize();
               return b3;
        }

关注点

在撰写本文期间，我很好地了解了技术写作中出现的问题类型。老实说，这是我的第一篇此类文章，我很喜欢写这篇文章。该代码完全由我编写。欢迎提出关于清晰度、困惑、代码和技术写作的建议。也欢迎发表评论。您也可以发送电子邮件至 funatlearn@ontheedge.co.in，主题为 BigNum CodeProject 文章。

历史

该代码是该程序的第一个草案。因此，没有关于该代码的历史记录可用。虽然我肯定想增强代码并使其成为更高效和有用的实用程序，而不是限制其当前限制，但我有一些我自己的想法，并且非常欢迎您提出建议。

希望您喜欢理解代码。谢谢！