python实现快速幂
时间: 2023-12-03 09:00:26 浏览: 36
快速幂是一种用于快速计算一个数的整数次幂的算法,其时间复杂度为 $O(\log n)$。在 Python 中,可以使用以下代码实现快速幂:
```python
def quick_pow(x, n):
res = 1
while n > 0:
if n % 2 == 1:
res *= x
x *= x
n //= 2
return res
```
其中,x 为底数,n 为指数。在算法中,每次循环将指数 n 除以 2,如果除以 2 后余数为 1,则将结果 res 乘以底数 x,底数 x 自乘,重复上述操作直到指数 n 为 0,最后返回结果 res 即可。
例如,计算 2 的 10 次方,可以调用函数 quick_pow(2, 10),得到结果为 1024。
相关问题
python实现快速模幂算法
快速模幂算法也称为快速幂算法,是一种用于计算大数的指数幂余数的算法。它的主要思想是将指数分解成二进制形式,并利用幂的平方性质以及模运算的余数性质来降低时间复杂度。
下面是 Python 实现快速模幂算法的代码:
```python
def fast_modular_exponentiation(base, exp, mod):
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp = exp // 2
base = (base * base) % mod
return result
```
该函数接受三个参数:底数 `base`、指数 `exp` 和模数 `mod`。它返回的是 `base` 的 `exp` 次幂对 `mod` 取模的结果。
该算法的时间复杂度为 $O(\log_2 n)$,其中 $n$ 是指数 `exp` 的位数。因此,它可以处理非常大的指数和模数,而且效率非常高。
python中快速幂
快速幂是一种用于快速计算幂运算的算法,它可以在O(logn)的时间复杂度内完成幂运算。在Python中,可以使用递归或循环的方式实现快速幂。
以下是使用递归实现快速幂的Python代码:
```python
def quick_pow(x, n):
if n == 0:
return 1
elif n % 2 == 0:
return quick_pow(x * x, n // 2)
else:
return quick_pow(x * x, n // 2) * x
print(quick_pow(2, 10)) # 输出:1024
```
以下是使用循环实现快速幂的Python代码:
```python
def quick_pow(x, n):
res = 1
while n > 0:
if n % 2 == 1:
res *= x
x *= x
n //= 2
return res
print(quick_pow(2, 10)) # 输出:1024
```