3
$\begingroup$

I am writing a program that processes data based on an integer factor. The process can either be done at once, or in multiple stages. For example, one stage with factor 500 could be replaced by three stages, the first one with factor 50, the second with factor 5, the third with factor 2. Because, 50*5*2 = 500. The reason for this is that the run-time complexity of the code is directly proportional to this integer.

It is best to order these sub-factors by size, largest first. Like in the example above: [50,5,2]. But, it is also best to make sure that the sum of these sub-factors is as small as possible. This means for example that [10,10,5] is better than [50,5,2], because the sum of the former is 25, while the sum of the latter is 57. This sum defines the run-time complexity, as mentioned above. The lower the number, the less work needs to be done, and the faster the code is.

It is of course possible that a factor simply cannot be decomposed into exactly the given number of sub-factors. One example is 25: Here, only [5,5] is possible. For this reason, I want something that decomposes an integer number into up to N numbers (N being a user specified parameter), with the constraint above about the sum of these numbers being as small as possible.

So far, I've had no luck finding anything that solves this. Does anybody know more?

$\endgroup$
  • 1
    $\begingroup$ Your best case is when the number is an Nth power. Otherwise as a rule of thumb you want numbers "as close as possible" to the Nth root, but to find the exact optimum split you probably need at least some level of brute force. $\endgroup$ – Peter Taylor Jan 10 at 14:32
  • $\begingroup$ $25$ as a product of $3$ numbers is $5\cdot 5\cdot 1$, giving a sum of $11$ $\endgroup$ – Daniel Mathias Jan 10 at 14:48
  • $\begingroup$ Using the Nth root is a good idea. The "brute force" part I still am not sure about, but I suppose involving prime factor decomposition would be a start. For example, decompose 500 into 2*2*5*5*5 . Then, calculate the Nth root (N=3), which is ~7.937 . Then pick the prime factors from the decomposition earlier that, when multiplied, provide a number closest to the root. For example, pick a factor 2 and another factor 5 out of the factors 2,2,5,5,5 , multiply them, 2*5=10, which is closest to 7.937. Then repeat the same with the remaining factors 2,5,5 . The closest is again 10 etc. $\endgroup$ – dv_ Jan 10 at 14:53
  • $\begingroup$ @DanielMathias , yes, but a factor of 1 makes no sense, since it means "identity". EDIT: I mean, it would not actually process anything; the output would be identical to the input, so it would just waste processor power. So, a factor of 1 is disallowed. $\endgroup$ – dv_ Jan 10 at 14:54
  • $\begingroup$ How large can $N$ and the number of stages be? $\endgroup$ – Michael Lugo Jan 10 at 15:39
1
$\begingroup$

The following algorithm gives an approximate solution, which is exact if $N=2$.

Let $a$ be the integer to be decomposed as a product of $N$ factors.

If $N=2$, let $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le\sqrt a\} $ and $d_2=a/d_1$. Then $a=d_1\times d_2$ is the optimal solution. For instance, if $a=112476$, then $\sqrt a=335.374$, $d_1=309$, $d_2=364$ and $d_1+d_2=673$.

Suppose now that $N=3$. Choose $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le a^{1/3}\}$ and apply the method for $N=2$ to $a/d_1$. As an example, take $a=112476$ again. Then $a^{1/3}=48.271$ and $d_1=42$; applying the method for $N=2$ to $a/d_1=2678$ we find $a/d_1=26\times103$, giving the decomposition $$ 112476=42\times26\times103,\quad42+26+103=171. $$ The actual minimum is given by $$ 112476=28\times39\times103,\quad28+39+103=170. $$ Not bad.

The process can be iterated to any value of $N$. Choose $d_1=\max\{k\in\Bbb N:k\text{ divides }a,k\le a^{1/N}\}$ and apply the method for $N-1$ to $a/d_1$.

For large $a$, the most time consuming part will be the computation of the divisors of $a$. However, not all of them are needed. Start from $\lfloor a^{1/N}\rfloor$ and go down by one until you find a divisor of $a$.

$\endgroup$
  • $\begingroup$ Thanks, this is good. I don't need an optimal solution, just an approximate one, and this fits the bill. $\endgroup$ – dv_ Jan 18 at 10:47
3
$\begingroup$

For every composite number $n=a\times b$ with $a,b>1$, you will have $n \ge a+b$. The only time that you have equality is $4=2\times 2=2+2$.

This means that it will always improve your runtime if you can split off another factor, so you basically you want to factorise your number into primes because those cannot be split any further.

If you do insist on limiting yourself to at most $N$ stages, then you may have to combine some primes of that prime factorisation to make fewer factors.

This can be very hard to do optimally if $N$ is low and you have many primes. In this case you would want to make the N stages around the same size, because that is when their sum is minimal. It then essentially becomes a cutting stock problem.

Actually you are multiplying numbers to make roughly equal sizes, whereas the cutting stock problem involves adding numbers to make equal sizes, but that is the same thing because you can take the logarithms first to convert multiplication to addition.

To give you an example of how tricky it can be, consider $3600$. This splits into 8 primes:
$2,2,2,2,3,3,5,5$
To reduce it to 7 or 6 factors you can combine the $2$s without changing the sum:
$3,3,4,4,5,5$
To get it down to 5 factors, you could combine the two smallest:
$4,4,5,5,9$
but it is better to keep the factors of $3$ separate and re-distribute the factors of $2$ instead:
$4,5,5,6,6$
To get this to 4 factors, you might think you should split the remaining $4$ and combine it with the $5$s like this:
$6,6,10,10$
but it is better to now combine the two factors of $3$:
$5,8,9,10$
The best arrangement into 3 factors is completely different, with the factors of $3$ separated again:
$15,15,16$
And for 2 factors you can do a completely even split:
$60,60$

The point this illustrates is that it is a hard problem, so if you don't need to limit the number of factors, then just go with the full factorisation.

$\endgroup$
  • $\begingroup$ Full factorisation might be an option, but at some point there is a tradeoff between runtime complexity and overhead from CPU cache misses etc. So, if for example there are lots of primes involved, then it may actually be better to have fewer non-primes instead. I do wonder if there is a greedy algorithm that could be used here. It is okay if the solution isn't strictly optimal, but pretty good overall. $\endgroup$ – dv_ Jan 10 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.