| 17544 | } |
| 17545 | |
| 17546 | __int64 pow_ll(__int64 base, __int64 exp) |
| 17547 | { |
| 17548 | /* |
| 17549 | Caller must ensure exp >= 0 |
| 17550 | Below uses 'a^b' to denote 'raising a to the power of b'. |
| 17551 | Computes and returns base^exp. If the mathematical result doesn't fit in __int64, the result is undefined. |
| 17552 | By convention, x^0 returns 1, even when x == 0, caller should ensure base is non-zero when exp is zero to handle 0^0. |
| 17553 | */ |
| 17554 | if (exp == 0) |
| 17555 | return 1ll; |
| 17556 | |
| 17557 | // based on: https://en.wikipedia.org/wiki/Exponentiation_by_squaring (2018-11-03) |
| 17558 | __int64 result = 1; |
| 17559 | while (exp > 1) |
| 17560 | { |
| 17561 | if (exp % 2) // exp is odd |
| 17562 | result *= base; |
| 17563 | base *= base; |
| 17564 | exp /= 2; |
| 17565 | } |
| 17566 | return result * base; |
| 17567 | } |