一个循环卷积的问题

无心人 · 发表于 2008-4-23 17:39:39

是否存在不使用$ZZ_m$环和任何剩余算法的循环卷积快速整数算法？

ssikkiss · 发表于 2008-4-29 21:06:54

以上各位高人:
小弟初到贵地.
前段时间我在学ntt,在网上搜到了yaos的一个代码,后来才知道这是来自apfloat中的代码.看到这个代码后,我终于对NTT赫然开朗,同时对fft也更理解了.在这里要感谢yaos!
关于这个问题,其实楼主在csdn中也有提到,这确实是一种很吸引人的东东!

不过我读TAOCP时,里面不是有答案吗?
对这个问题,书上给出来2个算法,只是讲的不明白,很难读懂!
不知道有谁能将这2个答案解释下!

无心人 · 发表于 2008-4-29 21:17:50

我就是不满足于他的答案

想来NTT可不依赖于任何代码库都能自己写
就是大家都熟悉了其流程了

这个，其思想和NTT的卷积是稍微不同的
除非我们弄懂了其思想

否则只能模仿其算法

ssikkiss · 发表于 2008-5-21 19:59:09

今日翻书,发现你的这个问题和Winograd的循环卷及思路很象:
上传图片如下:

ssikkiss · 发表于 2008-5-21 20:13:46

这和TAOCP里的第一个答案的理论是很像,不妨研究下!

liangbch · 发表于 2008-5-21 20:26:13

14# 的图片是来自快速数论变换吗？

ssikkiss · 发表于 2008-5-21 20:29:20

不是,是数字信号处理,讲WFTA那段的

无心人 · 发表于 2008-5-21 20:32:35

看不到图片

无心人 · 发表于 2008-5-21 20:33:44

看到了，能不能有比较详细的叙述？

ssikkiss · 发表于 2008-5-21 20:46:21

再贴个大点的图片,不过由于内容过多,请看数字信处理的书,一般的书都有介绍,
这是WFTA的内容

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 一个循环卷积的问题