Fast Multiplication of Large Integers Using PHP GMP Library

In computer science, integer operations are fundamental, but traditional methods become inefficient for very large numbers. This article shows how to use PHP's GMP (GNU Multiple Precision) library to perform fast multiplication of big integers.

1. Introduction to GMP Library

The GMP library provides high‑precision arithmetic functions such as addition, subtraction, multiplication, division, and exponentiation. Its algorithms are efficient for extremely large integers. PHP includes a GMP extension that wraps these capabilities with a simple interface.

2. Fast Multiplication Algorithm

The fast multiplication algorithm (similar to Karatsuba) reduces the multiplication complexity from O(n²) to O(n^log₂3) by recursively splitting each operand into high‑ and low‑order parts, multiplying the parts, and combining the results using the formula:

// Simplified representation of the Karatsuba formula
// Let x = a·10^m + b, y = c·10^m + d
// Then x·y = a·c·10^(2m) + ((a+b)·(c+d) - a·c - b·d)·10^m + b·d

The steps are: split the numbers, compute three sub‑products (high×high, low×low, and (high+low)×(high+low) minus the previous two), then combine them with appropriate powers of 10, recursing until the operands are small enough for direct multiplication.

3. PHP Code Example

The following PHP code demonstrates the recursive fast multiplication using the GMP extension:

<?php
function multiply($x, $y) {
    $x_gmp = gmp_init($x);
    $y_gmp = gmp_init($y);
    // When operands are small enough, use direct multiplication
    if (gmp_cmp($x_gmp, "1000000") <= 0 || gmp_cmp($y_gmp, "1000000") <= 0) {
        return gmp_strval(gmp_mul($x_gmp, $y_gmp));
    }
    // Split $x into high and low parts
    $x_str = gmp_strval($x_gmp);
    $split_point = ceil(strlen($x_str) / 2);
    $a = substr($x_str, 0, -$split_point);
    $b = substr($x_str, -$split_point);
    // Split $y into high and low parts
    $y_str = gmp_strval($y_gmp);
    $c = substr($y_str, 0, -$split_point);
    $d = substr($y_str, -$split_point);
    // Recursively compute sub‑products
    $ac = multiply($a, $c);
    $bd = multiply($b, $d);
    $abcd = multiply(gmp_add($a, $b), gmp_add($c, $d));
    $ad_bc = gmp_sub($abcd, gmp_add($ac, $bd));
    // Combine the results
    $result = gmp_add(
        gmp_mul(gmp_pow(10, 2 * $split_point), $ac),
        gmp_add(
            gmp_mul(gmp_pow(10, $split_point), $ad_bc),
            $bd
        )
    );
    return gmp_strval($result);
}

// Example input
$x = "12345678901234567890";
$y = "98765432109876543210";
// Call the multiplication function
$result = multiply($x, $y);
echo "Result: " . $result . "\n";
?>

Running this script with two large integer strings produces their product efficiently.