:)
麻烦你把那个PDF发上来
或者你在网上搜索Winograd WFTA也能找到相应的信息
在WFTA中,Winograd 为了计算FFT,把大N点FFT转化成小n的循环卷积问题,
而我们要做乘法,就是一个循环卷积问题
过去我们是用FFT来做的,也就是把循环卷积问题转化为FFT的计算
现在,如果我们对Winograd的那个"小n点快速卷及算法"弄懂了,就不必绕圈子了!
:)
那个和FNT关系不大
那个算法是把高度复合数N点变换
分解成小n变换，高效的2-12点的变换
发了3次!发不了!太大了,9MB,
那个和FNT关系不大
那个算法是把高度复合数N点变换
分解成小n变换，高效的2-12点的变换
你说的这个是针对整个WFTA,而我说的是WFTA中Winograd提出的那个 小n点循环卷及算法
不知怎么发不上来文件,我把它用WINRAR分成了24分,还是发不上来
要么,留个email?
yaojialin@126.com
这是用Z变换来计算卷及,不是与TAOCP上的一样么?
发了,你看看收到没有
谢谢
本帖最后由 ssikkiss 于 2010-7-2 22:05 编辑
此题网上以有人做出。
我抄写了它的c++代码，编译出错，稍更改了下，可以通过，不过请自己加入main函数
const int NMax = 1<<22;
const int SomeMore = 600;
const int PolyTempMax = 1<<11;
#define NUMBERTYPE long
NUMBERTYPE * Global = new NUMBERTYPE;
long CountAdd;
long CountMul;
// Standard circular convolution
void CircConv(long N, NUMBERTYPE *X, NUMBERTYPE *H, NUMBERTYPE *Y) {
long i, j;
for (i = 0; i < N ;i++)
Y = 0;
for (i = 0; i < N ;i++)
for (j = 0; j < N ;j++)
if (i + j < N)
Y += X * H;
else
Y += X * H;
}
void WriteResult(long N, NUMBERTYPE *X) {
long i;
long t=0;
for (i = 0; i < N; i++) {
t+=X;
cout<<t%10;
t/=10;
}
printf("\n");
}
void ModuloPlusMinus(long N, long X) {
long i;
NUMBERTYPE Temp;
for (i = 0; i < N; i++) {
Temp = Global;
Global = Temp - Global;
Global = Temp + Global;
}
CountAdd += N<<1;
}
void MulAddDiv(long N, long X1, long X2) {
long i;
NUMBERTYPE Temp;
for (i = 0; i < N; i++) {
Temp = Global;
Global = (Temp + Global)>>1;
Global = (-Temp + Global)>>1;
}
CountAdd += N<<1;
}
void PermutePolySub(long N, long K, long X, NUMBERTYPE * Y, long Z) {
long i;
long adr;
long ex;
for (i = 0; i < N; i++) {
adr = (i + K +2 * N * N) % N;
ex = ((i + K +2 * N * N) / N) & 1;
if (ex == 0) {
Global = Global - Y;
} else {
Global = -Global + Y;
}
}
CountAdd +=N;
}
void PolyAdd(long N, long X, NUMBERTYPE * Y, long Z) {
long i;
for (i = 0; i < N; i++) {
Global = Global + Y;
}
CountAdd +=N;
}
void PolySubPermute(long N, long K, long X, NUMBERTYPE * Y, long Z) {
long i;
long adr;
long ex;
for (i = 0; i < N; i++) {
adr = (i + K + 2 * N * N) % N;
ex = ((i + K + 2 * N * N) / N) & 1;
if (ex == 0) {
Global = Global - Y;
} else {
Global = Global + Y;
}
}
CountAdd +=N;
}
void PolyAddPermute(long N, long K, long X, NUMBERTYPE * Y, long Z) {
long i;
long adr;
long ex;
for (i = 0; i < N; i++) {
adr = (i + K + 2 * N * N) % N;
ex = ((i + K + 2 * N * N) / N) & 1;
if (ex == 0) {
Global = Global + Y;
} else {
Global = Global - Y;
}
}
CountAdd +=N;
}
void PolyTransNB(long N, long L2, long K, long X) {
long i;
long M;
long m1;
long P;
long p1;
long Q;
long q1;
long adr;
NUMBERTYPE *Temp = new NUMBERTYPE;;
M = (long)floor(0.5 + log(N) / log(2));
P = 1;
Q = N / 2;
for (m1 = 0; m1 < M; m1++) {
for (p1 = 0; p1 < P; p1++)
for (q1 = 0; q1 < Q; q1++) {
adr = q1 +p1 * (Q<<1);
for (i = 0; i < L2; i++)
Temp = Global;
PermutePolySub(L2, P * q1 * K, X + L2 * adr, Temp, X + L2 * (adr + Q));
PolyAdd(L2, X + L2 * adr, Temp, X + L2 * adr);
}
P <<=1;
Q >>=1;
}
delete []Temp;
}
void PolyTransBN(long N, long L2, long K, long X) {
long i;
long M;
long m1;
long P;
long p1;
long Q;
long q1;
long adr;
NUMBERTYPE *Temp = new NUMBERTYPE;;
M = (long)floor(0.5 + log(N) /log(2));
P = N / 2;
Q = 1;
for (m1 = 0; m1 < M; m1++) {
for (p1 = 0; p1 < P; p1++)
for (q1 = 0; q1 < Q; q1++) {
adr = q1 + 2 * p1 * Q;
for (i = 0; i < L2; i++)
Temp = Global;
PolySubPermute(L2, P * q1 * K,X+L2*adr,Temp,X+L2*(adr+Q));
PolyAddPermute(L2, P * q1 * K,X + L2 * adr, Temp, X + L2 * adr);
}
P >>=1;
Q <<=1;
}
delete []Temp;
}
void NegaConvolution(long N, long X, long H, long Y) {
long i, k;
long N2, N3, N4;
long L1, L2;
NUMBERTYPE Tp0, Tp1, Tp2;
if (N==2) {
Tp0= (Global + Global) * Global;
Tp1=(Global + Global) * Global;
Tp2=(Global - Global) * Global;
CountMul +=3;
Global = Tp0 - Tp1;
Global = Tp0 - Tp2;
CountAdd+=5;
} else {
N2=N<<1;
N3=N2+N;
N4=N2<<1;
L2 = (long)floor(0.5 + sqrt(N));
if (L2 * L2 != N)
L2 = (long)floor(0.5 + sqrt(N2));
L1 = N / L2;
for (k=0;k<L1;k++)
for (i=0;i<L2;i++) {
Global=Global;
Global=Global;
Global=0;
Global=0;
}
PolyTransNB(2 * L1, L2, L2 / L1, Y);
PolyTransNB(2 * L1, L2, L2 / L1, Y + N2);
for (k = 0; k < 2 * L1; k++)
NegaConvolution(L2, Y + L2 * k, Y + N2 + L2 * k, Y + N4);
PolyTransBN(2 * L1, L2, -(L2 / L1), Y);
for (k = 0; k < L1; k++) {
for (i = 1; i < L2; i++) {
Global = (Global +
Global) / (2 * L1);
}
Global = (Global - Global) / (2 * L1);
CountAdd+=L2+1;
}
}
}
void CircConvolution(long N, long X, long H) {
long M;
long N2;
long X1, X2;
NUMBERTYPE Tp0, Tp1, Tp2;
N2 = 2 * N;
M = N / 2;
do {
ModuloPlusMinus(M, X);
ModuloPlusMinus(M, H);
NegaConvolution(M, X, H, N2);
X += M;
H += M;
M /= 2;
} while (M != 1);
Tp0=(Global+Global)*Global;
Tp2=(Global-Global);
Tp1=Tp2*Global;
Tp2=Tp2*Global;
CountAdd +=5;
CountMul +=3;
Global = Tp0 - Tp1;
Global = Tp0 - Tp2;
M = 2;
X1 = X - M;
X2 = X;
do {
MulAddDiv(M, X1, X2);
X2 -= M;
M <<=1;
X1 -= M;
} while (M != N);
}
char* testmul(int e) {
NUMBERTYPE* sequenceOne=new NUMBERTYPE;
NUMBERTYPE* sequenceTwo=new NUMBERTYPE;
NUMBERTYPE* resultFast=new NUMBERTYPE;
NUMBERTYPE* resultSlow=new NUMBERTYPE;
long N;
long X,H;
long i;
N=2;
N<<=e;
for (i=0;i<N/2;i++) {
sequenceOne=9;
sequenceTwo=9;
}
for (i=N/2;i<N;i++) {
sequenceOne=0;
sequenceTwo=0;
}
cout<<N<<endl;
X=0;
H=N;
Timer timer;
timer.start();
for (i = 0; i < N; i++) {
Global = sequenceOne;
Global = sequenceTwo;
}
CountAdd = 0;
CountMul = 0;
CircConvolution(N, X, H);
timer.end();
cout<<"test mul:耗时"<<timer.getSecond()<<"秒"<<endl;
//WriteResult(N, Global); // First part of Global contains the convolution
printf("\n");
//CircConv(N, sequenceOne, sequenceTwo, resultSlow);
//WriteResult(N, resultSlow);
cout<<"Additions:"<<CountAdd<<endl;
cout<<"Multiplications:"<<CountMul<<endl;
char* ret=(char*)malloc(sizeof(char)*(N+2));
long t=0;
for (i = 0; i < N; i++) {
t+=Global;
ret=t%10+'0';
t/=10;
}
ret=0;
return ret;
}