階乘使用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

回答

相關問題