1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
|
# Fast Power Operator (`**`)
The `**` operator computes integer exponentiation using **binary exponentiation** (also known as square-and-multiply). It raises the base (first operand) to the integer power of the exponent (second operand) on the RPN stack.
## Binary Exponentiation
Binary exponentiation reduces the number of multiplications from O(n) to O(log n) by exploiting the binary representation of the exponent.
The algorithm works as follows:
1. Initialize `result = 1`
2. While the exponent is positive:
- If the exponent is **odd**, multiply `result` by the current `base`
- Square the `base`
- Divide the exponent by 2 (integer division)
3. For negative exponents, compute `1 / (base^|exp|)`
### Example: 3^13
| Step | exp | exp odd? | result | base |
|------|-----|----------|--------|------|
| 0 | 13 | yes | 1 * 3 = 3 | 3 |
| 1 | 6 | no | 3 | 9 |
| 2 | 3 | yes | 3 * 9 = 27 | 81 |
| 3 | 1 | yes | 27 * 81 = 2187 | 6561 |
| 4 | 0 | — | **2187** | — |
Only 4 multiplications instead of 12. For 10^100, that's ~17 multiplications instead of 99.
## Syntax
RPN (Reverse Polish Notation):
```
base exponent **
```
Operands are popped in reverse order: `exponent` (top) then `base`, result is `base^exponent`. Pushed back as a unitless (Cool) number.
## Examples
### Integer exponent
```
2 10 ** → 1024
```
### Negative exponent
```
2 -3 ** → 0.125 (i.e., 1/8)
```
### Zero exponent
```
5 0 ** → 1
```
Any number to the power of 0 is 1 (short-circuited, no multiplication performed).
### Large exponent
```
10 100 ** → 1e+100
```
### Fractional exponent (rejected)
```
2 1.5 ** → Error: exponent must be an integer, got 1.5
```
The `**` operator **requires** an integer exponent. Use `^` for fractional exponents.
## `**` vs `^`
| Feature | `**` (Fast Power) | `^` (Power) |
|---------|-------------------|-------------|
| Exponent type | Integer only | Any float |
| Algorithm | Binary exponentiation (square-and-multiply) | `math.Pow()` |
| Complexity | O(log n) multiplications | Hardware/logarithm-based |
| Fractional exponents | Rejected with error | Supported |
| Negative exponents | Supported (as `1/base^|n|`) | Supported |
| Zero exponent | Short-circuited → 1 | `math.Pow(base, 0)` → 1 |
### When to use `**`
- Exponent is a known integer
- You want a fast, exact integer-power computation
- You want to guard against accidental fractional exponents
### When to use `^`
- Exponent may be fractional (e.g., `9 0.5 ^` → 3 for square root)
- Working with arbitrary floating-point exponents
- General-purpose power computation
## Edge Cases
| Input | Result | Notes |
|-------|--------|-------|
| `x 0 **` | 1 | Short-circuited; no multiplications |
| `x -n **` | 1/(x^n) | Computed recursively via positive exponent |
| `0 0 **` | 1 | By convention (0^0 = 1) |
| `2 1.5 **` | Error | Fractional exponents not supported |
| `x n **` (n large) | float64 result | Result limited by float64 range; may overflow to Inf |
| `-2 3 **` | -8 | Negative base with integer exponent works correctly |
## Performance Notes
- **Time complexity**: O(log |n|) where n is the exponent. An exponent of 100 requires only ~7 loop iterations (vs 99 naive multiplications).
- **Space complexity**: O(1) for positive exponents; O(log |n|) stack depth for negative exponents (recursive call).
- The implementation uses `float64` throughout, so results may lose precision for very large exponents (same limitations as any floating-point computation).
- For exponent 0, the function returns 1 immediately without entering the loop.
|
