Find closest divisor of a number

I have a vector of 65536 elements that I want to divide into n columns. I have found the optimal n that I need in order to perform further calculations, but it is not a divisor of 65536. How can I round it up to the closest divisor that is also an integer (since i'll be using a reshape function)?

This is the code i'm using up to now:

n=(9*(Ttot*Br(i))^4)^(1/5);
n=round(n);
X=reshape(X,[],n);

Answer 1

[John D'Errico]

Simple enough. I wrote an alldivisors code many years ago...

vlen = 65536;
div_vlen = alldivisors(vlen)

div_vlen = 1×17

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536

Now, suppose that you have chosen n as 50. You just need to find the smallest divisor in that set that is at least as large as n.

n = 50;
N = div_vlen(find(div_vlen >= n,1,'first'))

N = 64

As I said, simple enough. The alldivisors code is given here:

function divs = alldivisors(N)
% compute the set of all integer divisors of the positive integer N

% first, get the list of prime factors of N. 
facs = factor(N);

divs = [1,facs(1)];
for fi = facs(2:end)
    % if N is prime, then facs had only one element,
    % and this loop will not execute at all
    
    % this outer product will generate all combinations of
    % the divisors found so far, and the current divisor
    divs = [1;fi]*divs;
    
    % unique eliminates the replicate divisors
    divs = unique(divs(:)');
end

end

[DANIELE PASINI]

Thank you very much, this works perfectly

[David Huynh]

Just as a heads up, the function divisors() was introduced in MATLAB R2014b.

Also, in terms of speed (which I realize may not matter much here), it works well just to search for the nearest divisor incrementally:

n = 65536;
m = 50;
d = roundUpNearestDivisor(n,m)

d = 64

fprintf('Increment method: %f ms\n',timeit(@() roundUpNearestDivisor(n,m))*1e3)

Increment method: 0.047790 ms

fprintf('Brute force method: %f ms\n',timeit(@() roundUpNearestDivisor(n,m,'brute'))*1e3)

Brute force method: 13.670790 ms

function d = roundUpNearestDivisor(n,m,opt)
%ROUNDUPNEARESTDIVISOR Finds the smallest divisor of n greater than or equal to m

%%
if nargin < 3 || isempty(opt)
    opt = 'increment';
end

%%
if mod(n,m) == 0
    % if m is divisor of n, return m
    d = m;
    return
elseif isprime(n)
    % if n is prime, divisors = [1,n], thus round m up to n
    d = n;
    return
else
    switch opt
        case 'increment'
            %% search next divisor larger than m
            ii = 1;
            while true
                if mod(n,m+ii) == 0
                    d = m + ii;
                    return
                else
                    ii = ii + 1;
                end
            end
            
        case 'brute'
            %% brute force option
            D = divisors(n);
            idx = find(D >= m,1);
            d = D(idx);
            return
    end
    
end

end

Answer 2

[Arran Sykes]

I had a similar problem.. There's an alternative way in this specific case if you like to make your code as compact as possible. Though there may be an even better solution if someone really wanted it.

All of your divisors are going to be powers of 2. So, any number of columns is going to be . That is 2 to the power of the ceiling of log_2 (n_desired). If you want to go down then you can take the floor.

With n_desired being the number of columns you are looking for and n being the rounded up number of columns.

You can then find the divisor by doing: with d being your divisor. Again, note this only works explicitly for powers of 2.

In code this is:

n_des = 50; %number of columns you would like
m = 65536;
n = 2^(ceil(log2(n_des)))

n = 64

d = m/n

d = 1024

function d = nearestDivisor(n_des,m)
n = 2^(ceil(log2(n_des))); % number of columns you actually need - use floor() to round down
d = m/n; % divisor
end