Die beste plattformübergreifende (tragbare) Mathematikbibliothek mit beliebiger Genauigkeit [geschlossen]

81

Ich suche eine gute Mathematikbibliothek mit beliebiger Genauigkeit in C oder C ++. Könnten Sie mir bitte einige Ratschläge / Vorschläge geben?

Die Hauptanforderungen:

  1. Es MUSS beliebig große ganze Zahlen verarbeiten (mein Hauptinteresse gilt ganzen Zahlen). Wenn Sie nicht wissen, was das Wort willkürlich groß bedeutet, stellen Sie sich so etwas wie 100000 vor! (die Fakultät von 100000).
  2. Die Genauigkeit MUSS NICHT während der Bibliotheksinitialisierung / Objekterstellung angegeben werden. Die Genauigkeit sollte NUR durch die verfügbaren Ressourcen des Systems eingeschränkt werden.
  3. Es sollte um die volle Leistung der Plattform nutzen und soll „kleine“ Zahlen nativ verarbeiten. Das bedeutet, dass auf einer 64-Bit-Plattform für die Berechnung von 2 ^ 33 + 2 ^ 32 die verfügbaren 64-Bit-CPU-Anweisungen verwendet werden sollten. Die Bibliothek sollte dies NICHT auf die gleiche Weise berechnen wie bei 2 ^ 66 + 2 ^ 65 auf derselben Plattform.
  4. Es MUSS Addition (+), Subtraktion (-), Multiplikation (*), Ganzzahldivision (/), Rest (%), Potenz (**), Inkrement (++), Dekrement (-), gcd () verarbeiten. , Fakultät () und andere gängige ganzzahlige arithmetische Berechnungen effizient. Die Fähigkeit, Funktionen wie sqrt () (Quadratwurzel), log () (Logarithmus) zu verarbeiten, die keine ganzzahligen Ergebnisse liefern, ist ein Plus. Die Fähigkeit, symbolische Berechnungen durchzuführen, ist noch besser.

Folgendes habe ich bisher gefunden:

  1. Java ‚s BigInteger und BigDecimal Klasse: Ich habe diese bisher verwenden. Ich habe den Quellcode gelesen, aber ich verstehe die Mathematik darunter nicht. Es kann auf Theorien / Algorithmen basieren, die ich nie gelernt habe.
  2. Der eingebaute Integer-Typ oder die Kernbibliotheken von bc / Python / Ruby / Haskell / Lisp / Erlang / OCaml / PHP / einigen anderen Sprachen: Einige davon habe ich jemals verwendet, aber ich habe keine Ahnung, welche Bibliothek sie verwenden oder welche Art von Implementierung sie verwenden.

Was ich schon gewusst habe:

  1. Verwenden Sie ein Zeichen als Dezimalstelle und ein Zeichen * als Dezimalzeichenfolge und berechnen Sie die Ziffern mit einer for-Schleife.
  2. Verwenden Sie ein int (oder ein long int oder ein long long ) als grundlegende "Einheit" und ein Array davon als beliebige lange Ganzzahl und führen Sie Berechnungen für die Elemente mithilfe einer for-Schleife durch.
  3. Verwenden eines Integer-Typs zum Speichern einer Dezimalstelle (oder einiger Stellen) als BCD (Binary-Coded Decimal) .
  4. Booths Multiplikationsalgorithmus

Was ich nicht weiß:

  1. Drucken des oben genannten binären Arrays in Dezimalzahl ohne Verwendung naiver Methoden. Beispiel für eine naive Methode: (1) Addieren Sie die Bits vom niedrigsten zum höchsten: 1, 2, 4, 8, 16, 32, ... (2) Verwenden Sie eine oben erwähnte Zeichenfolge * , um die Zwischenergebnisse der Dezimalstellen zu speichern ).

Was ich schätze:

  1. Gute Vergleiche zu GMP , MPFR , decNumber (oder anderen Bibliotheken, die Ihrer Meinung nach gut sind).
  2. Gute Vorschläge zu Büchern / Artikeln, die ich lesen sollte. Beispielsweise ist eine Darstellung mit Abbildungen zur Funktionsweise eines nicht naiven Konvertierungsalgorithmus von Binär zu Dezimal gut. Der Artikel "Binär-Dezimal-Umwandlung in begrenzter Präzision" von Douglas W. Jones ist ein Beispiel für einen guten Artikel.
  3. Irgendeine Hilfe.

Bitte beantworten Sie diese Frage NICHT , wenn:

  1. Sie denken, dass die Verwendung eines Double (oder eines Long Double oder eines Long Long Double ) dieses Problem leicht lösen kann. Wenn Sie dies glauben, bedeutet dies, dass Sie das zur Diskussion stehende Problem nicht verstehen.
c++ c biginteger bigdecimal gmp Siu Ching Pong -Asuka Kenji-
quelle
3
Soweit ich sehen kann, scheint GMP eine gute Bibliothek zu sein. Ich frage mich, warum die Autoren von Python / Haskell / Erlang / etc das Rad neu erfinden müssen. Wenn GMP so gut ist, warum sollten Sie sich nicht darauf verlassen? Die GPL / LGPL-Lizenz kann eines der Probleme sein, aber gibt es trotzdem (und auch im Rundungsmodus) andere Nachteile von GMP? Ist die integrierte Ganzzahl von Python / Haskell / Erlang / einer Kryptografiebibliothek schneller als GMP? Wenn ja, möchte ich es extrahieren und verwenden, wenn die Lizenz dies zulässt.
Siu Ching Pong -Asuka Kenji-
Ich habe einen schönen Artikel von Douglas W. Jones unter cs.uiowa.edu/~jones/bcd/decimal.html gefunden . Der Artikel beschreibt eine Methode zum Konvertieren einer 16-Bit-Ganzzahl in eine Dezimaldarstellung unter Verwendung von nur 8-Bit-Ganzzahlarithmetik. Die Idee ist, die 16-Bit-Zahl in 4 Halbbytes aufzuteilen, die jeweils eine Basis-16 "Ziffer" darstellen. Die Ziffer 0 (n0) steht also für x1, n1 => x16, n2 => x256, n3 => x4096. Dann ist es offensichtlich, dass die Ziffer 0 der Dezimalzahl (d0) die Ziffer 0 des Ergebnisses von n0 * 1 + n1 * 6 + n2 * 6 + n3 * 6 ist. Durch ordnungsgemäße Behandlung des Übertrags können d1 bis d4 auch berechnet werden.
Siu Ching Pong -Asuka Kenji-
Soweit ich mir vorstellen konnte, konnte Douglas 'obige Idee jedoch nicht auf beliebig lange binäre Ganzzahlen erweitert werden. Dies liegt daran, dass die Zahlen 1 (16 ^ 0), 16 (16 ^ 1), 256 (16 ^ 2) und 4096 (16 ^ 3) vorberechnet sind. Das Problem wird dann, wie 16 ^ n in Dezimalzahlen für beliebig große n dargestellt werden.
Siu Ching Pong -Asuka Kenji-

Antworten:

24

GMP ist die beliebte Wahl. Squeak Smalltalk hat eine sehr schöne Bibliothek, die jedoch in Smalltalk geschrieben ist.

Sie haben nach relevanten Büchern oder Artikeln gefragt. Der schwierige Teil von Bignums ist die lange Teilung. Ich empfehle Per Brinch Hansens Artikel Multiple-Length Division Revisited: Eine Tour durch das Minenfeld .

Norman Ramsey
quelle
Vielen Dank für Ihren Link zum Papier! Ja, ich stimme zu, dass die Teilung der schwierigste Teil ist. Ich wusste schon vor langer Zeit, wie man mit "Papier-und-Bleistift-Methoden" von Hand dividiert :-), und daher kann dieselbe Methode auf eine Dezimalzeichenfolge char *(die jeweils chareine Dezimalstelle darstellt) oder eine int *BCD-Zeichenfolge ( jeweils eine Dezimalstelle) angewendet werden. jeweils int4/8/16 BCD-Ziffern). Ich frage mich jedoch, ob Bibliotheken auf Produktionsebene die "Papier-Bleistift-Methode" nachahmen, da sie zu langsam ist.
Siu Ching Pong -Asuka Kenji-
Um zu sehen, warum, stellen wir uns vor, wie es läuft 100,000,000,000,000,000 / 333,333,333,333: Der erste Schritt ist der Vergleich 100,000,000,000mit 333,333,333,333. Da ersteres kleiner als letzteres ist, geht die Berechnung einfach zur nächsten Ziffer über. Der zweite Schritt besteht darin, den Quotienten von zu finden 1,000,000,000,000 / 333,333,333,333. Dies beinhaltet entweder eine Trial-and-Error-Multiplikation von 333,333,333,333 * 1(und * 2, * 3und * 4) oder aufeinanderfolgende Subtraktionen in einer Schleife. Sehen Sie, wie langsam es ist? Ich glaube, dass effizientere Algorithmen existieren.
Siu Ching Pong -Asuka Kenji-
3
@Sui: Brinch Hanson zeigt, wie Sie die Trial-and-Error-Methode auf höchstens zwei Versuche reduzieren können. Es ist wirklich sehr beeindruckend.
Norman Ramsey
Okay, lassen Sie mich das Papier genauer betrachten. Danke dir!
Siu Ching Pong -Asuka Kenji-
1
Ich bin mir nicht sicher, wo Sie Ihre Lösung gefunden haben oder in welchem ​​Format Sie Ziffern gespeichert haben, aber das COMP-3-Nybble-Format von COBOL ist viel besser zu handhaben, da es kompakter ist und jeweils 4 Bits eine 0-9 speichert value, AND, Sie müssen hex 30 nicht vom ASCII-Zeichenwert subtrahieren, um eine verwendbare Ziffer zu erhalten.
13

Insgesamt ist die schnellste willkürliche Präzisionsbibliothek für allgemeine Zwecke GMP . Wenn Sie mit Gleitkommawerten arbeiten möchten, sehen Sie sich die MPFR- Bibliothek an. MPFR basiert auf GMP.

In Bezug auf die native Unterstützung für willkürliche Genauigkeit in anderen Sprachen verwendet Python aus Gründen der Lizenz, der Codegröße und der Codeportabilität eine eigene Implementierung. Mit dem GMPY- Modul kann Python auf die GMP-Bibliothek zugreifen.

casevh

casevh
quelle
Danke für Ihre Antwort! Sie haben "Code-Portabilität" erwähnt. Könnten Sie bitte erklären, wo das Problem liegt? Ich dachte, dass GMP portabel ist und auf wichtigen Plattformen unterstützt wird ...
Siu Ching Pong -Asuka Kenji-
2
"Code-Portabilität" ist nicht dasselbe wie "auf wichtigen Plattformen unterstützt". Python verwendet eine einfache Implementierung, die nur sehr wenige Annahmen über das Verhalten des C-Compilers macht, sodass derselbe Code auf fast jedem C-Compiler kompiliert werden kann. GMP verwendet mehr Code (C und hochgradig optimierte Assembly), der GMP schneller macht, aber auch mehr Annahmen über das Verhalten des C-Compilers und Assemblers macht. Beispielsweise wird GMP von den Microsoft Visual Studio-Compilern nicht gut unterstützt. Es gibt eine GMP-Abzweigung namens MPIR (www.mpir.org), die die Compiler von Microsoft unterstützt.
casevh
Aha. Das bedeutet, dass die Python-Implementierung eher ANSI C ähnelt, während die GMP-Implementierung __asm-Tricks verwendet ... Vielen Dank für Ihre Erklärungen.
Siu Ching Pong -Asuka Kenji-
8

Siehe http://ttmath.org

Kleine Nur-Header-Bibliothek mit Vorlagen für den kostenlosen persönlichen und kommerziellen Gebrauch.

Andrey Syrokomskiy
quelle
Hallo! Dies ist eine benutzerfreundliche Bibliothek, die anscheinend die CPU-Leistung nutzt und etwas C ++ - Vorlagenmagie verwendet, um den Job abzuschließen. Tolle Bibliothek! +1 für dich!
Siu Ching Pong -Asuka Kenji-
Ja, und es hat eine zulässige BSD-Lizenz ohne Copyleft.
Plasmacel
Auf der obigen Seite: "Wie groß die Werte sein können, wird zur Kompilierungszeit festgelegt." - Das entspricht also nicht den Anforderungen.
Osxdirk
7

Ich habe selbst keine Arithmetikbibliotheken mit willkürlicher Präzision miteinander verglichen, aber Leute, die sich mehr oder weniger einheitlich für GMP entschieden haben. Für das, was es wert ist, werden die willkürlichen Präzisions-Ganzzahlen in GHC Haskell und GNU Guile Scheme beide mit GMP implementiert, und die schnellste Implementierung des Pidigits-Benchmarks für das Sprach-Shootout basiert auf GMP.

Richard Barrell
quelle
Vielen Dank! ^ ___ ^ Schöne Information!
Siu Ching Pong -Asuka Kenji-
4

Was ist mit Pari? Es basiert auf Top-GMP und bietet alle anderen Extras zu Operationen der Zahlentheorie, die Sie jemals benötigen werden (und viele symbolische Berechnungsmaterialien).

http://pari.math.u-bordeaux.fr/

fortran
quelle
Hallo fortran (!), Es sieht gut aus! Danke für Ihre Information!
Siu Ching Pong -Asuka Kenji-
Gern geschehen :-) Auch mit Pari können Sie mit GP schnelle Prototypen rollen und, wenn Sie zufrieden sind, die optimierte C-Version schreiben (und ich denke, es wird auch ein GP-> C-Compiler
mitgeliefert