"Simulieren" einer 64-Bit-Ganzzahl mit zwei 32-Bit-Ganzzahlen

Question

Ich schreibe eine sehr rechenintensive Prozedur für ein mobiles Gerät und bin auf 32-Bit-CPUs beschränkt. Im Wesentlichen führe ich Punktprodukte von riesigen Datensätzen durch (>12k vorzeichenbehaftete 16-Bit-Ganzzahlen). Fließkommaoperationen sind einfach zu langsam, also habe ich nach einer Möglichkeit gesucht, die gleiche Berechnung mit Ganzzahltypen durchzuführen. Ich stieß auf etwas namens Block Fließkomma Arithmetik (Seite 17 in dem verlinkten Dokument). Es macht einen ziemlich guten Job, aber jetzt stehe ich vor dem Problem, dass 32 Bit einfach nicht ausreichen, um die Ausgabe meiner Berechnung mit ausreichender Präzision zu speichern.

Nur um klarzustellen, der Grund, es ist nicht genug Präzision ist, dass ich drastisch Präzision jedes meiner Arrays "Elemente zu reduzieren, um eine Zahl passend in eine 32-Bit-Ganzzahl am Ende zu erhalten. Es ist die Summierung von ~16000 Dinge, die mein Ergebnis so riesig macht.

Gibt es eine Möglichkeit (ich würde gerne einen Verweis auf einen Artikel oder ein Tutorial), um zwei 32-Bit-Ganzzahlen als höchstwertiges Wort und niedrigstwertiges Wort zu verwenden et Arithmetik auf ihnen definieren (+, -, *, /), um Daten effizient zu verarbeiten? Gibt es vielleicht auch bessere Möglichkeiten, solche Dinge zu tun? Gibt es ein Problem mit diesem Ansatz? Ich bin ziemlich flexibel, was die von mir verwendete Programmiersprache angeht. Ich würde C/C++ bevorzugen, aber Java geht auch. Ich bin sicher, jemand hat das schon mal gemacht.

Answer 1

Ich bin mir ziemlich sicher, dass die JVM eine 64-Bit-Arithmetik unterstützen muss long Typ, und wenn die Plattform ihn nicht unterstützt, muss die VM ihn emulieren. Wenn Sie es sich jedoch nicht leisten können, den float für Leistungsprobleme, dann wird eine JVM Sie wahrscheinlich zerstören.

Die meisten C- und C++-Implementierungen bieten emulierte 64-Bit-Arithmetik für 32-Bit-Ziele - ich weiß, dass MSVC und GCC dies tun. Sie sollten sich jedoch bewusst sein, dass es sich um viele Integer-Befehle, um einen einzigen Gleitkomma-Befehl zu sparen. Sie sollten in Betracht ziehen, dass die Spezifikationen für dieses Programm unangemessen sind oder dass Sie vielleicht an anderer Stelle Leistung freisetzen könnten.

Answer 2

Ja, verwenden Sie einfach 64-Bit-Ganzzahlen:

long val; // Java

#include <stdint.h>
int64_t val; // C

Answer 3

Es gibt eine Liste der Bibliotheken auf der Wikipedia-Seite über Arbitrary Precision Arithmetic. Vielleicht hilft Ihnen etwas von dort weiter?

Answer 4

Wenn Sie Java verwenden können, lautet die kurze Antwort: Verwenden Sie Java-Longs. Der Java-Standard definiert einen Long als 64 Bit. Jede JVM sollte dies implementieren oder sie ist nicht konform mit dem Standard. Es ist nicht erforderlich, dass die CPU 64-Bit-Arithmetik unterstützt. Wenn sie nicht nativ unterstützt wird, sollte eine JVM sie mit Software implementieren.

Wenn Sie wirklich ein verkrüppeltes Java haben, das keine Long-Werte unterstützt, verwenden Sie BigInteger. Damit können Sie ganze Zahlen beliebiger Größe verarbeiten.

Answer 5

Apropos C/C++.
Jeder normale Compiler würde den Typ "long long" als 64-Bit-Integer mit allen normalen Rechenoperationen unterstützen.
In Kombination mit -O3 hat es sehr gute Chancen, den bestmöglichen Code für 64-Bit-Arithemtic auf Ihrer Plattform auszugeben.