202606120940快速幂

快速幂

问题：求一个非负数的n次方。数学表达，

$$f_b(n)=b^n,b>0,n\ge 0$$

其中，$b$ 叫底数，$n$ 叫次数，$b^n$ 成为 $b$ 的 $n$ 次幂。当 $b=0$ 时，有 $f_b(n)=0,n\in N^{+}$. 特别的，约定 $b^0=1$，$0^0=1$.

现在要设计一个算法，求解 $b^n$.

; recursive
(define (expo b n)
	(if (= n 0)
        1
        (* b (expo b (- n 1)))))
 
; iterative
(define (expon b n)
	(define (exp-iter prod cnt)
		(if (= cnt n)
            prod
            (exp-iter (* b prod) (+ cnt 1))))
    (exp-iter 1 0))
 
;; test
(expo 3 4)
(expon 3 4)
 
;; a fast version
(define (fast-exp b n)
	(cond ((= n 0) 1)
          ((even? n)
           (square (fast-exp b (/ n 2))))
          (else (* b (fast-exp b (- n 1))))))
 
;; test
(fast-exp 3 4)

// 快速幂，可能会溢出
unsigned long long exp(unsigned b, unsigned n) {
	unsigned long long ans = 1;
	while (n > 0) {
		if (n & 1) { // 指数为奇数，先乘一次底数
			ans *= b;
		}
		b *= b;  // 底数自乘，指数折半
		n >>= 1; // 指数除2
	}
	return ans;
}

有些知识点，很小，也不难。但要用的时候，总是记不全，所以有被记录的价值。