Project1

标题: 快速傅里叶变换在游戏里面的玩法 [打印本页]

作者: 浮云半仙    时间: 2016-11-16 22:47
标题: 快速傅里叶变换在游戏里面的玩法
本帖最后由 浮云半仙 于 2016-11-17 00:20 编辑

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

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

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

RUBY 代码复制下载
  1. class Poly
  2.     attr_accessor :array, :limit  #系数向量,次数界
  3.     def initialize(a)
  4.         @array = []
  5.         a.each {|e| @array.push Complex(e, 0)}
  6.         [url=home.php?mod=space&uid=215071]@limit[/url] = a.size
  7.     end
  8.     def exchange #位逆序置换
  9.         j = 0
  10.         (0...@limit).each do |i|
  11.             if j > i
  12.                 t = @array[i]
  13.                 @array[i] = @array[j]
  14.                 @array[j] = t
  15.             end
  16.             k = @limit
  17.             j &= ~k while j&(k >>= 1) != 0 #倒着做减法
  18.             j |= k
  19.         end
  20.     end
  21.     PI = Math.acos(-1)
  22.     def fft(idft = false)
  23.         pi = PI
  24.         pi = -pi if idft #idft旋转方向反过来
  25.         exchange   #置换
  26.         s = 1  #合并区间的长度
  27.         while s < @limit
  28.             t  = 0
  29.             while t < @limit  #合并区间的开始点
  30.                 x = pi/s
  31.                 omgn = Complex(Math.cos(x), Math.sin(x))
  32.                 omg = Complex(1.0, 0.0)
  33.  
  34.                 (0...s).each do |m|
  35.                     a1 = m+t
  36.                     a2 = m+t+s
  37.                     Complex comm = omg * @array[a2]  #蝴蝶操作
  38.                     @array[a2] = @array[a1] - comm
  39.                     @array[a1] = @array[a1] + comm
  40.                     omg = omg*omgn
  41.                 end
  42.  
  43.                 t += s<<1
  44.             end
  45.             s <<= 1
  46.         end
  47.         @array.map!{|e| e/@limit} if idft   #逆变换
  48.     end
  49.     def mul(o)
  50.         s = 1
  51.         s <<= 1 while s < @limit + o.limit
  52.         (@limit...s).each {|i| @array[i] = Complex(0.0, 0.0)}
  53.         (o.limit...s).each {|i| o.array[i] = Complex(0.0, 0.0)}  #不足补零
  54.         @limit = o.limit = s  #修正次数界
  55.  
  56.         fft
  57.         o.fft
  58.         (0...s).each do |i|
  59.             @array[i] *= o.array[i]
  60.         end
  61.         fft(true)
  62.     end
  63.     #-----------------------
  64.     def mul_with(poly)
  65.         x = Poly.new(@array)
  66.         y = Poly.new(poly.array)
  67.         x.mul(y)
  68.         (0...x.limit).each do |i|
  69.             @array[i] = Integer(x.array[i].real+0.5)  #四舍五入...
  70.         end
  71.     end
  72. end
  73.  
  74. #test
  75. #多项式乘法(1+2x)(1+2x+x^2) = (1+4x+5x^2+2x^3)
  76. #结果的多项式次数界为3,四项
  77. x = Poly.new([1, 2])
  78. y = Poly.new([1, 2, 1])
  79. x.mul_with y
  80. #输出结果的系数
  81. #puts x.array #=> 1 4 5 2 0 0 0 0 (末尾4个0是多余的)
  82. puts x.array[0..3]

fft.zip

1.08 KB, 下载次数: 64

内含这个脚本文件


作者: 浮云半仙    时间: 2016-11-17 08:37
还有一些应用比如图像和声音的处理...(胡扯完毕闪人
作者: fux2    时间: 2016-11-17 09:48
半仙的蜜汁功能,一般还是用不上




欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1