Fast Multiplication of Large Integers Using PHP GMP Library

In computer science, integer arithmetic is fundamental, but traditional methods become inefficient for very large numbers; this article introduces how to use PHP's GMP (GNU Multiple Precision) library to achieve fast multiplication of big integers.

1. GMP Library Overview

The GMP library offers high‑precision arithmetic, supporting addition, subtraction, multiplication, division, and exponentiation for arbitrarily large integers. PHP includes a GMP extension that wraps these capabilities with a simple API.

2. Fast Multiplication Algorithm

The fast multiplication algorithm reduces the complexity from O(n²) to roughly O(n^{1.585}) by applying a divide‑and‑conquer strategy similar to Karatsuba multiplication. It splits each operand into high‑ and low‑order parts, recursively multiplies the parts, and combines the results using the formula:

ac·10^{2m} + ((a+b)(c+d) - ac - bd)·10^{m} + bd

where m is the split position. The process repeats until the sub‑problems are small enough for direct multiplication.

3. PHP Code Example

The following PHP code demonstrates the implementation of the fast multiplication algorithm using the GMP extension:

<?php
function multiply($x, $y) {
    $x_gmp = gmp_init($x);
    $y_gmp = gmp_init($y);

    // Direct multiplication for small numbers
    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 ($a) and low ($b) 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 ($c) and low ($d) parts
    $y_str = gmp_strval($y_gmp);
    $c = substr($y_str, 0, -$split_point);
    $d = substr($y_str, -$split_point);

    // Recursive multiplications
    $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 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 the above script produces the product of the two large integers efficiently.

PHP Practical Development Fast‑Track

Scan the QR code to receive free learning materials