Arithmétique avec des entiers arbitrairement grands en PHP

Question

Ok, donc PHP n'est pas le meilleur langage pour traiter des entiers arbitrairement grands, étant donné qu'il ne prend en charge nativement que les entiers signés 32 bits.Ce que j'essaie de faire, c'est de créer une classe qui pourrait représenter un nombre binaire arbitrairement grand et être capable d'effectuer des opérations arithmétiques simples sur deux d'entre eux (ajouter/soustraire/multiplier/diviser).

Ma cible concerne des entiers de 128 bits.

Il y a quelques approches que j'examine et des problèmes que je vois avec elles.Toute contribution ou commentaire sur ce que vous choisiriez et comment vous pourriez procéder serait grandement apprécié.

Approche n°1 : Créez une classe entière de 128 bits qui stocke son entier en interne sous forme de quatre entiers de 32 bits.Le seul problème avec cette approche est que je ne sais pas comment gérer les problèmes de débordement/sous-débordement lors de la manipulation de morceaux individuels des deux opérandes.

Approche n°2 : Utilisez l'extension bcmath, car cela ressemble à quelque chose pour lequel elle a été conçue.Mon seul souci en adoptant cette approche est le paramètre d'échelle de l'extension bcmath, car il ne peut y avoir d'erreur d'arrondi dans mes entiers de 128 bits ;ils doivent être précis.Je crains également de pouvoir éventuellement convertir le résultat des fonctions bcmath en une chaîne binaire (que je devrai plus tard insérer dans certaines fonctions de cryptage mcrypt).

Approche n°3 : Stockez les nombres sous forme de chaînes binaires (probablement LSB en premier).Théoriquement, je devrais pouvoir stocker de cette façon des entiers de n’importe quelle taille arbitraire.Tout ce que j'aurais à faire est d'écrire les quatre fonctions arithmétiques de base pour effectuer add/sub/mult/div sur deux chaînes binaires et produire un résultat de chaîne binaire.C'est exactement le format que je dois également transmettre à mcrypt, c'est donc un avantage supplémentaire.C'est l'approche qui, à mon avis, est la plus prometteuse pour le moment, mais le seul point de friction que j'ai est que PHP ne m'offre aucun moyen de manipuler les bits individuels (à ma connaissance).Je pense que je devrais le diviser en morceaux de la taille d'un octet (sans jeu de mots), auquel cas mes questions sur la gestion du débordement/sous-débordement de l'approche n°1 s'appliquent.

Answer 1

Le Extension PHP GMP ce sera mieux pour ça.En prime, vous pouvez l'utiliser pour effectuer votre conversion décimale en binaire, comme ceci :

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

Answer 2

Il existe déjà divers Des classes disponible pour cela, vous souhaiterez peut-être les consulter avant d'écrire votre propre solution (si l'écriture de votre propre solution est encore nécessaire).

Answer 3

Pour autant que je sache, l'extension bcmath est celle que vous souhaiterez.Les données contenues dans le manuel PHP sont un peu rares, mais vous pouvez définir la précision exactement ce dont vous avez besoin en utilisant la fonction bcscale() ou le troisième paramètre facultatif dans la plupart des autres fonctions bcmath.Je ne suis pas trop sûr du problème des chaînes binaires, mais un peu de recherche sur Google me dit que vous devriez pouvoir le faire en utilisant la fonction pack().

Answer 4

J'ai implémenté ce qui suit Évaluateur des plaintes PEMDAS BC qui pourra vous être utile.

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;
}

Il traite automatiquement les erreurs d'arrondi, il suffit de définir la précision sur les chiffres dont vous avez besoin.