Javascript
时间：2014-04-11
来源：互联网
复制内容到剪贴板代码:function complex(_re, _im)
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}
function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Number(_c);
}
function imag(_c)
{
if(isNaN(_c))
return _c.imag;
else
return 0;
}
function norm(_c)
{
if(isNaN(_c))
return _c.real * _c.real + _c.imag * _c.imag;
else
return Number(_c) * Number(_c);
}
function abs(_c)
{
if(isNaN(_c))
return Math.sqrt(norm(_c));
else
return Math.abs(Number(_c));
}
function arg(_c)
{
if(isNaN(_c))
return Math.atan2(_c.imag, _c.real);
else
return 0;
}
function conj(_c)
{
if(isNaN(_c))
return new complex(_c.real, -_c.imag);
else
return Number(_c);
}
function polar(rho, theta)
{
if(isNaN(rho) || Number(rho) == 0)
return 0;
else if(isNaN(theta) || Number(theta) == 0)
return Number(rho);
else if(Number(theta) == Math.PI)
return -Number(rho);
else
return new complex(Number(rho) * Math.cos(Number(theta)), Number(rho) * Math.sin(Number(theta)));
}
function plus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real + b.real, a.imag + b.imag);
else if(isNaN(a))
return new complex(a.real + Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) + b.real, b.imag);
else
return Number(a) + Number(b);
}
function minus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real - b.real, a.imag - b.imag);
else if(isNaN(a))
return new complex(a.real - Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) - b.real, -b.imag);
else
return Number(a) - Number(b);
}
function multiplies(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real * b.real - a.imag * b.imag, a.imag * b.real + b.imag * a.real);
else if(isNaN(a))
return new complex(a.real * Number(b), a.imag * Number(b));
else if(isNaN(b))
return new complex(Number(a) * b.real, Number(a) * b.imag);
else
return Number(a) * Number(b);
}
function divides(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex((a.real * b.real + a.imag * b.imag) / norm(b), (a.imag * b.real - b.imag * a.real) / norm(b));
else if(isNaN(a))
return new complex(a.real / Number(b), a.imag / Number(b));
else if(isNaN(b))
return new complex((Number(a) * b.real) / norm(b), (-b.imag * Number(a)) / norm(b));
else
return Number(a) / Number(b);
}
function Fourier(data)
{
switch(data.length)
{
case 0:
return new Array;
case 1:
return data;
case 2:
var data_1 = multiplies(data[0], Math.SQRT1_2);
var data_2 = multiplies(data[1], Math.SQRT1_2);
return new Array(plus(data_1, data_2), minus(data_1, data_2));
default:
if(data.length % 2 == 0) return CooleyTukey(data);
else return Bluestein(data);
}
}
function CooleyTukey(data)
{
var even = new Array;
var odd = new Array;
for(var idx = 0; idx < data.length; ++idx)
{
if(idx % 2 == 0) even.push(multiplies(data[idx], Math.SQRT1_2));
else odd.push(multiplies(data[idx], Math.SQRT1_2));
}
even = Fourier(even);
odd = Fourier(odd);
var result = new Array;
for(var idx = 0; idx < data.length / 2; ++idx)
{
var temp = multiplies(polar(1, 2 * Math.PI * idx / data.length), odd[idx]);
result[idx] = plus(even[idx], temp);
result[idx + data.length / 2] = minus(even[idx], temp);
}
return result;
}
function Bluestein(data)
{
var signal = new Array;
var kernel = new Array;
var phase = new Array;
for(var idx = 0; idx < data.length; ++idx)
{
kernel[idx] = polar(1, -idx * idx * Math.PI / data.length);
phase[idx] = conj(kernel[idx]);
signal[idx] = multiplies(data[idx], phase[idx]);
}
var result = Convolve(signal, kernel);
var part = result.slice(data.length);
result = result.slice(0, data.length);
if(data.length % 2)
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = minus(result[idx], part[idx]);
} else
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = plus(result[idx], part[idx]);
}
for(var idx = 0; idx < result.length; ++idx)
result[idx] = divides(multiplies(phase[idx], result[idx]), Math.sqrt(data.length));
return result;
}
function Flip(data)
{
var temp = data.shift();
data.reverse();
data.unshift(temp);
return data;
}
function InverseFourier(data)
{
return Flip(Fourier(data));
}
function Convolve(signal, kernel)
{
var result = new Array;
if(signal.length == 0 || kernel.length == 0) return result;
if(signal.length == 1)
{
for(var idx = 0; idx < kernel.length; ++idx) result.push(multiplies(kernel[idx], signal[0]));
return result;
}
if(kernel.length == 1)
{
for(var idx = 0; idx < signal.length; ++idx) result.push(multiplies(signal[idx], kernel[0]));
return result;
}
var complexity = [
_split_convolve_complexity(signal.length, kernel.length),
_split_convolve_complexity(kernel.length, signal.length),
_fft_convolve_complexity(signal.length, kernel.length),
];
if(complexity[0] <= complexity[2] || complexity[1] <= complexity[2])
{
var _signal, _kernel;
if(complexity[0] <= complexity[1])
{
_signal = signal;
_kernel = kernel;
} else
{
_kernel = signal;
_signal = kernel;
}
var split_length = _split_convolve_length(_signal.length);
var num = parseInt(_signal.length / split_length);
for(var i = 0; i < num; ++i)
{
var temp = Convolve(_signal.slice(i * split_length, (i + 1) * split_length), _kernel);
for(var j = i * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
if(_signal.length % split_length)
{
var temp = Convolve(_signal.slice(num * split_length), _kernel);
for(var j = num * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
return result;
}
return _fft_convolve(signal, kernel);
}
function _fft_convolve(signal, kernel)
{
var _length = _fft_convolve_length(signal.length, kernel.length);
var _signal = CooleyTukey(signal.concat(Array.apply(null, new Array(_length - signal.length)).map(Number.prototype.valueOf,0)));
var _kernel = CooleyTukey(kernel.concat(Array.apply(null, new Array(_length - kernel.length)).map(Number.prototype.valueOf,0)));
var result = new Array;
for(var idx = 0; idx < _length; ++idx)
result[idx] = multiplies(_signal[idx], _kernel[idx]);
result = InverseFourier(result).slice(0, signal.length + kernel.length - 1);
for(var idx = 0; idx < result.length; ++idx)
result[idx] = multiplies(result[idx], Math.sqrt(_length));
return result;
}
function _fft_convolve_length(x, y)
{
return 1 << Math.ceil(Math.log(x + y - 1) / Math.LN2);
}
function _fft_convolve_complexity(x, y)
{
var length = _fft_convolve_length(x, y);
return 3 * length * Math.ceil(Math.log(length) / Math.LN2) + 2 * length;
}
function _mixed_convolve_complexity(x, y)
{
if (x == 1 || y == 1) return x * y;
return Math.min(_split_convolve_complexity(x, y), _split_convolve_complexity(y, x), _fft_convolve_complexity(x, y));
}
function _split_convolve_length(x)
{
return parseInt(Math.sqrt(x));
}
function _split_convolve_complexity(x, y)
{
var _x = _split_convolve_length(x);
return parseInt(x / _x) * _mixed_convolve_complexity(_x, y) + (x % _x ? _mixed_convolve_complexity(x % _x, y) : 0);
}
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}
function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Number(_c);
}
function imag(_c)
{
if(isNaN(_c))
return _c.imag;
else
return 0;
}
function norm(_c)
{
if(isNaN(_c))
return _c.real * _c.real + _c.imag * _c.imag;
else
return Number(_c) * Number(_c);
}
function abs(_c)
{
if(isNaN(_c))
return Math.sqrt(norm(_c));
else
return Math.abs(Number(_c));
}
function arg(_c)
{
if(isNaN(_c))
return Math.atan2(_c.imag, _c.real);
else
return 0;
}
function conj(_c)
{
if(isNaN(_c))
return new complex(_c.real, -_c.imag);
else
return Number(_c);
}
function polar(rho, theta)
{
if(isNaN(rho) || Number(rho) == 0)
return 0;
else if(isNaN(theta) || Number(theta) == 0)
return Number(rho);
else if(Number(theta) == Math.PI)
return -Number(rho);
else
return new complex(Number(rho) * Math.cos(Number(theta)), Number(rho) * Math.sin(Number(theta)));
}
function plus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real + b.real, a.imag + b.imag);
else if(isNaN(a))
return new complex(a.real + Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) + b.real, b.imag);
else
return Number(a) + Number(b);
}
function minus(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real - b.real, a.imag - b.imag);
else if(isNaN(a))
return new complex(a.real - Number(b), a.imag);
else if(isNaN(b))
return new complex(Number(a) - b.real, -b.imag);
else
return Number(a) - Number(b);
}
function multiplies(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex(a.real * b.real - a.imag * b.imag, a.imag * b.real + b.imag * a.real);
else if(isNaN(a))
return new complex(a.real * Number(b), a.imag * Number(b));
else if(isNaN(b))
return new complex(Number(a) * b.real, Number(a) * b.imag);
else
return Number(a) * Number(b);
}
function divides(a, b)
{
if(isNaN(a) && isNaN(b))
return new complex((a.real * b.real + a.imag * b.imag) / norm(b), (a.imag * b.real - b.imag * a.real) / norm(b));
else if(isNaN(a))
return new complex(a.real / Number(b), a.imag / Number(b));
else if(isNaN(b))
return new complex((Number(a) * b.real) / norm(b), (-b.imag * Number(a)) / norm(b));
else
return Number(a) / Number(b);
}
function Fourier(data)
{
switch(data.length)
{
case 0:
return new Array;
case 1:
return data;
case 2:
var data_1 = multiplies(data[0], Math.SQRT1_2);
var data_2 = multiplies(data[1], Math.SQRT1_2);
return new Array(plus(data_1, data_2), minus(data_1, data_2));
default:
if(data.length % 2 == 0) return CooleyTukey(data);
else return Bluestein(data);
}
}
function CooleyTukey(data)
{
var even = new Array;
var odd = new Array;
for(var idx = 0; idx < data.length; ++idx)
{
if(idx % 2 == 0) even.push(multiplies(data[idx], Math.SQRT1_2));
else odd.push(multiplies(data[idx], Math.SQRT1_2));
}
even = Fourier(even);
odd = Fourier(odd);
var result = new Array;
for(var idx = 0; idx < data.length / 2; ++idx)
{
var temp = multiplies(polar(1, 2 * Math.PI * idx / data.length), odd[idx]);
result[idx] = plus(even[idx], temp);
result[idx + data.length / 2] = minus(even[idx], temp);
}
return result;
}
function Bluestein(data)
{
var signal = new Array;
var kernel = new Array;
var phase = new Array;
for(var idx = 0; idx < data.length; ++idx)
{
kernel[idx] = polar(1, -idx * idx * Math.PI / data.length);
phase[idx] = conj(kernel[idx]);
signal[idx] = multiplies(data[idx], phase[idx]);
}
var result = Convolve(signal, kernel);
var part = result.slice(data.length);
result = result.slice(0, data.length);
if(data.length % 2)
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = minus(result[idx], part[idx]);
} else
{
for(var idx = 0; idx < part.length; ++idx)
result[idx] = plus(result[idx], part[idx]);
}
for(var idx = 0; idx < result.length; ++idx)
result[idx] = divides(multiplies(phase[idx], result[idx]), Math.sqrt(data.length));
return result;
}
function Flip(data)
{
var temp = data.shift();
data.reverse();
data.unshift(temp);
return data;
}
function InverseFourier(data)
{
return Flip(Fourier(data));
}
function Convolve(signal, kernel)
{
var result = new Array;
if(signal.length == 0 || kernel.length == 0) return result;
if(signal.length == 1)
{
for(var idx = 0; idx < kernel.length; ++idx) result.push(multiplies(kernel[idx], signal[0]));
return result;
}
if(kernel.length == 1)
{
for(var idx = 0; idx < signal.length; ++idx) result.push(multiplies(signal[idx], kernel[0]));
return result;
}
var complexity = [
_split_convolve_complexity(signal.length, kernel.length),
_split_convolve_complexity(kernel.length, signal.length),
_fft_convolve_complexity(signal.length, kernel.length),
];
if(complexity[0] <= complexity[2] || complexity[1] <= complexity[2])
{
var _signal, _kernel;
if(complexity[0] <= complexity[1])
{
_signal = signal;
_kernel = kernel;
} else
{
_kernel = signal;
_signal = kernel;
}
var split_length = _split_convolve_length(_signal.length);
var num = parseInt(_signal.length / split_length);
for(var i = 0; i < num; ++i)
{
var temp = Convolve(_signal.slice(i * split_length, (i + 1) * split_length), _kernel);
for(var j = i * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
if(_signal.length % split_length)
{
var temp = Convolve(_signal.slice(num * split_length), _kernel);
for(var j = num * split_length; j < result.length; ++j)
result[j] = plus(result[j], temp.shift());
result = result.concat(temp);
}
return result;
}
return _fft_convolve(signal, kernel);
}
function _fft_convolve(signal, kernel)
{
var _length = _fft_convolve_length(signal.length, kernel.length);
var _signal = CooleyTukey(signal.concat(Array.apply(null, new Array(_length - signal.length)).map(Number.prototype.valueOf,0)));
var _kernel = CooleyTukey(kernel.concat(Array.apply(null, new Array(_length - kernel.length)).map(Number.prototype.valueOf,0)));
var result = new Array;
for(var idx = 0; idx < _length; ++idx)
result[idx] = multiplies(_signal[idx], _kernel[idx]);
result = InverseFourier(result).slice(0, signal.length + kernel.length - 1);
for(var idx = 0; idx < result.length; ++idx)
result[idx] = multiplies(result[idx], Math.sqrt(_length));
return result;
}
function _fft_convolve_length(x, y)
{
return 1 << Math.ceil(Math.log(x + y - 1) / Math.LN2);
}
function _fft_convolve_complexity(x, y)
{
var length = _fft_convolve_length(x, y);
return 3 * length * Math.ceil(Math.log(length) / Math.LN2) + 2 * length;
}
function _mixed_convolve_complexity(x, y)
{
if (x == 1 || y == 1) return x * y;
return Math.min(_split_convolve_complexity(x, y), _split_convolve_complexity(y, x), _fft_convolve_complexity(x, y));
}
function _split_convolve_length(x)
{
return parseInt(Math.sqrt(x));
}
function _split_convolve_complexity(x, y)
{
var _x = _split_convolve_length(x);
return parseInt(x / _x) * _mixed_convolve_complexity(_x, y) + (x % _x ? _mixed_convolve_complexity(x % _x, y) : 0);
}
作者: Susan﹏汪汪 发布时间: 2014-04-11
大整数乘法
附件 未命名.png (3.4 KB)
2014-3-30 05:57 PM
未命名.png (3.4 KB)
2014-3-30 05:57 PM
作者: Susan﹏汪汪 发布时间: 2014-04-11
OO的方法会pro d....
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.real * this.real + this.imag * this.imag;
}
Complex.prototype.abs=function()
{
return Math.sqrt(this.norm());
}
.......
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.real * this.real + this.imag * this.imag;
}
Complex.prototype.abs=function()
{
return Math.sqrt(this.norm());
}
.......
作者: slight 发布时间: 2014-04-11
作者: fitcat07 发布时间: 2014-04-11
引用:原帖由 slight 於 2014-3-31 10:32 PM 发表
OO的方法会pro d....
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.r ...
可惜javascript不能overload operator OO的方法会pro d....
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.r ...
作者: Susan﹏汪汪 发布时间: 2014-04-11
引用:原帖由 slight 於 2014-3-31 10:32 PM 发表
OO的方法会pro d....
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.r ...
汪汪咁写系有原因OO的方法会pro d....
function Complex(_re, _im)
{
this.real = Number(_re)||0;
this.imag = Number(_im)||0;
}
Complex.prototype.norm=function()
{
return this.r ...
好似以plus为例
因为输入可以系real or complex number
根据输入资料判断需唔需要转成complex
成个fourier算法就可以输入real number
输出的会根据数字而决定系real定complex
咁样个abs就需要自动为不同的数字类型做不同的实作
作者: Susan﹏汪汪 发布时间: 2014-04-11
引用:原帖由 Susan﹏汪汪 於 2014-3-30 04:08 AM 发表
function complex(_re, _im)
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}
function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Num ...
我估以下 project 你会有兴趣看看：function complex(_re, _im)
{
this.real = isNaN(_re) ? 0 : Number(_re);
this.imag = isNaN(_im) ? 0 : Number(_im);
}
function real(_c)
{
if(isNaN(_c))
return _c.real;
else
return Num ...
http://nayuki.eigenstate.org/page/free-small-fft-in-multiple-languages
http://nayuki.eigenstate.org/res/free-small-fft-in-multiple-languages/fft.js
作者: xianrenb 发布时间: 2014-04-11
引用:原帖由 xianrenb 於 2014-4-1 02:02 PM 发表
我估以下 project 你会有兴趣看看：
http://nayuki.eigenstate.org/page/free-small-fft-in-multiple-languages
http://nayuki.eigenstate.org/res/free-small-fft-in-multiple-languages/fft.js
汪汪的算法同佢有好大出入我估以下 project 你会有兴趣看看：
http://nayuki.eigenstate.org/page/free-small-fft-in-multiple-languages
http://nayuki.eigenstate.org/res/free-small-fft-in-multiple-languages/fft.js
作者: Susan﹏汪汪 发布时间: 2014-04-11
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读：74
-
如何安装mysql8.0
阅读：31
-
Word快速设置标题样式步骤详解
阅读：28
-
20+道必知必会的Vue面试题（附答案解析）
阅读：37
-
HTML如何制作表单
阅读：22
-
百词斩可以改天数吗？当然可以，4个步骤轻松修改天数！
阅读：31
-
ET文件格式和XLS格式文件之间如何转化？
阅读：24
-
react和vue的区别及优缺点是什么
阅读：121
-
支付宝人脸识别如何关闭?
阅读：21
-
腾讯微云怎么修改照片或视频备份路径?
阅读：28
