34. Repeated Squaring

If function f multiplies then f⍨ squares; squaring n times raises to power 2*n and is therefore a fast way to exponentiate.

   y← 3
   ×⍨ y
9
   ×⍨ ×⍨ ×⍨ ×⍨ y
43046721
   ×⍨⍣4 ⊢y
43046721

   y*2*4
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.

   ⎕pp←18  ⍝ to display all digits

   y*25
847288609443

   2⊥⍣¯1 ⊢25
1 1 0 0 1

   powop←{⍺←⊣ ⋄ ⍺∘⍺⍺{⍺⍺⍣⍵⊢⍵⍵}⍵¨⍵⍵}

   ⍸ ⌽ 2⊥⍣¯1 ⊢25
0 3 4
   ×⍨powop 0 3 4 ⊢y
3 6561 43046721
   ×/ ×⍨powop 0 3 4 ⊢y
847288609443

   pow←{⊃⍺⍺/⍺⍺⍨powop(⍸⌽2⊥⍣¯1⊢⍵)⊢⍺}

   y ×pow 25
847288609443

powop is a power operator like the primitive ⍣ but extended to allow an array “exponent” (right operand). Moreover, monadic ⊤ can be specified to compute the binary representation [100]. With these extensions, pow can be defined more tersely as pow←{⊃⍺⍺/⍺⍺⍨⍣(⍸⌽⊤⍵)⊢⍺} .

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.

   ⊢ m←3 3⍴⍳5
0 1 2
3 4 0
1 2 3

   m+.×m+.×m+.×m+.×m+.×m+.×m+.×m+.×m+.×m+.×m 
30302130 48622309 23428348
57287403 91922080 44289762
56003936 89862991 43299771

   m +.×⍣11 ∘.=⍨⍳≢m
30302130 48622309 23428348
57287403 91922080 44289762
56003936 89862991 43299771

   m +.×pow 11
30302130 48622309 23428348
57287403 91922080 44289762
56003936 89862991 43299771

Appeared in J in [102].