Question

Hello folks, i need an algorithm that finds a solution for a + b + c = a*b*c = 5,70 . I did it in three for loops (all of them starts from 0,01 and incrementing by 0,01), but i'm looking for a faster algorithm.
Hello folks, i need an algorithm that finds a solution for a + b + c = a*b*c = 5,70 . I did it in three for loops (all of them starts from 0,01 and incrementing by 0,01), but i'm looking for a faster algorithm.
@Computer Science

Answer 1

\[a * b * c = 5.7\]
\[c = 5.7/(a*b)\]
a+b+c = 5.7 or c = 5.7 - a - b
5.7 -a - b = 5.7/(a*b)
Solve this to create a polynom:
\[-a ^{2}b ^{2} + 5.7 ab - 5.7 = 0\]
Range: a = [0.01,5.7], b = [0.01,5.7], c = [0.01,5.7]

Using quadratic formula: \[(-b \pm \sqrt{b^{2} - 4ac})/2a\]

\[(-5.7a \pm \sqrt {(5.7a)^{2} - 4*5.7a^{2})} /(-2a^{2}) = (2.85/a) \pm (0.5 * \sqrt{32.49a ^{2} - 22.8 ^{2}})/a^{2} \]

\[2.85/a \pm (\sqrt{2.4225})/a\] = \[(2.85 \pm 1.556) /a\]

So, the possible value for b is (2.85 +1.556)/a = 4.406/a or (2.85 - 1.556) )/a = 1.2941/a

Because b <= 5.7, a range is [1.2941/5.7, 4.406/5.7] = [0.227 .. 0.773]

Algorithm:

a = 0.2

Loop:
b = 1.2941/0.2
c = 5.7 - 0.2 - 1.2941
if (a + b + c = 5.7) then
if (a * b * c == 5.7) then loop_is_done
else
a = a + 0.01
if (b > 4.406/a) then loop_is_done
end_loop

Answer 2

Sorry, the algorithm is wrong, it should be:
a = 0.2

loop:
b = 1.2941/a
c = a + b +c
if (5.7/(a*b) = c) then loop_is done

Answer 3

You're given two equations in three variables. It will have infinite solutions, (a, b, c). Specifically, since the two equations are not linearly independent, there will be exactly one free variable, and the other two variables can be expressed in terms of that free variable. Since the two equations are both symmetric wrt a, b, and c, it doesn't really matter which one we make the free variable, because the expressions for the other two will still be the same. So, let's make a the free variable. Also, 5.7 seems pretty arbitrary, so I'll use k.

mlutfi had the right idea:
abc = k
a+b+c = k
So
c = k/(ab)
c = k-a-b
We'll use these expressions for c later; one we will use to calculate c, the other we will use to check our solutions.
We now have two expressions for c. We can set them equal to each other.
k/(ab) = k-a-b
This is an equation in two variables, a and b. We can solve for one in terms of the other.
[algebra]
ab^2 + a(a-k)b + k = 0
This is a quadratic equation in b. So the roots are at
\[b = \frac{k-a}{2} \pm \sqrt{(\frac{k-a}{2})^{2} - \frac{k}{a}}\]This is our expression for b in terms of a.

Now, for any a (and constant value for k) we can calculate the value for b. And given this a and b (and k) we can calculate c. So we only have to loop over values for a. We're given k. We can then calculate b = f(a, k) and c = g(a, b, k). We're essentially done. But if you naively implement this algorithm you'll get errors that say you're trying to take the square root of a negative number.

The problem comes when we try to loop over values for a. The formula for b in terms of a and k involves a square root. So, if we're limited to real solutions, then we have to limit our range of a's to yield nonnegative determinants. That is,\[(\frac{k-a}{2})^{2} - \frac{k}{a} \ge 0\]or\[a^{3}-2ka^{2}+k^{2}a-4k\ge0\]That's a cubic equation in a. The roots will be expressions in k. So, given k we can figure out what legal values for a are. http://en.wikipedia.org/wiki/Cubic_function#General_formula_of_roots There's the general formula for the roots of a cubic polynomial. Click on the link then immediately come back. We're not going there. So, when looping over values for a, evaluate the expression for the determinant, and if it's negative then just reject that value of a (continue the loop).

For your value k = 5.7 the roots of that polynomial are at 1.0581742, 2.89236215, and 7.44946364. And, since the coefficient of a^3 is positive, the determinant will be nonnegative between the first two roots, and after the third root. I guess it's theoretically possible the equation could have only one real root, but for 5.7 it has three.

So, using these ranges, loop over a, generate b from a, and generate c from a and b. I used c=k-a-b to calculate c, then I used abc=k to check my solutions.

So, to summarize all this rambling:
1. Write c in terms of a and b.
2. Write b in terms of a.
3. Loop over a (reject invalid values).
4. Use a to calculate b.
5. Use a and b to calculate c.
6. Check your solution.