数论变换原理简述

plp626

我们不是为了使用数论变换而使用数论变换，我所关心的是 怎样利用数论变换实现大数乘法（高效的大数乘法），纯理论性的东西没有多大意义。毕竟apfloat实现了一个使用数论变换的大数乘法，我们参考他的东西有何不对？ ... liangbch 发表于 2008-4-18 11:15

你这么说话有点浮躁，好的算法都是从理论里提炼优化出来的，如果你不了解原理，没有理论支持就总是在重复别人的路，和copy没有本质的区别，这意义也大不到哪去

gxqcn

liangbch 在 14# 里已有特别解释。

liangbch

我还是在解释一下我的观点， 我在13楼的话也许说的片面了些，许多人可能误解了我所说的。见此机会，我发几句牢骚。 1.做产品也好，作科研也罢。我想应该分为2类人。 第1类人是做基础理论研究的，这需要相当高的科学素养，大部分人应该冠之以科学家称号，这类人应该是非常少的。大部分人不必也没有能力做这样的基础研究。就大数算法基本理论而言。其大部分算法在上世纪60-70年代已经完成，如FFT 乘法，Karatsuba 乘法，Toom-Cook 乘法等。基础理论的研究热潮已经过去。目前很少有突破性的新理论出现。 就计算机算法而言，绝大多数工程师不需要研究算法的，注意是研究算法，而不是学习算法。在csdn网友中，真正研究算法的者寥寥，我知道的恐怕只有海星了。海星在2003年已辞去 数据结构和算法版主，见http://topic.csdn.net/t/20030329/22/1594297.html。 第2类人是实现算法或者做一个产品的。这些人占绝大多数，他们多是工程师，甚至许多科研人员亦属此类。例，我公司是做Video 压缩/解压缩的，是目前世界上主要的video产品供应商。但即使这样的公司，需要真正研究MPEG2，H.264算法的也很少，大部分只要了解这个算法就可以了。 我国目前的国情是，许多人重研究(实际上他们并没有研究出什么东西，产出的只是大量的垃圾论文）轻实践。发表论文后就算完成任务了，没有后续的开发，理论转化为产品者寥寥。就计算机科学而言，你所知道的操作系统，数据库，编译器，有几个是中国人开发的。我的感兴趣的课题是大整数阶乘计算。但是在我遍查我国的学术论文后诧异地发现，这些论文中最先进的算法，仅仅相当我的《大数阶乘之计算从入门到精通》系列文章的入门篇。之所以这样，我以为这和大环境的浮躁的学风有关，他们为了发表论文而发表论文，没有深入的去做后续的工作。相反，许多被视为非研究人员的软件开发者开发出了很好的作品，这比发垃圾论文意义更大。这些关于大数阶乘的论文见 1. 大整数阶乘的高精度快速计算，李村合 《微型计算机 1996年第16卷，第6期》 2. 基于C++的求大整数N的阶乘的实现 薛燕红 《邢台职业技术学院学报 2006年 第23卷 第5期》 3. 利用字符串求任意数的阶乘 高军 戴华 《黑龙江农垦师专学报 20O3年第2期》 4.一种求任意正整数n阶乘的算法及实现 何大德 《湖南教育学院学报 第l9卷第4期》

你这么说话有点浮躁，好的算法都是从理论里提炼优化出来的，如果你不了解原理，没有理论支持就总是在重复别人的路，和copy没有本质的区别，这意义也大不到哪去

我应该不属于浮躁的人。我没有说不要去了解原理，去学习算法，事实上也很喜欢算法，我在CSDN的专家分中，绝大多数是来自 数据结构和算法 版块。我所强调的是，不要为了研究某个原理而一味的研究原理，我们不能陷入数学的海洋。目前前人积累的数学知识恐怕不是任何一个人能在有生之年学完的。我们需要在有限的时间里，学习最关键最有用的技术和原理，来实现我们所需的产品或者作品，我们最好不要总停留在研究阶段，应该尽快地出产品。

liangbch

21# plp626 你在论坛了呆久了，你就会知道，真正浮躁的往往是哪些初学者。

gxqcn

如果一个人每天抽出半小时专注于某个领域，要不了多久就可以成为这方面的专家。 梁兄在中学时就开始研究高精度算法，而后又做了系列的大整数阶乘算法，这没有一定的定力是无法完成的，所以可以肯定他绝对不是浮躁之人。 大数算法要想做好，很不容易。不仅涉及到复杂的数学原理，还要设计到巧妙的算法结构，甚至硬件的实际运作（比如针对CPU作对应的汇编优化等）。 在世界范围内能专注于此的不多，在国内则更少，当然我指的是已经达到一定水准的。 虽然网上充斥着不少论文，但真正有价值的很少，这点我与梁兄深有同感。 前不久大连理工大学的一位网友曾搜集了一些模幂算法论文寄给我，大多是国人发表的英文论文，说实话可供吸收的营养实在有限。

gxqcn

大数算法的开发调试都非常耗神，每次我升级一版都有种从亢奋到虚脱的经历，所以有时我都有点怕继续下去， 不过有些奇妙的想法若不实现实在是心有不甘，有种未充分发挥上天赐予的天赋的负罪感。 去年金融危机，今年公司有一个系列的新产品开发（我在其中起到了核心关键作用，所开发的算法远超同行水准，尽管不乏一些著名的日系大公司，现在产品在欧美销量很好）。 现在略可喘口气了，但最近家里房子需要装修，还是暂时无法凝神于HugeCalc升级开发上。

ssikkiss

楼主要继续更新啊，最近读“孙琦，郑德勋，沈仲琦”的快速数论变换，发现这本书比蒋峥嵘的书好的多，发现里面将了几个复数域数论变换，二次域数论变换，分圆域数论变换，其中对复数域数论变换基本读懂了，发现蒋的书也写了复数域变换，但是蒋的书和这本书大不一样；在蒋的书里，说的很笼统，连复数域上加法和乘法的定义都没说，而且其变换的性质和普通NTT一样；但孙他们的书里，麦森数也有了用武之地，可以像FFT那样快速运算；而且他们后来讲到的二次域，更是厉害，可以大幅度提高变换长度和降低模的大小，对模的选择也更宽松，只是我看到那个N次跟有点头大。

无心人

楼上，偶就是有那个书的纸本，呵呵 另外，这个原理也是开始容易，后面越来越难写，索性到了一个阶段就放弃了 偶曾经写过一个很短的C代码来做FNT变换，可惜夹在某本书上，随岁月而消失了 等我有时间做这个吧，或者诸君有兴趣写个蝶式变换的算法的通用语句？