mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2003-12-29, 20:48   #1
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

192 Posts
Default Different word sizes/accuracy for forward/inverse transform?

During my studies of FFT+NTT I got following idea:

In case of FFT we have to provide enough bits per word to safely hold the squares of the values in frequency space without getting rounding errors during the inverse transform. But actually we don't need that many bits during the forward transform. That offers the possibility to use a floating point format with a smaller mantissa. I assume that the 24bit mantissa of single precision numbers is unfortunately just a few bits too short to fully utilize the double precision 53bit mantissa on the way back.

However there is maybe still a possible gain by using SP for forward and DP for inverse transform thanks to roughly double throughput for single precision calculations using SIMD instructions on some architectures. The memory traffic wouldn't decrease much if at all because IMO it would be better to have the 32bit values at nearly the same locations as the doubles later to avoid additional TLB/cacheline issues, which could appear if some out-of-place transform style is being used.

An enhancement is possible by grouping SP values of 2 cachelines together into one to reduce memory traffic. The unused space of cacheline size would be used for the doubles and the grouping of SP values is also necessary to be able to load them efficiently using SIMD instructions.

Another story is, if this scheme could be applied to NTTs by using primes of different sizes. Unfortunately the values we get after a forward transform are repeatedly multiplied by powers of roots and added - always modulo a chosen prime. So I imagine it will be difficult or even impossible to change these values in a way that a different prime (with more bits) can be used for the inverse transform. Any ideas?
Dresdenboy is offline   Reply With Quote
Old 2003-12-29, 21:25   #2
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

23×3×5×67 Posts
Default

The very first FFT I wrote for prime95 (way back in 1995) used a Nussbaumer FFT where the forward FFT used 112 bit integers and the inverse FFT used 224 bit integers. Then I read up on the Crandall/Fagin DWT and it was much faster.

Not sure if that's at all relevant to this thread...
Prime95 is offline   Reply With Quote
Old 2003-12-29, 22:55   #3
Dresdenboy
 
Dresdenboy's Avatar
 
Apr 2003
Berlin, Germany

192 Posts
Default

Quote:
Originally posted by Prime95
The very first FFT I wrote for prime95 (way back in 1995) used a Nussbaumer FFT where the forward FFT used 112 bit integers and the inverse FFT used 224 bit integers. Then I read up on the Crandall/Fagin DWT and it was much faster.

Not sure if that's at all relevant to this thread...
I think, it is as it shows that forward/inverse NTT may use different primes.

The floating point version of this idea could be tested easily. The DWT shouldn't cause troubles because the weights are just weights and don't change the number of relevant bits per word that much. And the mantissa size for the forward transform should be at least a half of the needed mantissa size for the squared values. All bits following the least significant mantissa bit will get lost, so we don't need to bring them into play. OTOH the multiplication pyramid shows, that a 50th bit of a factor would still have some influence on a double precision product.

BTW, how do the prospects for this 112/224 bit nussbaumer look on 64bit hardware with fast 64bit mul? It won't beat the floating point FFT but maybe there are other uses (for arbitrary large integer multiplication)
Dresdenboy is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Inverse Laplace Transform flouran Math 1 2010-01-18 23:48
FFT sizes Cruelty Riesel Prime Search 3 2006-07-12 15:15
How Much Memory at Various Sizes? wblipp GMP-ECM 5 2005-04-24 20:04
Cache Sizes Unregistered Hardware 4 2003-12-06 13:43
Looking Forward QuintLeo Lounge 5 2003-01-17 21:29

All times are UTC. The time now is 12:25.


Tue Oct 4 12:25:32 UTC 2022 up 47 days, 9:54, 0 users, load averages: 1.43, 1.36, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔