Motivation
Motivation
Das auf dieser Seite präsentierte Material ist aufgrund meines Interesses an der Zahlentheorie entstanden. Es ist ein Forschungsgebiet woher vielen klassischen Algorithmen stammen, die man ohne Verzögerung implementieren möge, um ihre Wirkungsmagie zu beobachten. Aber leider, sobald die Sachen fesselnd werden, gelangt man an die Grenzen, die das Gerät auferlegt:
‘[..] Die Anzahl von Symbole welche der Rechner in einem Moment beachten kann, ist beschrankt. Wenn er wünscht Mehre zu beachten, muß er aufeinander folgenden Operationen verwenden.’ Alan Turing, Auf berechenbaren Zahlen [..], 1936.
Deshalb brauchte ich eine kleine Programmbibliothek, um die Grundrechenarten in Bezug auf solche ‘aufeinander folgenden Operationen’ umzuformulieren. Anstatt eine von den vielen existierenden Langzahlbibliotheken zu meinem Zweck anzupassen, schien es ausreichend um vorne anzufangen, und nur die notwendigsten Operationen durchzuführen.
Das Projekt wuchs unter eigenem Antrieb, einigen sehr nützlichen Funktionen werden zugefügt, aber unter Beibehalten des anfänglichen, einfachen Entwurfs. Die Bibliothek ist in reinem QuickBasic geschrieben, ergänzt mit Assembly-Schieberoutinen.
Dateikopf der Langzahl-Bibliothek' ************************************************************************** 'Thema: Einfügeeinheit-Datei für eine Langzahl BASIC-Programmbibliothek. 'Autor: Sjoerd.J.Schaper 'Datum: 02-02-2004 'Code : QuickBasic, PDS, VBdos ' **************************************************************************
(Siehe Download-Seite für Visual Basic/Win, FreeBasic und XBasic Versionen.)
' --------------------------------------------------------------------------
' Dimensionen von Zahlen-Array n(uj, ui) ( nur für die $STATIC-Version )
' --------------------------------------------------------------------------
'CONST ui = 5, uj = 1418 ' langes Lib
CONST ui = 35, uj = 402 ' medium Lib
'CONST ui = 172, uj = 91 ' weites Lib
' --------------------------------------------------------------------------
' globale Konstanten
' --------------------------------------------------------------------------
CONST LB = 15, MB = 32768, MH = 16384 ' binär Speicherbasen
CONST M1 = 32767, M2 = 1073709056 ' Masken MB - 1, (MB - 1)* MB
CONST LD = 8, MD = 100000000 ' dezimale ein/aus Basen, MY < MB
CONST MY = 10000&, Fx = 2147483629 ' feste Limit
CONST t0 = -1, t1 = -2 ' Zeigern zu Wechsel-Spalten
CONST t2 = -3, t3 = -4
'
' **************************************************************************
' Initialisierung und Zuweisung
' **************************************************************************
'Die LargeInt-Klasse wird mit einem 'LargeInit(Größe%, Name$)' Aufruf am
'Modul-Niveau initialisiert. Für alle Langzahlen, die Sie verwenden wollen,
'sollen Sie konstante Indizes angeben ('CONST p = 0, q = 1, ..'), so daß
'jede Zahl mit einem eindeutigen Spaltenzeiger verbunden wird. Diese
'Zeigern werden dann den Prozeduren übergeben. Sie sollen keinen Funktions-
'Aufrufe mit gleichen Zeigern machen ('Squ p, p'), und sich hüten für
'Doppelverweisungen, weil diese Programmabstürze verursachen.
'
'In nachfolgenden Prototypen,
'sind die Buchstaben p, q, r, d, m 16-Bit Zeigern zur Langzahlen,
'die Variablen a, k, sw 16-Bit Ganzzahlen; c ist eine 32-Bit Ganzzahl;
'g ist eine Zahlzeichenkette; f und h sind irgendwelche Zeichenketten.
'
DECLARE FUNCTION LargeInit% (k AS INTEGER, f AS STRING)
'Initialisiert die Zahlen-Arrays, öffnet die Primzahltabelle und Logdatei.
'Auf zu rufen mit k = Anzahl der Largeint-Zahlen in ihrem Programm
'(k <= ui in der $STATIC-Version) und String f = Programm-Name. Wenn f = ""
'wird keine Logdatei geöffnet. Ruckgabewert ist die Largeint-Wortlänge.
'Die Maximallänge einer Dezimalzahl ist annäherend 4.51 * Wortlänge.
'
DECLARE SUB Letf (p AS INTEGER, c AS LONG)
'Weist Langzahl p den Doppelwortwert c zu.
'
DECLARE SUB Rndf (p AS INTEGER, k AS INTEGER)
'Weist p eine positive Zufallszahl mit Bitlänge Abs(k) zu.
'
DECLARE SUB Term ()
'Schließen der Primzahltabelle und Logdatei.
'
' **************************************************************************
' Funktionen zur Konvertierung
' **************************************************************************
DECLARE SUB Readst (p AS INTEGER, g AS STRING)
'Konvertiert die dezimale Zahlzeichenkette g in Langzahl p.
'Außer einem vorgesetzten Minuszeichen, gibt es keine Überprüfung
'auf Nichtziffer-Charaktere in der Zeichenkette.
'
DECLARE FUNCTION Decf% (p AS INTEGER)
'Konvertiert Langzahl p zur Basis MD in der Reihe ln().
'Gibt die Bytelänge von p zurück. An zu rufen bevor CnvSt.
'
DECLARE SUB CnvSt (g AS STRING)
'Konvertiert eine Zahl der Basis MD in eine Zahlzeichenkette.
'Rufen Sie erst k = Decf(p) auf, legen Sie einen Zeichenkettenpuffer
'g = STRING$(k, "0") an, und übergeben Sie diesen am CnvSt.
'
DECLARE FUNCTION Logf# (p AS INTEGER)
'Natürlicher Logarithmus von Langzahl Abs(p) in doppelte Genauigkeit.
'
DECLARE SUB Ratdec (g AS STRING, p AS INTEGER, q AS INTEGER)
'Gibt die Dezimaldarstellung von Zahlenverhältnis p / q in [0, 1)
'in Zahlzeichenkette g aus.
'
' **************************************************************************
' Datenausgabe
' **************************************************************************
DECLARE SUB Printf (f AS STRING, g AS STRING, h AS STRING, sw AS INTEGER)
'Druckt die Zeichenketten f, g und h zum Bildschirm und der Logdatei.
'Wenn sw = 1 wird eine CrLf, sw = 2 auch die Länge von g ausgegeben.
'
DECLARE SUB Printn (p AS INTEGER, f AS STRING, h AS STRING, sw AS INTEGER)
'Druckt Langzahl p ab mit Vorspann f und Schwanzende h, verwendet Printf.
'
DECLARE SUB Printr (p AS INTEGER, q AS INTEGER, r AS INTEGER, f AS STRING, _
h AS STRING)
'Druckt die Dezimaldarstellung von Zahlenverhältnis p / q ab,
'die Dezimallänge wird in der Zahl r übergeben mit 'Setl r, len'.
'
DECLARE SUB Prints (f AS STRING, sw AS INTEGER)
'Druckt die Zeichenkette f ab,
'setzen Sie switch = 1 um ein CrLf an zu heften, switch = 2 für Zweier.
'
' **************************************************************************
' grundlegende Rechenfunktionen
' **************************************************************************
DECLARE FUNCTION Absf% (p AS INTEGER)
'Setzt das Vorzeichen von Zahl p auf 1, gibt den jetzigen Wert zurück.
'
DECLARE SUB Add (p AS INTEGER, q AS INTEGER)
'Addiert p und q, das Ergebnis steht in p.
'
DECLARE SUB Chs (p AS INTEGER)
'Veränderung des Vorzeichens von p.
'
DECLARE SUB Dcr (p AS INTEGER, a AS INTEGER)
'Vermindert Langzahl p mit dem positiven Kleinwert a.
'
DECLARE SUB Divd (p AS INTEGER, d AS INTEGER, q AS INTEGER)
'Dividiert p und d. Der Quotient steht in q, der Rest in p.
'
DECLARE SUB Inc (p AS INTEGER, a AS INTEGER)
'Erhöht Langzahl p mit dem positiven Kleinwert a.
'
DECLARE SUB Mult (p AS INTEGER, q AS INTEGER, r AS INTEGER)
'Multipliziert p und q. Das Ergebnis steht standardmäßig in p,
' 'Swp p, r' setzt es in r.
'
DECLARE SUB Powr (p AS INTEGER, k AS INTEGER)
'Potenziert Basis p mit Hochzahl k. Das Ergebnis steht in p.
'
DECLARE SUB Squ (p AS INTEGER, q AS INTEGER)
'Gibt das Quadrat von p in q zurück.
'
DECLARE SUB Subt (p AS INTEGER, q AS INTEGER)
'Subtrahiert q von p, das Ergebnis steht in p.
'Um p zu erhalten, verwenden Sie 'Subt q, p: Chs q'.
'
' **************************************************************************
' Vergleich und Kopieren
' **************************************************************************
DECLARE FUNCTION Cmp% (p AS INTEGER, q AS INTEGER)
'Vergleicht p und q:
'das Resultat ist -1 wenn p < q, 0 wenn p = q, und 1 wenn p > q.
'
DECLARE FUNCTION Isf% (p AS INTEGER, a AS INTEGER)
'Boolesch: überprüft ob Langzahl p den Kleinwert a gleich ist.
'
DECLARE FUNCTION Ismin1% (p AS INTEGER, m AS INTEGER)
'Boolesch: überprüft ob p = m - 1
'
DECLARE SUB Copyf (p AS INTEGER, q AS INTEGER)
'Kopiert Zahl p zu q.
'
DECLARE SUB Swp (p AS INTEGER, q AS INTEGER)
'Tauscht Zahlen p und q.
'
' **************************************************************************
' Bit-Verarbeitung
' **************************************************************************
DECLARE FUNCTION Bitl% (p AS INTEGER)
'Gibt die Bitlänge von Langzahl p zurück.
'
DECLARE SUB Boolf (p AS INTEGER, q AS INTEGER, k AS INTEGER)
'Bitweise boolesche Funktionen ergeben p:= q Op(k) p,
'mit Op(1) = AND, Op(2) = XOR, Op(3) = OR.
'Falls k = 0 wird NOT p zurückgegeben und q ignoriert.
'Jeweils bleibt das Vorzeichen von p unverändert.
'
DECLARE SUB Lsft (p AS INTEGER, k AS INTEGER)
'Langzahl p wird um k Bits nach links verschoben.
'
DECLARE SUB Rsft (p AS INTEGER, k AS INTEGER)
'Langzahl p wird um k Bits nach rechts verschoben.
'
' **************************************************************************
' Modular-Arithmetik
' **************************************************************************
DECLARE SUB Modbal (p AS INTEGER, m AS INTEGER)
'Gibt den ausgeglichenen Rest p Modul m: Abs(p) <= m \ 2.
'
DECLARE SUB Moddiv (p AS INTEGER, m AS INTEGER)
'Gibt den positiven Rest p Modul m.
'
DECLARE SUB Modmlt (p AS INTEGER, q AS INTEGER, m AS INTEGER)
'Multipliziert p und q, reduziert dann Modul m. Das Ergebnis steht in p.
'
DECLARE SUB Modpwr (p AS INTEGER, q AS INTEGER, m AS INTEGER)
'Modulares Potenzieren: Basis p, Hochzahl q, Modul m.
'Das Ergebnis steht in p.
'
DECLARE SUB Modsqu (p AS INTEGER, m AS INTEGER)
'Quadriert p, reduziert dann Modul m.
'
DECLARE FUNCTION Mp2% (p AS INTEGER, a AS INTEGER)
'Gibt Langzahl p Modul eine Einwortwert Potenz-von-Zwei zurück.
'
' **************************************************************************
' zahlentheoretische Funktionen
' **************************************************************************
DECLARE SUB Bezout (p AS INTEGER, q AS INTEGER, d AS INTEGER)
'Lösung der diophantische Gleichung px + qy = ggT(p, q).
'Positive x wird in p, y in q und ggT(p, q) in d zurückgegeben.
'
DECLARE SUB Euclid (p AS INTEGER, q AS INTEGER, d AS INTEGER)
'Der erweiterte Euklidische Algorithmus errechnet
'p^ -1 Mod q in p, q/ ggT in q und ggT(p, q) in d.
'
DECLARE SUB Fctl (p AS INTEGER, a AS INTEGER)
'Berechnet Fakultät a(a-1)···2·1 in Langzahl p.
'
DECLARE SUB Gcd (p AS INTEGER, q AS INTEGER, d AS INTEGER)
'Gibt der größte gemeinsame Teiler(p, q) in d zurück.
'
DECLARE FUNCTION IsPPrm% (p AS INTEGER, d AS INTEGER, k AS INTEGER)
'Boolesch: überprüft mit dem Test des Millers-Rabin ob p eine
'wahrscheinliche Primzahl ist. k ist die Anzahl des zu verwenden Zeuges.
'Falls es einen kleinen Teiler gibt, wird er in d zurückgegeben.
'
DECLARE FUNCTION IsSqr% (p AS INTEGER, q AS INTEGER)
'Boolesch: überprüft ob p ein Quadrat ist. Wenn wahr, ist die Wurzel in q.
'
DECLARE SUB Isqrt (p AS INTEGER, q AS INTEGER)
'Errechnet mit des Heronschen Algorithmus die Ganzzahl-Quadratwurzel von p,
'und gibt sie in q zurück.
'
DECLARE FUNCTION Kronec% (p AS INTEGER, q AS INTEGER, d AS INTEGER)
'Das quadratische Restsymbol Kroneckers (p/q) = 0, 1, oder -1.
'Gibt einen ungraden ggT(p, q) in d zurück, und 2 wenn er graden ist.
'
DECLARE SUB Lcm (p AS INTEGER, q AS INTEGER, d AS INTEGER)
'Gibt das kleinste gemeinsame Vielfache(p, q) in d zurück.
'
DECLARE FUNCTION Nxtprm& (sw AS INTEGER)
'Schleift durch Tabelle PrimFlgs.bin. Initiieren mit sw = 0 und
'Primzahl fortschreiben mit sw <> 0 bei jedem folgenden Aufruf.
'
DECLARE SUB Triald (q AS INTEGER, p AS INTEGER, c AS LONG)
'Probedivision von p bis Schranke c. Primfaktoren u/Exponenten werden
'in die Liste {q} gespeichert, der Restfaktor wird in p zurückgegeben.
'
' **************************************************************************
' direkter Zugrif
' **************************************************************************
DECLARE SUB EnQ (q AS INTEGER, p AS INTEGER, a AS INTEGER)
'Speichert kleine p und Einwortwert Abs(a) in sequentielle Liste {q}.
'Weil {q} negativen Trennzeichen enthält, wird ein einfaches Kommando
' Printn q, ...' Programmabstürz verursachen. Verwenden Sie stattdessen:
'
DECLARE FUNCTION ExQ% (p AS INTEGER, a AS INTEGER, q AS INTEGER, _
k AS INTEGER)
'Herausziehen der sukzessiven Zahlen p und Abs(a) aus der Liste {q} mit
'Versetzung k. Initiieren mit k = 0, Wert ist Null wenn am Ende der Liste.
'
DECLARE FUNCTION Gete% (p AS INTEGER, k AS INTEGER)
'Gibt Array-Element Numero k der Zahl p zurück.
'Dies ist eine Ziffer in der Basis MB.
'
DECLARE FUNCTION Getl% (p AS INTEGER)
'Gibt die Anzahl der Array-Elemente für Zahl p zurück.
'
DECLARE FUNCTION Gets% (p AS INTEGER)
'Gibt das Vorzeichen der Zahl p zurück, Gets = -1 wenn p < 0, sonst 1.
'
DECLARE SUB Sete (p AS INTEGER, k AS INTEGER, a AS INTEGER)
'Setzt binär Array-Element Numero k von Zahl p auf Abs(a).
'
DECLARE SUB Setl (p AS INTEGER, a AS INTEGER)
'Setzt das Anzahl der Array-Elemente für p auf Abs(a).
'
DECLARE SUB Sets (p AS INTEGER, a AS INTEGER)
'Setzt das Vorzeichen von Zahl p auf Sgn(a + 0.5).
'
' **************************************************************************
' interne Funktionen
' **************************************************************************
DECLARE SUB Errorh (f AS STRING)
'Zeigt eine Fehlermeldung an.
'
DECLARE FUNCTION Hp2% (p AS INTEGER)
'Rückgabewert 2^ (höchste gesetzte bit im höchstwertigen Speicherwort von p).
'
DECLARE SUB Lftj (p AS INTEGER, k AS INTEGER)
'Langzahl p wird links justiert ab Array-Element k.
'
DECLARE FUNCTION PrimCeil& ()
'Rückgabewert ist die obere Begrenzung von Primzahltabelle PrimFlgs.bin.
'
DECLARE SUB Work (f AS STRING)
'Gibt das Arbeits-Dateiverzeichnis im ENVIRON$("LARGEINT") zurück.
'Der Puffer f soll genügend groß sein um den Pfad zu behalten.
'
' **************************************************************************
' BASIC Prototypen für Maschinensprache-Unterstützung
' **************************************************************************
DECLARE FUNCTION EstQ% (SEG a AS INTEGER, c AS LONG)
'( n(j, ..)·MB^2 + n(j-1, ..)·MB + n(j-2, ..) ) \ c
'45-bit Teilungszahl \ 30-bit Teiler.
'
DECLARE SUB Ffix ()
'Repariert den FWAIT Programmfehler ins Microsoft FPU Emulator-Library.
'
DECLARE SUB SftL (c AS LONG, k AS INTEGER)
'ShL long Integer c um k (mod 32) Bits.
'
DECLARE SUB SftR (c AS LONG, k AS INTEGER)
'ShR long Integer c um k (mod 32) Bits.
'
' **************************************************************************
Übersicht der Module zur Zahlentheorie
Mit der Programmbibliothek kommen einigen BASIC-Module betreffend die Zahlentheorie, die als Testumfeld dienen können. Lassen Sie sie laufen mit den Beispiel-Eingabedateien um Korrektheit und Leistung der Bibliothek zu zeigen. Alle Module sind im Englisch verfaßt.
Sehen Sie den Liesmich.txt ein
Spiegel Seite (in English)
Die Ackermannsche Funktion in Basic (English).
Es gibt auch einen Anhang: Arithmetik in endlichen Körper (English).
Wenn Sie ein interessantes Programm mit der Bibliothek geschrieben oder Verbesserungsvorschläge haben, laßt mich wissen. Wenn Sie Programmfehler finden, berichten Sie mir bitte hier.
Lernen Sie über der Zahlentheorie auf Eric Weissteins großen
Welt der Mathematik
oder der On-Line
Wikipedia Enzyklopädie.
Buchliste:
Verzicht:
Dieser BASIC-Code für Langzahlen (großen Ganzzahlen, big numbers, grands nombres entiers, grandi numeri interi, números enteros grandes, inteiros grandes, μεγαλοι ακεραιοι αριθμοι usw.) wird kostenlos verteilt in die Hoffnung daß es nützlich sein wird, aber ohne Garantie jeder Art, sogar die implizierte Garantie der Marktgängigkeit oder Angemessenheit zu einem bestimmten Zweck. Erlaubnis ist bewilligt für das Ändern Ihrer Kopie des Codes oder die Formung einer nicht-kommerziellen Anwendung, die auf ihn basiert, und solche Kopien und Änderungen zu verteilen, vorausgesetzt daß der geänderte Inhalt einen Hinweis auf dem Urheber des Quellcodes und Nachrichten angebend trägt, daß er geändert worden ist und von wem.
