一些小技巧
若有两个数字A和B,要求不使用乘法的情况下完成A*B操作。
方法一:递归+加法(非位运算)
int multiply(int A, int B) {
if(A==0) return 0;
return multiply(A-1,B)+B;
}
这种做法固然可以求出A*B,但是当A的数值特别大时就会爆栈。并且如果不爆栈,也会因为A的数值过大而导致计算速度过慢。
方法二:递归+位运算
这种方法利用了位运算,相比方法一很大程度提高了计算速度。
问题:
现有数字A和数字B,欲计算A*B,并将结果保存到变量ret中
具体步骤:
算法的c语言递归描述如下:
int multiply(int A, int B) {
if(A == 0) return 0;
if(A & 1){
return multiply(A>>1, B<<1) + B;
} else {
return multiply(A>>1, B<<1);
}
}
举个例子
假设现在要计算5*2,数字5和2分别表示为A和B,ret=0
缺点
当数字B特别大时,左移还是会造成数据溢出
现有三个大数A,B和m,求(A*B)\ mod\ m
如果我们直接使用乘法运算符将数字相乘后再取模则肯定会数据溢出,如求 314882150829468584 和 427197303358170108 相乘后对 2009731336725594113 取模的结果
这时可用大数相乘取模算法计算
原理:
算法的c语言描述如下:
typedef long long ll;
ll f(ll a,ll b,ll m){
ll ret = 0; //保存答案
while(b != 0){
if(b & 1) ret = (ret + a) % m;
a = (a << 1) % m;
b >>= 1;
}
return ret;
}
现有数字A和B,求A^B,答案保存在变量ret中
原理:
具体步骤:
举个栗子
A=2,B=5,计算A^B,答案保存在ret
上述过程即为
红色为每一次迭代ret的值,蓝色是每一次迭代A的值
或者再来一个例:
算法的c语言描述如下:
typedef long long ll;
ll fastPower(ll base, ll exp){
ll ret = 1; //保存答案
while(exp != 0){
if(exp & 1) ret *= base;
base *= base;
exp >>= 1;
}
return ret;
}
现有三个大数A和B,m,求(A^B)\ mod\ m
针对大数,若直接使用幂运算符计算再取模则很可能会数据溢出
原理:
算法的c语言描述如下:
typedef long long ll;
ll f(ll base, ll exp, ll m){
ll ret = 1; //保存答案
base = base % m;
while(exp){
if(exp & 1) ret = (ret * base) % m;
exp >>= 1;
base = (base * base) % m;
}
return ret;
}
https://blog.csdn.net/qq_19782019/article/details/85621386
https://blog.csdn.net/qq_36760780/article/details/80092665