Ok my problem is of mathematical nature. I have an array of bytes whose length is X, i need to find the two closest numbers which multiplied together equal X. I need to do this because i am bulding a bitmap from an array of bytes and i need to make the bitmap look like a square as much as possible. I am coding this in C# but don' t worry about syntax, any algorithm or pseudo-code will do. Thanks in advance for your help
7
votes
7 Answers
11
votes
There's probably a better algorithm for this, but off the top of my head:
1) Take the square root of the number X; we'll call it N.
2) Set N equal to the ceiling of N (round up to the nearest integer).
3) Test for (X % N). If N divides evenly into X, we found our first number.
if 0, divide X by N to get M. M and N are our numbers
if not 0, increment N by 1 and start step 3 over.
4
votes
Note that if X is at all large, then starting from sqrt(X) and working downwards one step at a time will be a miserable task. This may take a huge amount of time.
If you can find the factors of the number however, then simply compute all divisors of X that are less than sqrt(X).
Consider the number X = 123456789012345678901234567890. The smallest integer less than sqrt(X) is 351364182882014, so simply decrementing that value to test for a divisor may be problematic.
Factoring X, we get this list of prime factors:
{2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161}
It is a fairly quick operation to compute the divisors less then sqrt(N) given the prime factors, which yields a divisor 349788919693221, so we have
349788919693221 * 352946540218090 = 123456789012345678901234567890
These are the closest pair of divisors of the number N. But, how many times would we have needed to decrement, starting at sqrt(N)? That difference is: 1575263188793, so over 1.5e12 steps.
A simple scheme to determine the indicated factors (in MATLAB)
Dmax = 351364182882014;
F = [2, 3, 3, 3, 5, 7, 13, 31, 37, 211, 241, 2161, 3607, 3803, 2906161];
D = 1;
for i = 1:numel(F)
D = kron(D,[1,F(i)]);
D = unique(D);
D(D > Dmax) = [];
end
D(end)
ans =
349788919693221
The other factor is obtained simply enough. If the numbers are too large to exceed the dynamic range of a flint as a double, then you will need to use some variation of higher precision arithmetic.
4
votes
I have rewritten the MATLAB answer proposed above by user85109 in a detailed function with sufficient comments and some simpler terms. Certainly quite efficient, works for large numbers and hopefully easy to write in any language which provides a library function for getting prime factorization of an integer.
function [a, b] = findIntegerFactorsCloseToSquarRoot(n)
% a cannot be greater than the square root of n
% b cannot be smaller than the square root of n
% we get the maximum allowed value of a
amax = floor(sqrt(n));
if 0 == rem(n, amax)
% special case where n is a square number
a = amax;
b = n / a;
return;
end
% Get its prime factors of n
primeFactors = factor(n);
% Start with a factor 1 in the list of candidates for a
candidates = [1];
for i=1:numel(primeFactors)
% get the next prime factr
f = primeFactors(i);
% Add new candidates which are obtained by multiplying
% existing candidates with the new prime factor f
% Set union ensures that duplicate candidates are removed
candidates = union(candidates, f .* candidates);
% throw out candidates which are larger than amax
candidates(candidates > amax) = [];
end
% Take the largest factor in the list d
a = candidates(end);
b = n / a;
end
1
votes
A perfect square would have a side of SQRT(X) so start from there and work downward.
int X = ...
for(int i=sqrt(x);i>0;i--) {
// integer division discarding remainder:
int j = X/i;
if( j*i == X ) {
// closest pair is (i,j)
return (i,j);
}
}
return NULL;
Note this will only work if X is actually divisible by two integers (ie a prime X is going to end up with (1,X)). Depending on what you're doing you might better off picking slightly larger dimensions and just making it square ... ie have the sides be CEILING(SQRT(X)).
0
votes
One alternative is to set up this optimization problem
Minimize the difference of the factors X and Y the difference of the product X × Y and P. You have thus an objective function that is weighted some of two objective:
min c × |X × Y - P| + d × |X – Y|
subject to X, Y ∈ ℤ
X, Y ≥ 0
where c, d are non-negative numbers that define which objective you value how much.
Like the sqrt solution a lot however : )
0
votes
Thanks for your answers. I have made a function that finds the closest 3 integers building on the sqrt approach:
function [a, b, c] = findIntegerFactorsCloseToCubeRoot(n)
% a cannot be greater than the cube root of n
% b cannot be smaller than the cube root of n
% we get the maximum allowed value of a
amax = floor(nthroot(n,3))
if amax^3 == n
% special case where n is a cube number
a = amax;
b = a;
c = a;
return;
end
% Get its prime factors of n
primeFactors = factor(n);
% Start with a factor 1 in the list of candidates for a
candidates = [1];
for i=1:numel(primeFactors)
% get the next prime factor
f = primeFactors(i);
% Add new candidates which are obtained by multiplying
% existing candidates with the new prime factor f
% Set union ensures that duplicate candidates are removed
candidates = union(candidates, f .* candidates);
% throw out candidates which are larger than amax
candidates(candidates > amax) = [];
end
% Take the largest factor in the list d
a = candidates(end);
% call similar function for remaining 2 factors
[b, c] = findIntegerFactorsCloseToSqRoot(n/a);
end
