Thread Subject: FFT and small prime factors

I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)

Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.

I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.

Cheers

"Rodrigo" <guerra.remove.this@physics.harvard.edu> wrote in message <hd5etq$j9f$1@fred.mathworks.com>...
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

Any thoughts?

On Nov 9, 12:18 pm, "Rodrigo" <guerra.remove.t...@physics.harvard.edu>
wrote:
> "Rodrigo" <guerra.remove.t...@physics.harvard.edu> wrote in message <hd5etq$j9...@fred.mathworks.com>...
> > I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries).  To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> > Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data.  Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> > I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> > Cheers
>
> Any thoughts?

I looked at it and couldn't figure out what you were getting at.
Do you want an algorithm that calculates numbers that have primes of
2, 3, 5 (a la Singleton's FFT that takes numbers with primes up to
23), or what?
And if each FFT is for only a few thousand points, I don't know what
you're worried about.
Just use Matlab's FFT on whatever number you have. It is very fast.

On Nov 7, 7:46 pm, "Rodrigo" <guerra.remove.t...@physics.harvard.edu>
wrote:
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries).  To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data.  Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

Rodrigo

I'm not going to suggest an algorithm for you, but I will suggest
reasons why I don't think the algorithm you seek will provide the most
efficient solution to your fft application.
1) solutions should be weighted by the 'efficiency' of the kernels
used
2) the most efficient kernels may well not be primes.
3) the values of the weights depend on the particulars of the hardware
and software implementations considered.

I would suggest that you look at the 'automatic generation of fft
codes' literature to find examples of solutions that might match your
intended implementation. There has been considerable effort towards
optimization specific to implementation characteristics.

A couple of examples for different architectures that include
discussion of the problem and some if the approaches that have been
tried are:

http://vgrads.rice.edu/publications/pdfs/AEOS_Codegenerator_For_FFT.pdf
http://www.iseclab.org/people/pw/papers/vecpar04

Google can find you many more. If you have knowledge of the intended
platform, language, software environment, etc., consider adding that
to your search terms.

Dale B. Dalrymple

This will do it for integers lower than your input (just supply the largest prime factor). It is easy to make it find the next highest integer, also (just put a while loop and increase j on each iteration).

function out = nearestLowPrimeFac(in,low)

for i=1:in-1
    
    j = in - i;
    
    if max(factor(j)) == low, break, end
        
end

out = j;

end


"Rodrigo" <guerra.remove.this@physics.harvard.edu> wrote in message <hd5etq$j9f$1@fred.mathworks.com>...
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

"Rodrigo" <guerra.remove.this@physics.harvard.edu> wrote in message <hd5etq$j9f$1@fred.mathworks.com>...
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>

You can do it using integer (linear) programming.
I.e., take the log of your target number, as well
as any candidate small primes. Then the goal is
to minimize the distance in log space, where you
can form your target as the sum of integer amounts
of the logs of your small primes.

Of course, to do this, you need an IP solver for
the linear programming problem.

HTH,
John