Path: news.mathworks.com!newsfeed-00.mathworks.com!news.kjsl.com!news.glorb.com!news2.glorb.com!postnews.google.com!2g2000prl.googlegroups.com!not-for-mail
From: TideMan <mulgor@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT and small prime factors
Date: Sun, 8 Nov 2009 15:42:07 -0800 (PST)
Organization: http://groups.google.com
Lines: 31
Message-ID: <814ec236-8aa8-436d-8f22-cbe487633266@2g2000prl.googlegroups.com>
References: <hd5etq$j9f$1@fred.mathworks.com> <hd7jj9$gov$1@fred.mathworks.com>
NNTP-Posting-Host: 202.78.152.105
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1257723727 9301 127.0.0.1 (8 Nov 2009 23:42:07 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Sun, 8 Nov 2009 23:42:07 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: 2g2000prl.googlegroups.com; posting-host=202.78.152.105; 
	posting-account=qPexFwkAAABOl8VUndE6Jm-9Z5z_fSpR
User-Agent: G2/1.0
X-HTTP-Via: 1.1 bc3
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.1.5) 
	Gecko/20091102 Firefox/3.5.5,gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:583434


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.