我隐约记得一些关于双基系统用于加速某些矩阵乘法的事情。
双基数系统是一种冗余系统,它为一个数字使用两个基数。
n = Sum(i=1 --> l){ c_i * 2^{a_i} * 3 ^ {b_i}, where c in {-1,1}
冗余意味着可以通过多种方式指定一个数字。
您可以查找 Todor Cooklev 的 Vassil Dimitrov 的文章“矩阵多项式计算的混合算法”。
尽量给出最好的简短概述。
他们试图计算矩阵多项式G(N,A) = I + A + ... + A^{N-1}
。
假设 N 是复合G(N,A) = G(J,A) * G(K, A^J)
的,如果我们申请 J = 2,我们得到:
/ (I + A) * G(K, A^2) , if N = 2K
G(N,A) = |
\ I + (A + A^2) * G(K, A^2) , if N = 2K + 1
还,
/ (I + A + A^2) * G(K, A^3) , if N = 3K
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 1
\ I + A * (A + A^2 + A^3) * G(K, A^3) , if N = 3K + 2
由于“显然”(开玩笑地)其中一些方程在第一个系统中很快,而在第二个系统中更好——所以根据N
. 但这需要对 2 和 3 进行快速模运算。这就是双基出现的原因 - 您基本上可以对它们进行快速模运算,从而为您提供一个组合系统:
/ (I + A + A^2) * G(K, A^3) , if N = 0 or 3 mod 6
G(N,A) = | I + (A + A^2 + A^3) * G(K, A^3) , if N = 1 or 4 mod 6
| (I + A) * G(3K + 1, A^2) , if N = 2 mod 6
\ I + (A + A^2) * G(3K + 2, A^2) , if N = 5 mod 6
查看文章以获得更好的解释,因为我不是这方面的专家。