阶乘使用FFT

我想在Ç计算一个非常大的n的阶乘（上百万）来实现程序，用FFT和二元分裂法。阶乘使用FFT

我已经实现了一个简单的库来表示任意精度整数。要计算FFT和IFFT，我使用twofft.c和four1.c从例程 “数字食谱用C”

达到一定N，一切正常，但当数字（浮动数组）太大时，在归一化和舍入之后，具有错误的值。

例如，如果我有两个数与2000位与40个零结束，我必须将它们相乘彼此（使用FFT），当我计算IFFT，一些结束零成为“一”。发生这种情况是因为当我四舍五入这个“零”（例如0.50009）时，它们变成了“一个”。现在，我不知道我的执行是否错误，或者如果我必须以不同的方式舍入这个数字。我试图同时使用二元分割法和因式分解，但N> = 9000，结果是错。

有办法解决这个问题吗？感谢您的关注，并对我的英语不好。

来源

2013-03-11 user2156701

请格式化您的问题！除此之外，'C'不能处理如此大的数字。 – 2013-03-11 12:21:14

请发布一个说明您的问题的最小代码示例。 – 2013-03-11 12:21:32

@ bash.d：OP明确表示，他/他实现并使用任意精度整数库来完成当前任务。 – datenwolf 2013-03-11 12:23:51

如何表示任意的精度整数？

我的意思是你实际使用的是什么类型？

你能告诉我们你的代码吗？

如果你觉得真懒，你可以复制这个项目我已经几个月前提出： https://github.com/nomadster/ESP

编辑：

通过进一步阅读您的文章我被这句话假设

“这发生是因为当我舍入其中一个“零”（例如0.50009）时，他们变成了“一”“

您仍然不知道fft乘法仅适用于rou ndoff误差小于0.5。所以在我看来（当且仅当我正确地解释了你的神秘消息）你正在使用不具有所需精度的浮点类型。

来源

2013-04-09 13:53:05

为了记录在案：

我也注意到，从数值食谱由IFFT返回从four1.c错误的价值观。我只用N = 256个复数值作为输入进行测试，以某种方式进行汇编，它们应该导致一个真实的唯一时域信号。

生成的时域矢量必须镜像（结束到开始，反之亦然...）并移位一个以符合其他实现的IFFT。（我简单地基于IDFT公式，测试了numpy.fft.ifft，octave的ifft和一个逆离散傅立叶变换，而这些变换应该是最初确定的）。

版本收件人提供的版本中必须存在基本算法错误。在他们的书中没有涉及到这个问题的描述。

来源

2015-12-10 14:35:42 Phaiax

阶乘使用FFT

回答

相关问题