3 ms·
For those wondering: that fast 'half the exponent' multiplication algorithm is not optimal in the number of matrix multiplications. For example, x^15 can be don
by Someone 14y ago
For those wondering: that fast 'half the exponent' multiplication algorithm is not optimal in the number of matrix multiplications. For example, x^15 can be done in 5 multiplications, while 'half the exponent requires 6. See http://en.wikipedia.org/wiki/Addition_chain_exponentiation http://en.wikipedia.org/wiki/Addition_chain_exponentiation:
x3 = x * x * x
x6 = x3 * x3
x12 = x6 * x6
x15 = x12 * x3
vs
x2 = x * x
x4 = x2 * x2
x8 = x4 * x4
x12 = x4 * x8
x14 = x12 * x2
x15 = x14 * x