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 (siehe Download-Seite für FreeBasic, XBasic und Visual Basic Versionen), 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
'
' ****************************************************************************
' 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 Doppelver-
'weisungen, weil diese Programmabstürze verursachen.
'
'In nachfolgenden Prototypen,
'sind die Buchstaben p, q, r, d, m 16-Bit (Pseudo)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.
'Die t-Nummern zwischen geschwungen Klammern bedeuten die Reihe der
'Zwischenregister die von der Subroutine verwendet werden, und nicht als
'Argumente übergeben werden können.
'
DEFINT A-B, D-Z: DEFLNG C
DECLARE FUNCTION LargeInit% (k, 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 <= 450 in der $STATIC-Version) und String f = Programm-Namen.
'Wenn f = "" wird keine Logdatei geöffnet.
'Rückgabewert ist die maximale Langzahllänge gemessen in Array-Elementen
'(='Worte'). Die Dezimalzahl-Länge ist annäherend 4.51 * Langzahllänge.
'
DECLARE SUB Letf (p, c)
'Weist Langzahl p den vorzeichenbehafteten Doppelwortwert c zu.
'
DECLARE SUB Readst (p, g AS STRING)
'Weist Langzahl p die dezimale Zahlzeichenkette g zu. Außer einem
'vorgesetzten Minuszeichen, gibt es keine Überprüfung auf Nichtziffer-
'Charaktere in der Zeichenkette. {t1..t2}
'
DECLARE SUB Rndf (p, k)
'Weist Langzahl p eine positive Zufallszahl der Bitlänge k zu.
'
DECLARE SUB Term ()
'Schließen der Primzahltabelle und Logdatei.
'
' ****************************************************************************
' Funktionen zur Konvertierung
' ****************************************************************************
DECLARE FUNCTION Decf% (p)
'Konvertiert Langzahl p zur Basis MD (siehe unten), gibt die Bytelänge von
'dezimal(p) zurück. Auf zu rufen bevor CnvSt. {t1..t2}
'
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. {t2}
'
DECLARE FUNCTION Logf# (p)
'Natürlicher Logarithmus von |Langzahl p| in doppelte Genauigkeit.
'
DECLARE SUB Ratdec (g AS STRING, p, q)
'Konvertiert die Dezimaldarstellung von Zahlenverhältnis p/q in [0, 1)
'in eine Zahlzeichenkette. {t0..t2}
'
' ****************************************************************************
' Datenausgabe
' ****************************************************************************
DECLARE SUB Printf (f AS STRING, g AS STRING, h AS STRING, sw)
'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, f AS STRING, h AS STRING, sw)
'Druckt Langzahl p ab mit Vorspann f und Schwanzende h, verwendet Printf.
'{t1..t2}
'
DECLARE SUB Printr (p, q, f AS STRING, k)
'Druckt die Dezimaldarstellung von Zahlverhältnis p/q ab mit Bruchlänge k.
'{t1..t2}
'
DECLARE SUB Prints (f AS STRING, sw)
'Druckt die Zeichenkette f ab,
'setzen Sie switch = 1 um ein CrLf an zu heften, switch = 2 für Zweier.
'
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.
'
' ****************************************************************************
' grundlegende Rechenfunktionen
' ****************************************************************************
DECLARE SUB Subt (p, q)
'Subtrahiert q von p, das Ergebnis steht in p.
'
DECLARE SUB Add (p, q)
'Addiert p und q, das Ergebnis steht in p.
'
DECLARE SUB Inc (p, a)
'Erhöht Langzahl p mit dem vorzeichenbehafteten Einwortwert a.
'
DECLARE SUB Divd (p, d, q)
'Dividiert p und d, der Quotient steht in q, der Rest in p. {t2}
'
DECLARE FUNCTION Divint% (p, a)
'Dividiert Langzahl p mit |Einwortwert a|,
'gibt der |Rest| zurück und setzt p zum Quotient.
'
DECLARE SUB Ldiv (p, d)
'Setzt p zum Quotient p / d. {t1..t2}
'
DECLARE SUB Mult (p, q, r)
'Multipliziert p und q, das Ergebnis steht in r.
'
DECLARE SUB Lmul (p, q)
'Setzt p zum Produkt p * q. {t2}
'
DECLARE SUB Squ (p, q)
'Gibt das Quadrat von p in q zurück.
'
DECLARE SUB Isqrt (p, q)
'Gibt die Ganzzahl-Quadratwurzel von p in q zurück. {t0..t2}
'
DECLARE SUB Chs (p)
'Änderung des Vorzeichens von Langzahl p.
'
DECLARE FUNCTION Absf% (p)
'Löscht das Vorzeichenbit von Langzahl p, gibt den jetzigen Wert zurück.
'
' ****************************************************************************
' Kopieren und Vergleich
' ****************************************************************************
DECLARE SUB Dup (p, q)
'Kopiert Langzahl p zu q.
'
DECLARE SUB Swp (p, q)
'Täuscht Langzahlen p und q.
'
DECLARE FUNCTION Cmp% (p, q)
'Vergleicht p und q:
'das Resultat ist -1 falls p < q, 0 falls p = q, und 1 falls p > q.
'
DECLARE FUNCTION Isf% (p, a)
'Boolesch: überprüft ob Langzahl p gleich den Einwortwert a ist.
'
DECLARE FUNCTION Ismin1% (p, m)
'Boolesch: überprüft ob p = m - 1
'
' ****************************************************************************
' Bit-Verarbeitung
' ****************************************************************************
DECLARE SUB Boolf (p, q, k)
'Bitweise boolesche Funktionen setzen p zu q Op(k) p, mit Op(1) = AND,
'Op(2) = XOR, Op(3) = OR. Falls k = 0 wird p zu NOT p gesetzt und q ignoriert.
'Jeweils bleibt das Vorzeichen von p unverändert.
'
DECLARE SUB Lsft (p, k)
'Langzahl p wird um k Bits nach links verschoben,
'k < 0 schiebt |k| ganze Worte.
'
DECLARE SUB Rsft (p, k)
'Langzahl p wird um k Bits nach rechts verschoben,
'k < 0 schiebt |k| ganze Worte.
'
DECLARE FUNCTION Odd% (p)
'Entfernt abschließende Null-Bits aus der Langzahl p,
'Rückgabewert ist die (rechts) Schiebezahl.
'
DECLARE FUNCTION Bitl% (p)
'Gibt die Bitlänge von Langzahl p zurück.
'
' ****************************************************************************
' Modular-Arithmetik
' ****************************************************************************
DECLARE SUB Moddiv (p, m)
'Gibt den positiven Rest p modulo m. {t1..t2}
'
DECLARE SUB Modbal (p, m)
'Gibt den ausgeglichenen Rest p modulo m: |p| <= m / 2. {t1..t2}
'
DECLARE FUNCTION Mp2% (p, a)
'Gibt Langzahl p modulo a zurück, mit a einem Einwortwert Potenz-von-Zwei.
'
DECLARE SUB Modmlt (p, q, m)
'Multipliziert p und q, reduziert dann modulo m. {t1..t2}
'
DECLARE SUB Modsqu (p, m)
'Quadriert p, reduziert dann modulo m. {t1..t2}
'
DECLARE SUB Modpwr (p, q, m)
'Modulares Potenzieren: Basis p, Hochzahl q, Modul m.
'Das Ergebnis steht in p. {t0..t2, t3 falls q < 0}
'
' ****************************************************************************
' zahlentheoretische Funktionen
' ****************************************************************************
DECLARE SUB Powr (p, k)
'Potenziert Basis p mit |Hochzahl k|, das Ergebnis steht in p. {t0..t3}
'
DECLARE SUB Fctl (p, a)
'Berechnet Fakultät a(a-1)¨¨¨2¨1 in Langzahl p. {t1..t2}
'
DECLARE SUB Lcm (p, q, d)
'Gibt das kleinste gemeinsame Vielfache (p, q) in d zurück. {t0..t2}
'
DECLARE SUB Gcd (p, q, d)
'Gibt den größte gemeinsame Teiler (p, q) in d zurück. {t0..t2}
'
DECLARE SUB Euclid (p, q, d)
'Der erweiterte Euklidische Algorithmus setzt
'p zu 1/p (modulo q), q zu q/ggT, und d zum ggT(p, q). {t0..t2}
'
DECLARE SUB Bezout (p, q, d)
'Lösung der diophantische Gleichung px + qy = ggT(p, q),
'setzt Langzahl p zu x, q zu y, und d zum ggT(p, q). {t0..t3}
'
DECLARE FUNCTION Kronec% (p, q)
'Gibt das quadratische Restsymbol Kroneckers (p/q) = 0, 1, oder -1. {t0..t3}
'
DECLARE FUNCTION IsSqr% (p, q)
'Boolesch: überprüft ob p ein reines Quadrat ist, und setzt q zur Wurzel
'falls wahr. {t0..t2}
'
DECLARE FUNCTION IsPPrm% (p, d, k)
'Überprüft die Primalität von p mit dem Miller-Rabin-Test.
'Rückgabewert 1 falls p bestimmt prim ist, -1 wahrscheinlich prim,
'0 falls p zusammengesetzt. K ist die Anzahl der Zeugen im Test,
'setze k < 0 um die anfänglichen Probedivisionen zu überspringen. {t0..t3}
'
DECLARE FUNCTION Nxtprm& (sw)
'Schleift durch Tabelle PrimFlgs.bin. Initiieren mit sw = 0, danach
'gibt ungeraden(sw) die nächste Primzahl bei jedem folgenden Aufruf.
'Mit sw = 2 der jetzigen Lage ablegen (Push) und Neustarten,
'mit sw =-2 wieder entnehmen (Pop).
'
DECLARE FUNCTION PrimCeil& ()
'Gibt die obere Begrenzung der Primzahltabelle PrimFlgs.bin zurück.
'
DECLARE SUB Triald (q, p, c)
'Probedivision von p bis Schranke c. Primfaktoren und Exponenten werden in
'die Liste {q} gespeichert, der Restfaktor wird in p zurückgegeben. {t0..t3}
'
' ****************************************************************************
' direkter Zugrif
' ****************************************************************************
DECLARE SUB EnQ (q, p, a)
'Speichert Langzahl p und |Einwortwert 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, a, q, k)
'Herausziehen der sukzessiven Zahlen p und |a| aus der Liste {q} mit
'Versetzung k. Initiieren mit k = 0, Wert ist Null wenn am Ende der Liste.
'
DECLARE FUNCTION Getl% (p)
'Gibt die Länge der Langzahl p zurück, gemessen in Worten.
'
DECLARE FUNCTION Gets% (p)
'Gibt das Vorzeichenbit der Zahl p zurück: -32768 falls p < 0, sonst Null.
'
DECLARE FUNCTION Getw% (p, k)
'Gibts Wort k der Langzahl p zurück: eine Ziffer der Basis MB (siehe unten).
'
DECLARE SUB Setl (p, a)
'Setzt die Länge der Langzahl p auf a Worte.
'
DECLARE SUB Sets (p, a)
'Setzt das Vorzeichenbit von Langzahl p falls a < 0, sonst löscht's.
'
DECLARE SUB Setw (p, k, a)
'Setzt Wort Numero k der Langzahl p auf |a| < MB.
'
' ****************************************************************************
' interne Funktionen
' ****************************************************************************
DECLARE SUB Errorh (f AS STRING)
'Zeigt eine Fehlermeldung an.
'
DECLARE SUB Lftj (p, k)
'Langzahl p wird links justiert ab Wort Numero k.
'
DECLARE FUNCTION Hp2% (p)
'Rückgabewert 2^(höchste gesetzte Bit im äußerst Linken Wort der Langzahl p).
'
' ****************************************************************************
' BASIC Prototypen für Maschinensprache-Unterstützung
' ****************************************************************************
DECLARE SUB SftL (c, BYVAL k)
'Long Integer c wird um k (modulo 32) Bits nach links verschoben.
'
DECLARE SUB SftR (c, BYVAL k)
'Long Integer c wird um k (modulo 32) Bits nach rechts verschoben.
'
DECLARE FUNCTION EstQ% (SEG a, c)
'Bildet ein 45-Bits Teilungszahl-Präfix, teilt durch 30-Bits Präfix
'und gibt einen 15-Bit Probe-Quotienten zurück.
'
DECLARE SUB Ffix ()
'Repariert den FWAIT Programmfehler ins QB FPU Emulator-Library.
'
' ****************************************************************************
' globale Konstanten
' ****************************************************************************
CONST LB = 15, MB = &H8000& ' binär Speicherbase
CONST LD = 4, MD = 10000 ' dezimale Zahlzeichenkettebase < MB
CONST t0 = -1, t1 = -2 ' Zeigern zu Wechselregistern
CONST t2 = -3, t3 = -4
'
' ****************************************************************************
Ü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.
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.
