Results 1 to 2 of 2

Thread: Fft

  1. #1

    Fft

    I hadn't noticed this until a day or two ago. I moved a worker from a slower computer and found the following:

    [Worker #1 May 8 18:04] Resuming PRP test of 24737*2^18572071+1 using zero-padded FFT length 2048K, 2 threads
    [Worker #1 May 8 18:04] Iteration: 1382378 / 18572085 [7.44%].
    [Worker #2 May 8 18:04] Resuming PRP test of 21181*2^17999900+1 using all-complex FFT length 1536K, 2 threads
    [Worker #2 May 8 18:04] Iteration: 15725838 / 17999914 [87.36%].


    What is the difference between a zero-padded FFT and one that uses all complex FFT length? I'm assuming the new FFT length is required (and becomes larger as we approach larger n values).

  2. #2
    Well, it is a rather complicated answer. The short explanation is that an all-complex FFT uses Dr. Richard Crandall's irrational base discrete weighted transform (IBDWT). These were described in a 1994 article in Mathematics of Computation. The alternative way to multiply large numbers using FFTs is to pad them with lots of zeros so that the result of the multiplication fits in the FFT without any data "wrapping around" and corrupting the result.

    Prime95 implements both FFT types and chooses the fastest one for the number you are testing.

    Yes, larger numbers will inevitably lead to larger FFT sizes.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •