关于快速乘法的一个问题

有人告诉我一种用二进制位运算优化乘法的方式，复杂度为

O(\log_2 n)

，我用该原理写了两份代码，一份是二进制，一份是以同样的原理类推的

O(\log_4 n)

四进制代码。但是都不如

O(n^2)

的普通乘法。设想应该是常数问题，但是找不出来到底是哪里有问题。我用手写代替循环，就快了许多，比普通乘法快。请各位dalao帮我改进这些代码，或者能给出一份更快的代码也行，万分感谢！！！

原理：把因数拆成

2^k

进制，再根据乘法分配律对于每一位进行乘法运算，再相加。

以下为代码：

CPP

inline long long multiply1(long long a, long long b) {
    long long res = 0;
    for (register int i = 0; b >> i; i++)
        if ((b >> i) & 1)
            res += a << i;
    return res;
}//2进制

inline long long multiply2(long long a, long long b) {
    long long res = 0;
    for (register int i = 0;b;++i){
        long long tmp=b-(b>>2<<2);
        res+=(tmp?(tmp==2?a<<(1+(i<<1)):a*(tmp<<(i<<1))):0);
        b>>=2;
    }
    return res;
}//4进制

以下为用于测试耗时的代码：

CPP

#include <bits/stdc++.h>
using namespace std;
double a1,a2,a3; 
inline long long multiply1(long long a, long long b) {
    long long res = 0;
    for (register int i = 0; b >> i; i++)
        if ((b >> i) & 1)
            res += a << i;
    return res;
}//2½øÖÆ 

inline long long multiply2(long long a, long long b) {
    long long res = 0;
    for (register int i = 0;b;++i){
    	long long tmp=b-(b>>2<<2);
    	res+=(tmp?(tmp==2?a<<(1+(i<<1)):a*(tmp<<(i<<1))):0);
    	b>>=2;
	}
    return res;
}//4½øÖÆ 
int main(){
	ios::sync_with_stdio(0);
	int t1,t2,C=100;
	long long r=0;
	while(C--){
		t1=clock();
		for(register int i=0;i<100000;++i)
			r=multiply1(99,999999999999999);
		t2=clock();
		a1+=t2-t1;
		t1=clock();
		for(register int i=0;i<100000;++i)
			r=multiply2(99,999999999999999);
		t2=clock();
		a2+=t2-t1;
		t1=clock();
		for(register int i=0;i<100000;++i)
			r=99*999999999999999;
		t2=clock();
		a3+=t2-t1;
		t1=clock();
	}cout<<a1/100<<endl<<a2/100<<endl<<a3/100<<endl;
	return 0;
}

关于快速乘法的一个问题

讨论操作

回复

相关推荐

关于快速乘法的一个问题