65.9K
CodeProject 正在变化。 阅读更多。
Home

多精度算术：减法算法

Andrea Simonassi
emptyStarIconemptyStarIconemptyStarIconemptyStarIconemptyStarIcon

0/5 (0投票)

2022年6月11日

CPOL

6分钟阅读

viewsIcon

5660

一种简单的多精度算术减法算法。

本文是系列文章的一部分

多精度算术：一个有趣的爱好项目

定义

减法是基本的算术运算之一，定义为加法的逆运算。

减法定义（作为加法的逆运算）：从A中减去B，意味着从A中移除B个项目，结果S使得B + S = A。

另一种定义：减法可以定义为倒计数操作。

9 – 5 = 从9开始倒数5次：8, 7, 6, 5, 4，结果是4。

注意：减法不是可交换的：9 – 5 不等于 5 – 9。

在自然数上，5 – 9 没有定义，因此减法仅对满足 A ∊ ℕ, B ∊ ℕ 且 A >= B 的数对 (A, B) 定义。

本文仅讨论 ℕ + 0 中的减法。

注意：计算机使用二进制补码表示法来表示固定大小的整数，但本文不采用这种方法，因为我使用的是不同的数字表示方式。

背景

简单减法

在十进制（其他进制也一样）中，要计算A - B 的结果，其中A和B是单个数字，手动使用笔和纸或算盘计算，您需要从9倒数到0：请记住，只有当A >= B 时，才能应用简单减法。

简单减法扩展

我们必须移除“只有当A >= B 时才能减去两个单个数字A和B”的限制，以便构建我们的算法。我们将引入借位（borrow）的概念，当CPU达到0时，它会溢出并从2寄存器大小 -1 开始继续计数：我们可以做同样的事情，例如：

5 - 9 = 从5开始倒数9次：4,3,2,1,0,（溢出，在纸上标记借位，从9继续计数），8,7,6：结果是6，并且我们有一个借位。

这对于应用我们稍后将介绍的长减法非常有用。

简单减法的一个有趣性质

简单减法的一个有趣性质是，无论基数b是多少，对于基数b的两个单个数字A和B，当B > A时，A – B将

  • 产生一个借位
  • 结果将始终是1位数字
  • 结果数字将大于第一个操作数（证明的概念与上一章加法的证明类似）。

长减法

如果数字A或B有多于1位数字，我们需要一种算法来完成运算，而无需进行昂贵的倒计数，想象一下您需要计算1000000 – 999999，而您不想进行如此长的倒计数。我们将通过将扩展的简单减法应用于每一对数字Ai – Bi来在十进制下应用倒计数方法：在每次迭代中，如果发生溢出，我们将从下一个A(i+1)数字借一个单位，我们只需要在纸上标记我们从前一个数字借了一个，然后在后续迭代中，我们将需要考虑这一点。

数字计算机上的长减法（与十进制相同，但使用基数2整数寄存器大小）

既然我们可以处理十进制数字，CPU就可以处理2整数寄存器大小个数字。CPU可能有一个借位标志和一个带借位的减法硬件指令来简化借位检测。

请注意，借位标志并非总是在高级语言中可用，但可以通过稍微调整我们之前讨论的性质来模拟借位标志。

算法

此处提出的算法是对实际算法的高层概述，其思想是将A-B的长减法分解为一系列简单的减法An-Bn，从两个数字的最低有效数字开始，我们还需要在每次迭代中传播借位（借位只能是1或0）。

算法如下：

您应该注意到“最终去除前导零”这一部分，这使得减法比加法更复杂，因为我们无法提前知道结果将有多少位数字。可以从sizeof(A)-1 开始循环结果，然后减小索引直到找到第一个非零数字。另一种方法可以是，在上述算法的每次迭代中，一旦我们将一个非零值附加到结果中，就标记该位置。

示例实现

在此，我粘贴了我用C编写的“参考”版本，我对本地机器硬件寄存器做了一些假设，其思想是有一个配置文件来设置实际算法的参数，并有一个基本的便携式实现。

让我解释一下为什么这是一个如此粗糙的实现，没有输入检查和如此老式的接口：其思想是只实现核心算法，更优化的部分可以在更高层实现，我们还需要在除法算法中重用这段代码，因此我们需要它尽可能快。我们也可能在处理数字的一部分，因此它必须能够处理非结构化数据。

代码有40行。

题外话：C语言无法读取或使用借位标志寄存器，因此我们使用分支来检测借位。

/*
Caller must check:
* R should have MAX(ASize, BSize) space, will not check bounds
* ASize must be > BSize  or ASize can be == BSize if A > B
* Most significant digit of A is not zero

Return value is number of significant digits in result

*/
numsize_t LongSub(reg_t* A, numsize_t ASize, reg_t * B, numsize_t BSize, reg_t* R)
{
    register numsize_t i;

    int borrow = (int)(i = 0);
    numsize_t msd = _R(-1); //keep track of last most significant digit

    while (BSize > i)
    {
        register reg_t a = A[i]; 
        register reg_t b = B[i];
        R[i] = a - b - borrow;    
        borrow = (a < b) | (borrow & (b==a)); /* that's an hack, 
                                                 tests will say if it work*/
        ++i;
    }

    while (ASize > i)
    {
        R[i] = A[i] - borrow;
        if (R[i] != 0)
            msd = i;
        borrow = R[i] > A[i] ? 1 : 0;
        ++i;
        if (borrow == 0)
            break;
    }

    if (ASize > i)
        msd = ASize - 1;

    while (ASize > i)
    {
        R[i] = A[i];
        ++i;
    }

    return msd+1;
}

后果

经过一些测试，我可以肯定地说，上述实现工作得很好。我还创建了2个额外的x64汇编版本，以在发布模式下编译时比较“参考”实现。

我不知道C编译器是否会因为无法优化外部调用而惩罚汇编函数调用，所以这些数字必须谨慎看待，无论如何，由于测试是在可重现的伪随机512KB数字对上进行的，两种情况下的调用时间都应该可以忽略不计。

同一算法三种版本的相对计时。

上面您可以看到2011年i7 3ghz的测试结果，使用VS 2017 C++编译。

上面您可以看到使用VS 2022 C++编译的i9-10900的测试结果，正如您可能注意到的，最快的ASM版本比（与之前的硬件+编译器设置相比）快2倍，并且C版本与汇编版本速度相同，尽管它通过分支间接检测借位，而ASM版本使用硬件借位标志，这表明我在vc2022编译器面前技术不足，总的来说，我感觉对于那些说“你需要非常专业才能胜过C编译器”的人来说，有些证实偏差。

历史

  • 2017：开始写作
  • 2019年2月4日：几乎准备发布
  • 2022 年 6 月 11 日：在线发布
© . All rights reserved.