Essays/Repeated Squaring
< Essays
Jump to navigation
Jump to search
If verb f multiplies then f~ squares; squaring n times raises to power 2^n and is therefore a fast way to exponentiate.
y=: 3x *~ y 9 *~ *~ *~ *~ y 43046721 *~^:4 y 43046721 y^2^4x 43046721
One way to compute the n-th power for an arbitrary n (when n is not a power of 2), is to find the squares corresponding to 1 bits in the binary representation of n , and then compute the product.
y^25 847288609443 #: 25 1 1 0 0 1 I. |. #: 25 0 3 4 *~^:0 3 4 y 3 6561 43046721 */ *~^:0 3 4 y 847288609443 pow=: 4 : '*/ *~^:(I.|.#:y) x' y pow 25 847288609443
This method works for other kinds of multiplication, such as matrix multiplication or multiplication in ring extensions of Z and Q. Both of these are used in computing elements of the Fibonacci sequence.
See also
Contributed by Roger Hui.