PHP での任意に大きな整数の算術演算

StackOverflow https://stackoverflow.com/questions/37391

  •  09-06-2019
  •  | 
  •  

質問

PHP は 32 ビットの符号付き整数のみをネイティブにサポートしていることを考えると、任意の大きな整数を扱うのに最適な言語ではありません。ただし、私がやろうとしているのは、任意の大きな 2 進数を表現し、そのうちの 2 つに対して単純な算術演算 (加算/減算/乗算/除算) を実行できるクラスを作成することです。

私の目標は 128 ビット整数を扱うことです。

私が検討しているアプローチがいくつかあり、それらに伴う問題も考えられます。あなたが何を選択するか、そしてそれをどのように進めるかについての意見やコメントをいただければ幸いです。

アプローチ #1: 整数を 4 つの 32 ビット整数として内部的に格納する 128 ビット整数クラスを作成します。このアプローチの唯一の問題は、2 つのオペランドの個々のチャンクを操作するときにオーバーフロー/アンダーフローの問題を処理する方法がわからないことです。

アプローチ #2: これは、対処するために設計されたものと思われるため、bcmath 拡張機能を使用してください。このアプローチを採用する際の唯一の心配は、bcmath 拡張機能のスケール設定です。128 ビット整数には丸め誤差が存在するはずがないからです。それらは正確でなければなりません。また、bcmath 関数の結果を最終的にバイナリ文字列に変換できるかどうかも心配です (後でこれをいくつかの mcrypt 暗号化関数に組み込む必要があります)。

アプローチ #3: 数値をバイナリ文字列として保存します (おそらく LSB ファースト)。理論的には、この方法で任意のサイズの整数を格納できるはずです。必要なのは、2 つのバイナリ文字列に対して add/sub/mult/div を実行してバイナリ文字列の結果を生成する 4 つの基本的な算術関数を作成することだけです。これはまさに mcrypt に渡す必要がある形式なので、さらにプラスになります。これは現時点で最も有望だと思うアプローチですが、私が抱えている 1 つの問題は、PHP が (私が知っている) 個々のビットを操作する方法を提供していないことです。これをバイトサイズのチャンクに分割する必要があると思います (しゃれではありません)。その時点で、アプローチ #1 のオーバーフロー/アンダーフローの処理に関する質問が当てはまります。

役に立ちましたか？

解決

の PHP GMP 拡張機能 この方が良いでしょう。追加のボーナスとして、次のようにこれを 10 進数から 2 進数への変換に使用できます。

gmp_strval(gmp_init($n, 10), 2);

他のヒント

すでに色々あるよ クラス 利用可能 このため、独自のソリューションを作成する前に、それらを参照するとよいでしょう (実際に独自のソリューションを作成する必要がある場合)。

私の知る限りでは、bcmath 拡張機能が最適です。PHP マニュアルのデータは少し少ないですが、bcscale() 関数、または他のほとんどの bcmath 関数のオプションの 3 番目のパラメーターを使用することで、正確に必要な精度を設定できます。バイナリ文字列についてはよくわかりませんが、少しグーグルで調べてみると、pack() 関数を使用することで対処できるようです。

以下を実装しました PEMDAS苦情BC評価者 それはあなたにとって役立つかもしれません。

function BC($string, $precision = 32)
{
    if (extension_loaded('bcmath') === true)
    {
        if (is_array($string) === true)
        {
            if ((count($string = array_slice($string, 1)) == 3) && (bcscale($precision) === true))
            {
                $callback = array('^' => 'pow', '*' => 'mul', '/' => 'div', '%' => 'mod', '+' => 'add', '-' => 'sub');

                if (array_key_exists($operator = current(array_splice($string, 1, 1)), $callback) === true)
                {
                    $x = 1;
                    $result = @call_user_func_array('bc' . $callback[$operator], $string);

                    if ((strcmp('^', $operator) === 0) && (($i = fmod(array_pop($string), 1)) > 0))
                    {
                        $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string = array_shift($string), $x, $i = pow($i, -1)));

                        do
                        {
                            $x = $y;
                            $y = BC(sprintf('((%1$s * %2$s ^ (1 - %3$s)) / %3$s) - (%2$s / %3$s) + %2$s', $string, $x, $i));
                        }

                        while (BC(sprintf('%s > %s', $x, $y)));
                    }

                    if (strpos($result = bcmul($x, $result), '.') !== false)
                    {
                        $result = rtrim(rtrim($result, '0'), '.');

                        if (preg_match(sprintf('~[.][9]{%u}$~', $precision), $result) > 0)
                        {
                            $result = bcadd($result, (strncmp('-', $result, 1) === 0) ? -1 : 1, 0);
                        }

                        else if (preg_match(sprintf('~[.][0]{%u}[1]$~', $precision - 1), $result) > 0)
                        {
                            $result = bcmul($result, 1, 0);
                        }
                    }

                    return $result;
                }

                return intval(version_compare(call_user_func_array('bccomp', $string), 0, $operator));
            }

            $string = array_shift($string);
        }

        $string = str_replace(' ', '', str_ireplace('e', ' * 10 ^ ', $string));

        while (preg_match('~[(]([^()]++)[)]~', $string) > 0)
        {
            $string = preg_replace_callback('~[(]([^()]++)[)]~', __FUNCTION__, $string);
        }

        foreach (array('\^', '[\*/%]', '[\+-]', '[<>]=?|={1,2}') as $operator)
        {
            while (preg_match(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), $string) > 0)
            {
                $string = preg_replace_callback(sprintf('~(?<![0-9])(%1$s)(%2$s)(%1$s)~', '[+-]?(?:[0-9]++(?:[.][0-9]*+)?|[.][0-9]++)', $operator), __FUNCTION__, $string, 1);
            }
        }
    }

    return (preg_match('~^[+-]?[0-9]++(?:[.][0-9]++)?$~', $string) > 0) ? $string : false;
}

丸め誤差は自動的に処理され、必要な桁に精度を設定するだけです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top