Efficient Factoring Algorithm Based on Quadratic Equations

Problem Background and Mathematical Modeling

In programming practice, we often encounter the problem: given the sum j and product i of two numbers, find the numbers a and b. Mathematically, this can be expressed as the following system of equations:

a + b = j
a * b = i

Using substitution method with a = j - b in the second equation, we obtain:

(j - b) * b = i
j*b - b² = i
b² - j*b + i = 0

This is precisely the standard form of a quadratic equation with coefficients: A = 1, B = -j, C = i.

Quadratic Equation Solving Algorithm

According to the quadratic formula:

b = [j ± sqrt(j² - 4*i)] / 2

The discriminant D = j² - 4*i determines the nature of the solutions:

• When D > 0, the equation has two distinct real solutions
• When D = 0, the equation has one repeated root
• When D < 0, the equation has no real solutions

PHP Implementation Code

Based on the mathematical principles above, we can implement an efficient solving function:

function findNumbers($sum, $product) {
    $discriminant = $sum * $sum - 4 * $product;
    
    if ($discriminant >= 0) {
        $sqrt_val = sqrt($discriminant);
        $b1 = ($sum + $sqrt_val) / 2;
        $b2 = ($sum - $sqrt_val) / 2;
        
        $a1 = $sum - $b1;
        $a2 = $sum - $b2;
        
        return array(
            array('a' => $a1, 'b' => $b1),
            array('a' => $a2, 'b' => $b2)
        );
    } else {
        return "No real solutions";
    }
}

Algorithm Verification and Case Analysis

Let's verify the algorithm's correctness through several typical examples:

Example 1: Sum = 5, Product = 6

$result = findNumbers(5, 6);
// Output: a=2, b=3 and a=3, b=2

Example 2: Sum = -14, Product = 45 (reference article case)

$result = findNumbers(-14, 45);
// Output: a=-9, b=-5 and a=-5, b=-9

Example 3: Sum = 14, Product = 9 (no real solutions case)

$result = findNumbers(14, 9);
// Output: "No real solutions"

Performance Comparison Analysis

Compared with traditional looping methods, the quadratic equation approach has significant advantages:

Looping Method (Reference Answer 2):

function loopMethod($sum, $product) {
    for ($a = 1; $a < $sum; $a++) {
        $b = $sum - $a;
        if ($a * $b == $product) {
            return array('a' => $a, 'b' => $b);
        }
    }
    return "No solution found";
}

Performance Comparison:

• Time Complexity: Quadratic method O(1), Looping method O(n)
• Space Complexity: Both O(1)
• Applicability: Quadratic method supports negative numbers and floats, looping method mainly for positive integers

Factoring Application Extensions

The factoring method proposed in Reference Answer 3 can be combined with our algorithm:

function factorCombination($target) {
    $factors = array();
    for ($i = 1; $i <= sqrt($target); $i++) {
        if ($target % $i == 0) {
            $factors[] = array($i, $target / $i);
        }
    }
    return $factors;
}

This method quickly finds all possible factor pairs, which can then be filtered based on the sum condition.

Edge Case Handling

In practical applications, the following edge cases need consideration:

• Zero values: When product is 0, at least one number must be 0
• Large number operations: Use BCMath extension for big number calculations
• Floating-point precision: Use appropriate precision for float comparisons

Conclusion

The quadratic equation-based factoring algorithm provides an efficient and universal solution. This algorithm not only achieves optimal time complexity but also handles various numerical scenarios including negative numbers. By mathematically modeling the problem as standard quadratic equation solving, we avoid unnecessary loop computations, providing a reliable technical foundation for factoring-related applications.