内联汇编的性能：一种基于斐波纳契数列计算的分析-2

look_w

优化的矩阵乘方算法这很可能是具有最佳性能的算法：它对斐波纳契数的计算具有对数时间复杂度。该算法取决于以下数学运算。
图 4. 矩阵乘方算法的数学基础第 n 个斐波纳契数将是将矩阵 A 扩展到 (n-1) 乘方后的结果矩阵的元素 (0, 0)。因为关注的所有矩阵都是二维的，所以矩阵运算可在固定的时间内完成。清单 7 中显示了一段示例代码。
清单 7：固定时间内的二维矩阵乘法

1 2 3 4 5 6 7 8 9 10 11 12

void multiply(long long M[2][2], long long N[2][2]) {   long long a =  M[0][0]*N[0][0] + M[0][1]*N[1][0];   long long b =  M[0][0]*N[0][1] + M[0][1]*N[1][1];   long long c =  M[1][0]*N[0][0] + M[1][1]*N[1][0];   long long d =  M[1][0]*N[0][1] + M[1][1]*N[1][1];   M[0][0] = a;   M[0][1] = b;   M[1][0] = c;   M[1][1] = d; }

为了将矩阵 A 扩展到 n 次方，一种直观的 算法将具有线性的运行时间，因为它必须调用乘法运算 (n-1) 次。
An = A A … A
这可以使用以下技术进一步优化：
An = A(n/2) A(n/2)
因此，无需将矩阵 A 扩展到 n 次方，该算法将它扩展到 (n/2) 次方并将 An/2 与自身固定次数的乘法操作。
清单 8：具有对数时间的矩阵乘方算法

1 2 3 4 5 6 7 8 9 10 11

void power(long long M[2][2], int n) {   if( n == 0 || n == 1) return;               //no operation needed for base case   long long A[2][2] = {{1,1},{1,0}};   power(M, n/2);                             //recursively call power on n/2   multiply(M, M);                           //a constant time multiplication   if (n%2 != 0)                             //To handle odd n      multiply(M, A); }

通过在 n/2 上调用乘方函数，输入的大小会每次减半。相应地，复杂度与对数时间有关。清单 9 显示了一种使用优化的矩阵乘方方法的示例实现。
清单 9：计算第 n 个斐波纳契数的优化的矩阵乘方方法

1 2 3 4 5 6 7 8

long long fib_m(int n) {   long long A[2][2] = {{1,1},{1,0}};              //matrix A   if (n == 0)       return 0;                                  //base case F0 = 0   power(A, n-1);                                 //raise A to power (n-1)   return A[0][0];                               //Fn is element (0,0) }

内联汇编实现内联汇编实现将基于迭代算法。从图 3 中显示的可视化形式可以看到，迭代算法计算第 n 斐波纳契数的方法是将它之前的两项 (n-2)和 (n-1)相加。(n-2) 项在此计算后可丢弃，因为后续计算不会再使用它。此观察发现可用来实现内联汇编方法。
算法内联汇编实现将两个最新的斐波纳契数保留在两个单独的寄存器中。在每次迭代时，该算法都会计算最新的项的和，然后将计算的值存储在保存较小的项的寄存器中。这将实际覆盖后一项。因为未来的计算不需要较小的项，所以删除此值是可接受的。因此较大的项是这次迭代的结果。图 4 显示了内联汇编方法的可视化表示。
图 5. 内联汇编方法的可视化表示
图 4 中已经非常直观地显示，该实现在斐波纳契数列中的每一项上迭代一次。每次迭代的结果将存储在图 4 中红色的寄存器中。该实现的伪代码如清单 10 所示。
清单 10：内联汇编实现的伪代码

1 2 3 4 5 6 7 8 9

Fib(n):     load F0 to register 0                              //smaller term in register 0     load F1 to register 1                              //greater term in register 1     for k in range [2,3,…,n]         swap the values in two registers              //register 1 holds smaller term         sum up the values in two register             //sum up 2 terms         store the sum to register 1                   //register 1 holds the sum     end for     return register 1                                 //return the sum

通过三异或运算 ( triple exclusive-or operation) 交换两个值可通过各种方式交换存储在两个寄存器中的值，一种是使用临时寄存器或变量的简单技术。但是，还有一种不需要经历临时存储而交换值的更快方式：使用三次连续的异或 (XOR) 运算的异或交换算法。表 2 中给出了三重 XOR 运算的事实表。
表 2：三异或运算的事实表
初始值R0 = R0 XOR R1R1 = R0 XOR R1R0 = R0 XOR R1 R0  R1  R0  R1  R0  R1  R0  R1 00 0  0  0  0 0001 1  1  1  0 1010 1  0  1  1 0111 0  1  0  1 11该事实表显示，两个寄存器 R0 和 R1 中的值在执行三次连续 XOR 运算后已交换。
汇编指令有许多汇编指令可用来实现该算法。有关可用指令的完整列表，请参阅图书 （IBM 出版物编号 SA22-7832-10）。在 IBM z Systems™ 上的长长的汇编指令列表中，本文选择使用以下指令来实现斐波纳契数列计算。
XGR R0, R1：

• 存储在第一个和第二个寄存器中的值的异或结果放在第一个操作数位置 (R0)。
• 存储在第 2 个操作数 (R1) 中的值保持不变。
• 这些操作数和结果的长度为 64 位。

AGR R0, R1：

• 将第二个操作数与第一个操作数相加，将两数的和放在第一个操作数所在的位置上。
• 存储在第 2 个操作数 (R1) 中的值保持不变。
• 这些操作数和结果被视为 64 位有符号二进制整数。

BRCT R0，分支地址：

• 从第一个操作数中减去值 1，将结果放回到第一个操作数位置。
• 结果为 0 时，继续执行正常的指令数列。
• 结果不为 0 时，当前程序状态字 (PSW) 中的指令地址替换为分支地址。

内联汇编代码计算第 n 个斐波纳契数的实际的内联汇编代码如清单 11 所示。
清单 11：计算第 n 个斐波纳契数的内联汇编方法

1 2 3 4 5 6 7 8 9 10 11 12 13 14

long long fib_asm(int upto) {     if ( upto < 2 ) return upto;                 //F0 = 0, F1 = 1     int mycount = upto - 1;     long long f0 = 0L, f1 = 1L;     asm ( "0:                 \n"                  //back to this when mycount > 0           "XGR   %0, %1       \n"                  //1st XOR           "XGR   %1, %0       \n"                  //2nd XOR           "XGR   %0, %1       \n"                  //3rd XOR           "AGR   %1, %0       \n"                  //Add 2 terms, store to f1           "BRCT  %2, 0b       \n"                  //back to 0 if mycount > 0          :"+r"(f0), "+r"(f1), "+r"(mycount)         );     return f1;                                     //return f1   }

在循环的开头，在值 f0 和 f1 中分别加载 0 和 1。变量 mycount 用于保存所需的斐波纳契数的索引；它也是要执行的迭代次数。在每次迭代的开头，f0 保存更小的项，f1 保存斐波纳契数列的更大的项。在每次迭代期间，该算法通过三次 XOR 运算来交换 f0 和 f1 的值。作为交换的结果，f0 保存更大的项，f1 保存更小的项。AGR 运算对 f0 和 f1 的值求和，然后将该和存储回 f1 中。在任何迭代结束时，f1 保存更大的项，f0 保存更小的项。当 mycount 大于 0 时，BRCT 运算从 mycount 减去 1 并将分支重置回标签 0。mycount 变为 0 时，汇编指令结束。程序会返回存储在 f1 中的值，这是第 n 个斐波纳契数。
因为内联汇编仅迭代斐波纳契数列的每一项一次，所以复杂度为线性时间级。