Differences between revisions 14 and 15
 ⇤ ← Revision 14 as of 2007-09-12 07:19:55 → Size: 1087 Editor: RogerHui Comment: ← Revision 15 as of 2008-12-08 10:45:34 → ⇥ Size: 1089 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 45: Line 45: [:../Fibonacci Sequence:Fibonacci sequence]. [[../Fibonacci Sequence|Fibonacci sequence]]. Line 47: Line 47: [[BR]] <
> Line 50: Line 50: * [:../Linear Recurrences:Matrix Powers] * [[../Linear Recurrences|Matrix Powers]] Line 52: Line 52: [[BR]] <
>

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.