快速傅里叶变换计算大整数乘法 code

快速傅里叶变换计算大整数乘法 code

4 years ago

source link: http://abcdxyzk.github.io/blog/2011/02/28/alg-fft-source/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

2011-02-28 19:10:00

// a->A, b->B C->c  用三次快速傅立叶变换。

#include <stdio.h>
#include <string.h>
#include <math.h>

#define N 50009

char s[N];
int La,Lb,a[N+N],b[N+N];

double pi = acos(-1.0);

struct Num {
	double a,b;
}
A[N+N],B[N+N],C[N+N];

Num operator+ (Num aa, Num bb) {
	Num ret;
	ret.a = aa.a+bb.a; ret.b = aa.b+bb.b;
	return ret;
}
Num operator- (Num aa, Num bb) {
	Num ret;
	ret.a = aa.a-bb.a; ret.b = aa.b-bb.b;
	return ret;
}
Num operator* (Num aa, Num bb) {
	Num ret;
	ret.a = aa.a*bb.a - aa.b*bb.b;
	ret.b = aa.a*bb.b + aa.b*bb.a;
	return ret;
}

Num W(int n, int k) {
	Num ret;
	ret.a = cos(-pi*k*2/n);
	ret.b = sin(-pi*k*2/n);
	return ret;
}

void DFT(int L, int R, Num from[], Num X[])
{
	if(L+1 == R)
	{
		X[L] = from[L];
		return;
	}

	int i,j,k;
	Num T;

	for(i=L;i<R;i++) X[i] = from[i];
	j = L; k = (L+R)/2;
	for(i=L;i<R;i+=2)
	{
		from[j++] = X[i]; from[k++] = X[i+1];
	}

	DFT(L, (L+R)/2, from, X);
	DFT((L+R)/2, R, from, X);

	for(i=L;i<(L+R)/2;i++)
	{
		T = X[i];
		X[i] = T + W(R-L, i-L)*X[i+(R-L)/2];
		X[i+(R-L)/2] = T - W(R-L, i-L)*X[i+(R-L)/2];
	}
}

int main()
{
	int i;
	while(scanf("%s",s) != EOF)
	{
		La = strlen(s);
		for(i=0;i<La;i++) a[i] = s[La-i-1]-48;
		scanf("%s",s);
		Lb = strlen(s);
		for(i=0;i<Lb;i++) b[i] = s[Lb-i-1]-48;

		i=1; while(i<La+Lb-1) i = i*2;
		for(;La<i;La++) a[La] = 0;
		for(;Lb<i;Lb++) b[Lb] = 0;

		for(i=0;i<La;i++) {
			A[i].a = a[i]; A[i].b = 0;
			B[i].a = b[i]; B[i].b = 0;
		}

		DFT(0, La, B, C);
		DFT(0, Lb, A, B);

		for(i=0;i<La;i++) B[i] = B[i]*C[i];
		DFT(0, La, B, C);

		C[La] = C[0]; b[0] = 0;
		for(i=1;i<=La;i++)
		b[i] = (int)(C[i].a/La + 0.5);

		for(i=La;i>0;i--)
		{
			b[i-1] += b[i]/10; b[i] %= 10;
		}

		i = 0; while(i < La && b[i] == 0) i++;
		for(;i<=La;i++) printf("%d",b[i]); printf("\n");
	}
	return 0;
}

Recommend

www.tuicool.com 5 years ago
Cache

傅里叶变换

图像处理中, 为了方便处理，便于抽取特征，数据压缩等目的，常常要将图像进行变换。一般有如下变换方法傅立叶变换Fourier Transform 离散余弦变换Discrete Cosine Transform 沃尔希-哈德...

zhuanlan.zhihu.com 4 years ago
Cache

二维傅里叶变换与逆变换基于Unity的实现

abcdxyzk.github.io 4 years ago
Cache

快速傅里叶变换计算大整数乘法

快速傅里叶变换计算大整数乘法 2011-02-28 18:56:00 我们知道，两个 N 位数字的整数的乘法，如果使用常规的算法，时间复杂度是 O(N2)。然而，使用快速傅里叶变换，时间复杂度可以降低到 O(N logN loglogN...

itimetraveler.github.io 4 years ago
Cache

【算法】从多项式乘法到快速傅里叶变换

【算法】从多项式乘法到快速傅里叶变换本文来自：从多项式乘法到快速傅里叶变换 —

kevinnan.org.cn 3 years ago
Cache

数字信号处理——Python实现快速傅里叶变换FFT

1、FFT背景快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，它是根据离散傅里叶的奇、偶、虚、实等特性，在DFT的基础上进行改进获得的。它对傅里叶变换的理论没有新的发现，但它的出现让离散傅里叶变换在计算机系统中得到了广泛的应用...

lasttillend.github.io 3 years ago
Cache

快速傅立叶变换（FFT）在整数乘法中的应用

在上一篇博文中，我们谈到了一种利用分治法优化整数乘法的算法，它的时间复杂度约为O(n1.59)，而本文将介绍另一种基于快速傅立叶变换（Fast Fourier Transform, FFT）的整数乘法，它的时间复杂度更低，为O(nlogn)。这个方法将整数乘法和多项式乘法联系起来，而...

xiaocairush.github.io 2 years ago
Cache

快速傅里叶变换

快速傅里叶变换前置知识：复数。本文将介绍一种算法，它支持在 O(nlog⁡...

www.cnblogs.com 2 years ago
Cache

多项式 I：拉格朗日插值与快速傅里叶变换 - qAlex_Weiq

1. 复数和单位根前置知识：弧度制，三角函数。 1.1 复数的引入跳出实数域 RR，我们定义 i2=−1i2

www.cnblogs.com 2 years ago
Cache

快速傅里叶变换及其实现 - 樱雨楼

第1章引言傅里叶变换（Fourier Transform）是由数学家傅里叶提出的一套对函数进行变换的方法，其主要分为连续傅里叶变换（Continuous Fourier Transform，CFT）和离散傅里叶变换（Discrete Fourier Transform，DFT）两种，在本文中，我们...

www.cnblogs.com 1 year ago
Cache

快速傅里叶变换FFT学习笔记 - DengDuck

点值表示法我们正常表示一个多项式的方式，形如 A(x)=a0+a1x+a2x2+...+anxnA(x)=a0+a1x

快速傅里叶变换计算大整数乘法 code

快速傅里叶变换计算大整数乘法 code

Recommend

About Joyk