［PHP］gmp_mul関数完全解説：大きな整数の乗算を自在に操る

PHP

はじめに

プログラミングにおいて大きな整数を扱う場面は少なくありません。暗号計算、金融計算、科学的計算など、PHPの標準的な整数型では表現できない巨大な数値を正確に処理する必要がある場合があります。そんなときに力を発揮するのが、PHP GMP拡張の一部であるgmp_mul関数です。この関数を使うことで、任意精度の整数同士の乗算が可能になります。

本記事では、gmp_mul関数の基本から応用まで徹底的に解説します。

gmp_mul関数の基本

構文

GMP gmp_mul ( GMP|int|string $a , GMP|int|string $b )

パラメータ

  • $a: 最初の被乗数（掛けられる数）
  • $b: 2つ目の被乗数（掛ける数）

戻り値

  • $a と $b の積（GMP数値型）

gmp_mul関数の特徴

gmp_mul関数には以下のような特徴があります：

  1. 任意精度: PHP整数型の制限（通常64ビット）を超える数値でも正確に計算できます。
  2. 柔軟な入力形式: 数値を整数、文字列、GMP数値オブジェクトとして渡すことができます。
  3. 高速な処理: 内部的に最適化された乗算アルゴリズムを使用しています。

基本的な使用例

単純な乗算

<?php
// 基本的な乗算
$product1 = gmp_mul(123, 456);
$product2 = gmp_mul("789", "101112");

echo "123 × 456 = " . gmp_strval($product1) . "\n";  // 56088
echo "789 × 101112 = " . gmp_strval($product2) . "\n";  // 79777368
?>

大きな数値の乗算

<?php
// 非常に大きな数値の乗算
$large_num1 = "12345678901234567890";
$large_num2 = "98765432109876543210";

$large_product = gmp_mul($large_num1, $large_num2);
echo "$large_num1 × $large_num2 = " . gmp_strval($large_product) . "\n";
// 結果: 1219326311370217952237463801111263526900
?>

負の数値の乗算

<?php
// 負の数値を含む乗算
$negative_product1 = gmp_mul(-123, 456);
$negative_product2 = gmp_mul(123, -456);
$negative_product3 = gmp_mul(-123, -456);

echo "-123 × 456 = " . gmp_strval($negative_product1) . "\n";  // -56088
echo "123 × -456 = " . gmp_strval($negative_product2) . "\n";  // -56088
echo "-123 × -456 = " . gmp_strval($negative_product3) . "\n";  // 56088
?>

実用的な応用例

1. ファクトリアル（階乗）の計算

<?php
function gmp_factorial($n) {
    if ($n < 0) {
        return false; // 負の数のファクトリアルは定義されていない
    }
    
    $result = gmp_init(1);
    for ($i = 2; $i <= $n; $i++) {
        $result = gmp_mul($result, $i);
    }
    
    return $result;
}

// 小さな数のファクトリアル
$fact5 = gmp_factorial(5);
echo "5! = " . gmp_strval($fact5) . "\n";  // 120

// 大きな数のファクトリアル
$fact50 = gmp_factorial(50);
echo "50! = " . gmp_strval($fact50) . "\n";
// 非常に大きな数が表示されます
?>

2. フィボナッチ数列の高速計算（行列乗算法）

<?php
function matrix_multiply($a, $b) {
    $c = [
        [gmp_add(gmp_mul($a[0][0], $b[0][0]), gmp_mul($a[0][1], $b[1][0])), 
         gmp_add(gmp_mul($a[0][0], $b[0][1]), gmp_mul($a[0][1], $b[1][1]))],
        [gmp_add(gmp_mul($a[1][0], $b[0][0]), gmp_mul($a[1][1], $b[1][0])), 
         gmp_add(gmp_mul($a[1][0], $b[0][1]), gmp_mul($a[1][1], $b[1][1]))]
    ];
    return $c;
}

function matrix_power($matrix, $n) {
    if ($n == 1) {
        return $matrix;
    }
    
    if ($n % 2 == 0) {
        $half_pow = matrix_power($matrix, $n / 2);
        return matrix_multiply($half_pow, $half_pow);
    } else {
        return matrix_multiply($matrix, matrix_power($matrix, $n - 1));
    }
}

function fibonacci($n) {
    if ($n <= 0) {
        return gmp_init(0);
    }
    if ($n == 1) {
        return gmp_init(1);
    }
    
    $base = [[gmp_init(1), gmp_init(1)], [gmp_init(1), gmp_init(0)]];
    $result = matrix_power($base, $n - 1);
    return $result[0][0];
}

// フィボナッチ数列の第10項
$fib10 = fibonacci(10);
echo "フィボナッチ数列の第10項: " . gmp_strval($fib10) . "\n";  // 55

// フィボナッチ数列の第100項
$fib100 = fibonacci(100);
echo "フィボナッチ数列の第100項: " . gmp_strval($fib100) . "\n";
// 354224848179261915075
?>

3. 大きな数の累乗計算

<?php
function gmp_custom_pow($base, $exponent) {
    if ($exponent < 0) {
        return false; // 負の指数は扱わない
    }
    if ($exponent == 0) {
        return gmp_init(1);
    }
    
    $result = gmp_init(1);
    $current_base = $base;
    
    while ($exponent > 0) {
        if ($exponent % 2 == 1) {
            $result = gmp_mul($result, $current_base);
        }
        $current_base = gmp_mul($current_base, $current_base);
        $exponent = intval($exponent / 2);
    }
    
    return $result;
}

// 2^10を計算
$pow_2_10 = gmp_custom_pow(gmp_init(2), 10);
echo "2^10 = " . gmp_strval($pow_2_10) . "\n";  // 1024

// 7^50を計算
$pow_7_50 = gmp_custom_pow(gmp_init(7), 50);
echo "7^50 = " . gmp_strval($pow_7_50) . "\n";
// 非常に大きな数が表示されます
?>

4. 組み合わせ（二項係数）の計算

<?php
function gmp_binomial($n, $k) {
    if ($k < 0 || $k > $n) {
        return gmp_init(0);
    }
    
    // nCk = n! / (k! * (n-k)!)
    if ($k > $n - $k) {
        $k = $n - $k; // 計算を減らすための最適化
    }
    
    $result = gmp_init(1);
    
    for ($i = 0; $i < $k; $i++) {
        $result = gmp_mul($result, gmp_sub($n, $i));
        $result = gmp_div($result, gmp_add($i, 1));
    }
    
    return $result;
}

// 5C2を計算
$combination_5_2 = gmp_binomial(5, 2);
echo "5C2 = " . gmp_strval($combination_5_2) . "\n";  // 10

// 100C50を計算
$combination_100_50 = gmp_binomial(100, 50);
echo "100C50 = " . gmp_strval($combination_100_50) . "\n";
// 非常に大きな数が表示されます
?>

5. カルマン法（大きな数の乗算）

<?php
function karatsuba_multiply($x, $y) {
    // 文字列から数値に変換
    $x_str = gmp_strval($x);
    $y_str = gmp_strval($y);
    
    $n = max(strlen($x_str), strlen($y_str));
    
    // 基底ケース
    if ($n <= 4) {
        return gmp_mul($x, $y);
    }
    
    $m = intval(ceil($n / 2));
    
    // 数値を分割
    $high_x = gmp_init(substr($x_str, 0, -$m) ?: "0");
    $low_x = gmp_init(substr($x_str, -$m));
    $high_y = gmp_init(substr($y_str, 0, -$m) ?: "0");
    $low_y = gmp_init(substr($y_str, -$m));
    
    // 再帰的に3つの積を計算
    $z0 = karatsuba_multiply($low_x, $low_y);
    $z1 = karatsuba_multiply(gmp_add($low_x, $high_x), gmp_add($low_y, $high_y));
    $z2 = karatsuba_multiply($high_x, $high_y);
    
    // 結果を組み立てる
    $temp1 = gmp_mul($z2, gmp_pow(10, 2 * $m));
    $temp2 = gmp_mul(gmp_sub(gmp_sub($z1, $z2), $z0), gmp_pow(10, $m));
    
    return gmp_add(gmp_add($temp1, $temp2), $z0);
}

// 通常の乗算との比較
$num1 = "12345678";
$num2 = "87654321";

$start_normal = microtime(true);
$result_normal = gmp_mul($num1, $num2);
$time_normal = microtime(true) - $start_normal;

$start_karatsuba = microtime(true);
$result_karatsuba = karatsuba_multiply(gmp_init($num1), gmp_init($num2));
$time_karatsuba = microtime(true) - $start_karatsuba;

echo "通常の乗算結果: " . gmp_strval($result_normal) . "\n";
echo "カルマン法の結果: " . gmp_strval($result_karatsuba) . "\n";
echo "通常の乗算時間: {$time_normal}秒\n";
echo "カルマン法の時間: {$time_karatsuba}秒\n";

// 注: 小さな数値ではgmp_mulの方が速いことが多いです。
// カルマン法は非常に大きな数値で効果を発揮します。
?>

パフォーマンスと注意点

パフォーマンス

GMPライブラリは内部的に最適化された乗算アルゴリズムを使用しています：

  1. 通常の乗算: 小さな数値では標準的な乗算アルゴリズム
  2. カラツバ法: 中程度の数値では再帰的なカラツバアルゴリズム
  3. シェーンハーゲ-シュトラッセン法: 非常に大きな数値ではFFTベースのアルゴリズム

これらのアルゴリズムは自動的に切り替わるため、開発者が意識する必要はありません。

注意点

  1. GMP拡張が必要: この関数を使用するには、PHPにGMP拡張がインストールされている必要があります。
<?php
if (!extension_loaded('gmp')) {
    echo "GMP拡張がインストールされていません。\n";
    exit;
}
?>
  1. メモリ使用量: 非常に大きな数値を扱う場合、計算に必要なメモリ量が増加することに注意してください。
  2. 戻り値の型: 結果はGMP数値型で返されるため、通常のPHP整数として使用するには変換が必要です。
<?php
$product = gmp_mul("123456789", "987654321");

// GMP数値として直接使用
$squared = gmp_mul($product, $product);

// 文字列に変換
$product_str = gmp_strval($product);

// PHPの整数型に変換（範囲内の場合のみ）
if (gmp_cmp($product, PHP_INT_MAX) <= 0 && gmp_cmp($product, PHP_INT_MIN) >= 0) {
    $product_int = intval($product_str);
}
?>

PHPの通常の乗算演算子との比較

PHPの標準的な乗算演算子（*）とgmp_mul関数の主な違いは以下の通りです：

  1. 精度: *演算子はPHPの整数限界（通常は64ビット）に制限されますが、gmp_mulは任意精度です。
  2. オーバーフロー: 標準演算子では大きすぎる数値はオーバーフローしてしまいますが、GMPでは問題ありません。
<?php
// PHP標準の乗算と比較
$large1 = "9223372036854775807"; // PHPのINT_MAXに近い値
$large2 = "2";

// PHPの整数としての乗算（オーバーフローする可能性あり）
$php_result = (int)$large1 * (int)$large2;

// GMPでの乗算
$gmp_result = gmp_strval(gmp_mul($large1, $large2));

echo "PHP (*): $php_result\n";  // オーバーフローする可能性あり
echo "GMP (gmp_mul): $gmp_result\n";  // 正確な結果
?>

まとめ

gmp_mul関数は、PHPで大きな整数の乗算を行うための強力なツールです。暗号計算、科学的計算、金融計算など、精度が重要な場面で活躍します。標準の演算子では扱えない大きさの数値でも正確に計算できることが特徴です。

また、GMP拡張の他の関数と組み合わせることで、複雑な数学的アルゴリズムも効率的に実装できます。大きな整数を使った計算が必要な場合には、ぜひGMP拡張とgmp_mul関数を検討してみてください。

タイトルとURLをコピーしました