快速傅里叶变换在游戏里面的玩法

浮云半仙

再来卖个萌(
好吧我承认我标题党了，其实应该说是"多项式乘法"的玩法。
游戏里面可以用的玩法想想有个 生成函数 资料可以在我的博客上找一下: http://sxysxy.org/blogs/15

加速计算卷积，做一些奇怪的事情....

这个代码框总是出一些奇怪的问题，这里以附件形式提供下载好了:
fft.zip (1.08 KB, 下载次数: 82)

2016-11-17 00:20 上传

点击文件名下载附件

[pre lang="ruby" file="fft.rb"]class Poly
    attr_accessor :array, :limit  #系数向量，次数界
    def initialize(a)
        @array = []
        a.each {|e| @array.push Complex(e, 0)}
        @limit = a.size
    end
    def exchange #位逆序置换
        j = 0
        (0...@limit).each do |i|
            if j > i
                t = @array
                @array = @array[j]
                @array[j] = t
            end
            k = @limit
            j &= ~k while j&(k >>= 1) != 0 #倒着做减法
            j |= k
        end
    end
    PI = Math.acos(-1)
    def fft(idft = false)
        pi = PI
        pi = -pi if idft #idft旋转方向反过来
        exchange   #置换
        s = 1  #合并区间的长度
        while s < @limit
            t  = 0
            while t < @limit  #合并区间的开始点
                x = pi/s
                omgn = Complex(Math.cos(x), Math.sin(x))
                omg = Complex(1.0, 0.0)
               
                (0...s).each do |m|
                    a1 = m+t
                    a2 = m+t+s
                    Complex comm = omg * @array[a2]  #蝴蝶操作
                    @array[a2] = @array[a1] - comm
                    @array[a1] = @array[a1] + comm
                    omg = omg*omgn
                end
               
                t += s<<1
            end
            s <<= 1
        end
        @array.map!{|e| e/@limit} if idft   #逆变换
    end
    def mul(o)
        s = 1
        s <<= 1 while s < @limit + o.limit
        (@limit...s).each {|i| @array = Complex(0.0, 0.0)}
        (o.limit...s).each {|i| o.array = Complex(0.0, 0.0)}  #不足补零
        @limit = o.limit = s  #修正次数界
        
        fft
        o.fft
        (0...s).each do |i|
            @array *= o.array
        end
        fft(true)
    end
    #-----------------------
    def mul_with(poly)
        x = Poly.new(@array)
        y = Poly.new(poly.array)
        x.mul(y)
        (0...x.limit).each do |i|
            @array = Integer(x.array.real+0.5)  #四舍五入...
        end
    end
end

#test
#多项式乘法(1+2x)(1+2x+x^2) = (1+4x+5x^2+2x^3)
#结果的多项式次数界为3，四项
x = Poly.new([1, 2])
y = Poly.new([1, 2, 1])
x.mul_with y
#输出结果的系数
#puts x.array #=> 1 4 5 2 0 0 0 0 (末尾4个0是多余的)
puts x.array[0..3]
[/pre]

浮云半仙

还有一些应用比如图像和声音的处理...(胡扯完毕闪人

fux2

半仙的蜜汁功能，一般还是用不上