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

class Poly
    attr_accessor :array, :limit  #系数向量，次数界
    def initialize(a)
        @array = []
        a.each {|e| @array.push Complex(e, 0)}
        [url=home.php?mod=space&uid=215071]@limit[/url] = a.size
    end
    def exchange #位逆序置换
        j = 0
        (0...@limit).each do |i|
            if j > i
                t = @array[i]
                @array[i] = @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[i] = Complex(0.0, 0.0)}
        (o.limit...s).each {|i| o.array[i] = Complex(0.0, 0.0)}  #不足补零
        @limit = o.limit = s  #修正次数界
 
        fft
        o.fft
        (0...s).each do |i|
            @array[i] *= o.array[i]
        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[i] = Integer(x.array[i].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]

class Poly


    attr_accessor :array, :limit  #系数向量，次数界


    def initialize(a)


        @array = []


        a.each {|e| @array.push Complex(e, 0)}


        [url=home.php?mod=space&uid=215071]@limit[/url] = a.size


    end


    def exchange #位逆序置换


        j = 0


        (0...@limit).each do |i|


            if j > i


                t = @array[i]


                @array[i] = @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[i] = Complex(0.0, 0.0)}


        (o.limit...s).each {|i| o.array[i] = Complex(0.0, 0.0)}  #不足补零


        @limit = o.limit = s  #修正次数界


 


        fft


        o.fft


        (0...s).each do |i|


            @array[i] *= o.array[i]


        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[i] = Integer(x.array[i].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]