Essays/Repeated Squaring

From J Wiki
Jump to: navigation, 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.