Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT and small prime factors
Date: Sun, 8 Nov 2009 23:18:01 +0000 (UTC)
Organization: Harvard University
Lines: 10
Message-ID: <hd7jj9$gov$1@fred.mathworks.com>
References: <hd5etq$j9f$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1257722281 17183 172.30.248.38 (8 Nov 2009 23:18:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sun, 8 Nov 2009 23:18:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 541566
Xref: news.mathworks.com comp.soft-sys.matlab:583426


"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?