Arithmetik mit willkürlich großen Ganzzahlen in PHP

Question

Ok, so PHP ist nicht die beste Sprache für den Umgang mit beliebig großen Ganzzahlen in, wenn man bedenkt, dass es nur nativ unterstützt 32-Bit signierte Ganzzahlen. Was ich versuche zu tun, obwohl ist eine Klasse zu erstellen, die eine beliebig große Binärzahl darstellen könnte und in der Lage, einfache arithmetische Operationen auf zwei von ihnen (addieren/Subtrahieren/Multiplizieren/Dividieren) durchzuführen.

Mein Ziel ist der Umgang mit 128-Bit-Ganzzahlen.

Es gibt mehrere Ansätze, die ich in Betracht ziehe, und ich sehe Probleme mit ihnen. Jede Anregung oder jeder Kommentar dazu, was Sie wählen würden und wie Sie dabei vorgehen würden, wäre sehr willkommen.

Ansatz #1: Erstellen Sie eine 128-Bit-Ganzzahlklasse, die ihre Ganzzahl intern als vier 32-Bit-Ganzzahlen speichert. Das einzige Problem bei diesem Ansatz ist, dass ich nicht sicher bin, wie man mit Über- und Unterlaufproblemen umgeht, wenn man einzelne Teile der beiden Operanden manipuliert.

Ansatz #2: Verwenden Sie die bcmath-Erweiterung, da sie für diese Aufgabe konzipiert wurde. Meine einzige Sorge bei diesem Ansatz ist die Skaleneinstellung der bcmath-Erweiterung, da es bei meinen 128-Bit-Ganzzahlen keine Rundungsfehler geben darf; sie müssen präzise sein. Ich mache mir auch Sorgen darüber, ob ich das Ergebnis der bcmath-Funktionen in eine binäre Zeichenkette umwandeln kann (die ich später in einige mcrypt-Verschlüsselungsfunktionen einfügen muss).

Ansatz #3: Speichern Sie die Zahlen als binäre Zeichenketten (wahrscheinlich zuerst das LSB). Theoretisch sollte ich in der Lage sein, ganze Zahlen beliebiger Größe auf diese Weise zu speichern. Alles, was ich tun müsste, ist, die vier grundlegenden arithmetischen Funktionen zu schreiben, um zwei binäre Zeichenfolgen zu addieren/sub/mult/divieren und ein binäres Zeichenfolgenergebnis zu erzeugen. Das ist genau das Format, das ich auch an mcrypt übergeben muss, das ist also ein zusätzliches Plus. Das ist der Ansatz, der meiner Meinung nach im Moment am vielversprechendsten ist, aber der einzige Knackpunkt ist, dass PHP mir keine Möglichkeit bietet, die einzelnen Bits zu manipulieren (soweit ich weiß). Ich glaube, ich müsste sie in bytegroße Stücke aufteilen (kein Wortspiel beabsichtigt), wobei meine Fragen zum Umgang mit Über- und Unterlauf aus Ansatz 1 zutreffen.

Answer 1

El PHP GMP-Erweiterung besser geeignet sein wird. Als zusätzlichen Bonus können Sie es verwenden, um Ihre Dezimal-zu-Binär-Konvertierung, wie so zu tun:

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

Answer 2

Es gibt bereits verschiedene Klassen verfügbar Sie sollten sich diese also ansehen, bevor Sie Ihre eigene Lösung schreiben (falls Sie überhaupt noch eine eigene Lösung schreiben müssen).

Answer 3

Soweit ich das beurteilen kann, ist die bcmath-Erweiterung diejenige, die Sie brauchen. Die Angaben im PHP-Handbuch sind etwas spärlich, aber man sollte in der Lage sein, die Genauigkeit genau so einzustellen, wie man sie braucht, indem man die Funktion bcscale() oder den optionalen dritten Parameter in den meisten anderen bcmath-Funktionen verwendet. Bei der Sache mit den binären Zeichenketten bin ich mir nicht ganz sicher, aber ein bisschen Googeln sagt mir, dass man das mit der pack()-Funktion hinbekommen sollte.

Answer 4

Ich habe Folgendes umgesetzt PEMDAS-Beschwerde BC-Bewerter die für Sie nützlich sein könnten.

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

Rundungsfehler werden automatisch ausgeglichen, stellen Sie einfach die Genauigkeit auf die von Ihnen benötigten Stellen ein.