はてなブックマーク

繰り返し2乗法 繰り返し2乗法とは、指数を2の累乗の積に分解し、計算を効率化するテクニック。 例えば、$3^{50}$が与えられたとき、 $14 = 2^3 + 2^2 + 2^1$と表せるため、$3^{14} = 3^{2^{2^{2^2}}} × 3^{2^{2^2}} × 3^{2^2}$ と変形できる。 愚直に計算した場合、$O(n)$の計算量になるころを、繰り返し2乗法を使って計算することにより、$O(logn)$の計算量になる。 def mat_mul(a, b) : I, J, K = len(a), len(b[0]), len(b) c = [[0] * J for _ in range(I)] for i in range(I) : for j in range(J) : for k in range(K) : c[i][j] += a[i][k] * b[k][j]