Aritmética com números inteiros arbitrariamente grandes em PHP

Question

Ok, então PHP não é a melhor linguagem para lidar com números inteiros arbitrariamente grandes, considerando que ele suporta nativamente apenas números inteiros assinados de 32 bits.O que estou tentando fazer é criar uma classe que possa representar um número binário arbitrariamente grande e ser capaz de realizar operações aritméticas simples em dois deles (adicionar/subtrair/multiplicar/dividir).

Meu objetivo é lidar com números inteiros de 128 bits.

Estou analisando algumas abordagens e vejo problemas com elas.Qualquer contribuição ou comentário sobre o que você escolheria e como fazer isso seria muito apreciado.

Abordagem nº 1: Crie uma classe inteira de 128 bits que armazene seu número inteiro internamente como quatro números inteiros de 32 bits.O único problema com essa abordagem é que não tenho certeza de como lidar com problemas de overflow/underflow ao manipular partes individuais dos dois operandos.

Abordagem nº 2: Use a extensão bcmath, pois parece algo para o qual foi projetada.Minha única preocupação ao adotar essa abordagem é a configuração de escala da extensão bcmath, porque não pode haver erros de arredondamento em meus números inteiros de 128 bits;eles devem ser precisos.Também estou preocupado em poder eventualmente converter o resultado das funções bcmath em uma string binária (que mais tarde precisarei inserir em algumas funções de criptografia mcrypt).

Abordagem nº 3: Armazene os números como strings binárias (provavelmente LSB primeiro).Teoricamente, eu deveria ser capaz de armazenar números inteiros de qualquer tamanho arbitrário dessa maneira.Tudo o que eu teria que fazer é escrever as quatro funções aritméticas básicas para executar add/sub/mult/div em duas strings binárias e produzir um resultado de string binária.Este é exatamente o formato que preciso entregar ao mcrypt também, o que é uma vantagem adicional.Essa é a abordagem que considero mais promissora no momento, mas o único ponto crítico que tenho é que o PHP não me oferece nenhuma maneira de manipular os bits individuais (que eu saiba).Acredito que teria que dividi-lo em pedaços do tamanho de bytes (sem trocadilhos), momento em que minhas perguntas sobre como lidar com overflow/underflow da Abordagem nº 1 se aplicam.

Answer 1

O Extensão PHP GMP será melhor para isso.Como um bônus adicional, você pode usá-lo para fazer a conversão de decimal para binário, assim:

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

Answer 2

Já existem vários Aulas disponível para isso, você pode querer examiná-los antes de escrever sua própria solução (se de fato ainda for necessário escrever sua própria solução).

Answer 3

Pelo que eu sei, a extensão bcmath é a que você deseja.Os dados no manual do PHP são um pouco escassos, mas você pode definir a precisão exatamente como precisa usando a função bcscale() ou o terceiro parâmetro opcional na maioria das outras funções bcmath.Não tenho muita certeza sobre a questão das strings binárias, mas um pouco de pesquisa no Google me diz que você deve conseguir fazer isso usando a função pack().

Answer 4

Eu implementei o seguinte Avaliador de BC de reclamação PEMDAS que pode ser útil para você.

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

Ele lida automaticamente com erros de arredondamento, basta definir a precisão para os dígitos necessários.