Prev: noise & PSNR of image
Next: Narx neural network with different delays for inputs and outputs
From: Timothy on 14 Apr 2010 05:52

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(a)physics.harvard.edu> wrote in message <hd5etq$j9f$1(a)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
From: John D'Errico on 14 Apr 2010 08:34
"Rodrigo" <guerra.remove.this(a)physics.harvard.edu> wrote in message <hd5etq$j9f$1(a)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
 | 
Pages: 1
Prev: noise & PSNR of image
Next: Narx neural network with different delays for inputs and outputs