Arbitrary Length Integer

Anwendungen, Tools, Userlibs und anderes nützliches.
RalfP
Beiträge: 23
Registriert: 17.03.2014 22:32

Arbitrary Length Integer

Beitrag von RalfP »

Hallo

Ich habe das Thema mit den 'beliebig langen Integerwerten' noch einmal angefasst und dafür eine DLL kompiliert.
Die DLL läuft mit x86 Programmen und enthält folgende Funktionen:

zzadd(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; Addition (ret = Wert1 + Wert2)
zzsub(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; Subtraktion
zzmul(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; Multiplikation
zzdiv(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; Division
zzrem(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; Modulo
zzpom(ret.a, w1.p-ascii, e.p-ascii, w3.p-ascii) ; Potenzieren-Modulo x = w1^e % w3 (e kann auch negative sein)
zzgcd(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; ggT (größter gemeinsamer Teiler)
zzeea(rd.a, rs.a, rt.a, Wa.p-ascii, Wb.p-ascii) ; Extended Euclidean Algorithm d = gcd(a, b) = a*s + b*t
zzsqr(ret.a, Wert1.p-ascii) ; Quadrat ret = w1*w1
zzsro(ret.a, Wert1.p-ascii) ; Quadratwurzel ret = floor(a^{1/2}) (a >= 0)
zzpri(ret.a, len.l) ; Primzahl erzeugen
zznpr(ret.a, Wert1.p-ascii) ; nächsthöhere Primzahl ret = smallest prime >= w1. Uses ProbPrime with NumTrials.
zzpwr(ret.a, Wert1.p-ascii, e.l) ; Potenzieren x = a^e (e >= 0)
zzsee(Wert1.p-ascii) ; setzt den Startwert für zzrnd (Seed)
zzrnd(ret.a, len.l) ; Zufallszahl mit der Länge 2^len-1 erzeugen
zzcrt(ret1.a, ret2.a, Wert1.p-ascii, Wert2.p-ascii) ; Incrementaler Chinesischer Restsatz
zzrec(ret1.a, ret2.a, Wert1.p-ascii, Wert2.p-ascii, Wert3.p-ascii, Wert4.p-ascii) ; Rational Reconstruction
zzbtn(ret.a, byte.a, n.l) ; Byte to Number x = sum(byte*256^i, i=0..n-1) (byte[0] = LSB)
zzntb(ret.a, Wert1.p-ascii, n.l) ; Number to Byte
zzand(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; bitwise And
zzior(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; bitwise Or
zzxor(ret.a, Wert1.p-ascii, Wert2.p-ascii) ; bitwise Xor
nbr.l = zznob(Wert1.p-ascii) ; Anzahl der Bits
nbr.l = zzham(Wert1.p-ascii) ; Hamming Gewicht (die Anzahl der von "0" verschiedenen Zeichen)
zzlsh(ret.a, Wert1.p-ascii, sh.l) ; links schieben
zzrsh(ret.a, Wert1.p-ascii, sh.l) ; rechts schieben (mit Nullen aufgefüllt - Vorzeichen bleibt erhalten)

Bei den Funktionen werden alle langen Integer in einem String an die DLL übergeben. Für das Ergebnis wird ein Pointer auf ein vorbereitetes Byte-Array (.a) übergeben. Das Array enthält nach der Berechnung das Ergebnis in Form eines Ascii-String bzw. der einzelnen Ziffern in den Feldern. Das Array muss vor der Nutzung komplett mit dem Wert "0" gefüllt sein (das ist der Fall, wenn es frisch angelegt wurde), sonst ist das Ende vom Ergebnis-String nicht erkennbar. Das Array muss mindestens so groß sein, wie die Anzahl der Stellen, die beim Ergebnis erwartet werden (+ 1 für den anschließenden 0-Wert).
Mit >> Ergebnis$ = PeekS(*ret, -1, #PB_Ascii) << erhält man wieder einen String zurück.

Um zu zeigen wie es funktioniert, habe dazu eine kleine Anwendung geschrieben die man hier herunterladen kann:
http://www.ralf-pagel.de/Kryptografiese ... erator.zip

Diese DLL darf jeder gerne für eigene Projekte nutzen.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Arbitrary Length Integer

Beitrag von STARGÅTE »

Auch wenn diese DLL durch den Umweg über Strings vermutlich sehr langsam ist, hab ich mal ein paar Tests gemacht.
  • Ist es gewollt, dass die Bit-Befehle (and, or, xor) das Vorzeichen ignorieren?
    Üblicherweise werden negative Zahlen als Zweierkomplement behandelt,
    sodass z.B. -3 (0b...11111) OR 2 (0b10) dann -1 (0b...11111) ergibt.
  • Eine Division durch Null "zzdiv(*ret4 "10", "0")" sollte besser abgefangen werden als ein Absturz der gesamten Anwendung:
    ---------------------------
    Microsoft Visual C++ Runtime Library
    ---------------------------
    This application has requested the Runtime to terminate it in an unusual way.
    Please contact the application's support team for more information.
    ---------------------------
    OK
    ---------------------------
Edit: Wieso eigentlich Microsoft Visual C++??
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
RalfP
Beiträge: 23
Registriert: 17.03.2014 22:32

Re: Arbitrary Length Integer

Beitrag von RalfP »

Danke @STARGÅTE fürs Testen.

Richtige Speedtests habe ich damit noch nicht durchgeführt, aber 4098-Bit-Primzahlen werden in ca. 3s gefunden. Alles andere mit der Länge geht wesentlich schneller.

Ob die Befehle "and, or, xor" das Vorzeichen ignorieren hatte ich nicht getestet. Ich schau mir das mal an (und denke auch noch mal darüber nach, speziell ob dann nicht auch eine feste Länge erforderlich ist).

Eine Division durch Null sollte abgefangen werden. Das hatte ich ebenfalls nicht getestet. Ich werde das ändern.

>> Wieso eigentlich Microsoft Visual C++?? <<
Die Frage kann ich z.Z. nicht beantworten. Ich habe das mit Code::Blocks gemacht, bin damit aber noch nicht so fit. Bisher bin ich davon ausgegangen, dass ich mingw32-gcc.exe als Kompiler eingestellt habe und das ist doch wohl eine Portierung aus dem Linux-Bereich.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Arbitrary Length Integer

Beitrag von STARGÅTE »

RalfP hat geschrieben:Ob die Befehle "and, or, xor" das Vorzeichen ignorieren hatte ich nicht getestet. Ich schau mir das mal an (und denke auch noch mal darüber nach, speziell ob dann nicht auch eine feste Länge erforderlich ist).
Das mit der festen Länge dachte ich im ersten Moment auch, aber nein, es funktioniert auch ohne Längenbeschränkung.
So wie positiven Zahlen beliebige viele Nullen voran gestellt werden können (ohne den Wert zu ändern),
können negativen Zahlen (im Zweierkomplement der Bit-Darstellung) beliebig viele Einsen voran gestellt werden.
Wenn ich also (-n) | (+m) mache, muss das Ergebnis wieder negativ sein.
Wenn ich (-n) & (+m) mache, wird darauf eine positive Zahl.
Natürlich sind ein paar Zwischenoperationen nötig, wenn man nicht im Zweierkomplement arbeitet,
sondern (wie ich vermute) die Zahlen +n und -n bis auf das Vorzeichen die gleiche Darstellung haben.

Noch eine Anmerkung:
Generell stürzt die DLL ab, wenn ich bei zzsro() oder bei zzpwr() negative Zahlen verwende.
Klar schreibst du, dass es nur für positive Zahlen geht, aber ich denke eine kleine If-Abfrage sollte trotzdem enthalten sein.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
RalfP
Beiträge: 23
Registriert: 17.03.2014 22:32

Re: Arbitrary Length Integer

Beitrag von RalfP »

Die Abstürze werde ich abfangen.

Ich habe für diesen speziellen Fall (bitweiser Operator, negative Werte, undefiniert Variablengrösse) keine vernünftigen Lösungen in der Literatur gefunden, also versuche ich mal Regeln für die Bit-Funktionen mit positiven und negativen Werten aufzustellen:
1.) Bei Strings ist alles klar, da steht an erster Stelle ein Minuszeichen oder eine Ziffer.
2.) Wenn es um die Bits geht, bedeutet ein führendes 1-Bit, egal wie viele Bits dahinter sind, dass es sich um einen negativen Wert handelt, und eine führende Null zeigt einen positiven Wert an. (Oder anders ausgedrückt: Der erste Wechsel von einem 1-Bit zu einem 0-Bit zeigt den Beginn eines negativen Werts an (wobei das 1-Bit das Vorzeichen darstellt) und der erste Wechsel von einem 0-Bit zu einem 1-Bit zeigt den Beginn eines positiven Werts an.

Punkt 2.) ist für zzand(), zzior(), zzxor() nicht relevant, weil dort beides, die Ein- und Ausgabe über Ascii-Zeichen erfolgt. Es gibt aber 3 weitere Funktionen mit denen die negativen Werte kompatibel sein müssten/sollten.

Für die Funktion zzham() (zählt die Anzahl der gesetzten Bits) schlage ich vor, dass bei negativen Werten die 1 vor der höchsten 0 mitgezählt wird und dann alle 1-Bits bis zum Ende gezählt werden (also nicht die 0-Bits zählen oder so ähnlich).

Bei den Funktionen zzbtn() und zzntb() müsste folgerichtig bei negativen Werten ebenso verfahren werden. Das führt aber bei zzbtn() und zzntb dazu, dass die Werte nicht eindeutig bestimmbar sind. Bei diesen beiden Funktionen wird die Länge (in Byte) angegeben.
Bei zzbtn() wird damit die Anzahl der relevanten Bytes im Übergabe-Array angegeben.
Bei zzntb() ist diese Angabe dazu gedacht um der Funktion die Länge des zur Verfügung stehenden Rückgabe-Arrays mitzuteilen.

Um eine Lösung zu finden könnte man bei zzbtn() statt der Anzahl der Bytes die Anzahl der Bits angeben (das müsste ich entsprechend umschreiben - die Bytes lassen sich davon ja ableiten). Mit der Anzahl der Bits steht auch die Position des Vorzeichen-Bits fest.
Die Funktion zzntb() müsste dann zusätzlich die Anzahl der Bits zurück geben, denn die steht vorher ja noch nicht fest (oder sie müsste vom Anwender mit der Funktion zznob() ermittelt werden bevor er das Array ausliest).

Alternativ könnte eine Ausnameregel definiert werden, dass bei Eingabe und Rückgabe das höchste Byte des Arrays (bei negativen Werten) mit Einsen aufzufüllen ist. Dann ist klar definiert, dass das erste Bit im höchsten Byte das Vorzeichen-Bit ist.

(darüber diskutiere ich gerne, mir gefällt beides nicht)

>>>
... nicht im Zweierkomplement ... sondern (wie ich vermute) die Zahlen +n und -n bis auf das Vorzeichen die gleiche Darstellung haben.
<<<
Ich bin überhaupt nicht auf die Idee gekommen, dass die Bit-Funktionen einmal negative Werte verarbeiten könnten. Deshalb ist es eher einem Zufall zu verdanken, dass das Programm dabei nicht auch abstürzt.
.
Benutzeravatar
STARGÅTE
Kommando SG1
Beiträge: 6996
Registriert: 01.11.2005 13:34
Wohnort: Glienicke
Kontaktdaten:

Re: Arbitrary Length Integer

Beitrag von STARGÅTE »

Bevor ich mitdiskutieren kann, muss du mir noch mal klar stellen, in welchem "System" du arbeitest.
Wenn ich zwei Strings in deinen Funktionen z.B. zzadd übergebe ("1234" und "-567"), rechnet diese Funktion dann intern mit den Dezimalzahlen/-ziffern oder werden die Strings vorher ins Binärsystem übertragen sodass du dann mit 010011010010 und 10111001001 bzw. -01000110111 ?
RalfP hat geschrieben:Ich habe für diesen speziellen Fall (bitweiser Operator, negative Werte, undefiniert Variablengrösse) keine vernünftigen Lösungen in der Literatur gefunden
Ich stütze meine Aussage auf:https://reference.wolfram.com/language/ ... html#28221
RalfP hat geschrieben:Punkt 2.) ist für zzand(), zzior(), zzxor() nicht relevant, weil dort beides, die Ein- und Ausgabe über Ascii-Zeichen erfolgt.
Hää, na genau bei Bit-Operationen ist es doch relevant welche Bitfolge die Zahl hat...
RalfP hat geschrieben:Bei den Funktionen zzbtn() und zzntb() müsste folgerichtig bei negativen Werten ebenso verfahren werden. Das führt aber bei zzbtn() und zzntb dazu, dass die Werte nicht eindeutig bestimmbar sind. Bei diesen beiden Funktionen wird die Länge (in Byte) angegeben.
Wenn du im Zweierkomplement-Bild bleibst schon. Dann fasst dort das most significant byte nur 7 (satt 8) Bits.
Möchtest du also die Zahl 130 in Byte-Darstellung haben, brauchst zu Zwei Bytes, damit es führende Null-Bits gibt und die Zahl als positiv erkannt wird.
Anders herum brauchst du für -130 ebenfalls 2 Byte, damit du führende Einzer-Bits hastund die Zahl als negativ erkannt wird.
Brauchst du maximal 7 Bits im most significant byte brauchst du dieses Zusatzbyte nicht.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
RalfP
Beiträge: 23
Registriert: 17.03.2014 22:32

Re: Arbitrary Length Integer

Beitrag von RalfP »

@STARGÅTE Danke für die Erläuterungen.
Das hört sich alles logisch an.

Ich habe erst einmal die Abstürze abgefangen, bei zzdiv() wenn man durch Null teilt, bei zzsro() und zzpwr() wenn man negative Zahlen verwendet. Die DLL im Zip-Download habe ich ausgetauscht.

Bei den Bit-Funktionen arbeite ich z.Z. mit den Absolut-Beträgen der übergebenen Werte.
.
RalfP
Beiträge: 23
Registriert: 17.03.2014 22:32

Re: Arbitrary Length Integer

Beitrag von RalfP »

Hallo,

ich habe die Bit-Funktionen in der DLL noch einmal überarbeitet, so dass damit jetzt auch negative Werte verarbeitet werden können.

Weil es sich um beliebig große Integer-Variablen handelt, sind dabei ein paar Dinge zu beachten:
Beginnt ein Wert in der binären Darstellung mit '0' handelt es sich um einen positiven Wert. Wenn er mit '1' beginnt handelt es sich um einen negativen Wert. Bei Integer-Variablen beliebiger Größe kann das Vorzeichen-Bit an jeder Stelle stehen. Damit die Werte eindeutig sind, müssen bei der binären Ein- und Ausgabe die erforderlichen Array-Bytes mit den entsprechenden Vorzeichen aufgefüllt werden (wenn sie nicht schon durch den Wert komplett ausgefüllt sind). Damit ist Bit7 im höchsten Byte immer das Vorzeichen-Bit.

Ein Beispiel dazu: Für den positiven Wert 255 sind in einer vorzeichenlosen Darstellung 8 Zeichen erforderlich. Man kann ihn also in einer PB-Byte-Variable vom Type .a speichern. Die beliebig großen Integer-Variablen haben allerdings immer ein Vorzeichen. Das Vorzeichen muß immer mitgeschrieben werden, auch wenn es eine '0' ist. Der Wert 255 hat also 9 Binär-Zeichen und es sind dafür 2 Byte im Array erforderlich. Das höchstwertige Byte muss mit Vorzeichen-Bits aufgefüllt werden. Das Byte[0] enthält dann '11111111' und das Byte[1] enthält dann '00000000'. Würde man nur ein Byte nutzen (und dieses mit Einsen füllen) wäre das ein anderer Wert. Dieser Wert würde als -1 interpretiert.

Bei der Funktion zzbtn() muss das höchstwertige Byte mit Vorzeichen-Bits aufgefüllt werden, wenn sich die Anzahl der (für die Wertdarstellung erforderlichen) Bits nicht restlos durch 8 teilen lässt. Zusätzlich zu dem Array, das den Wert enthält, muss in einer Long-Variablen die Zahl der genutzten Bytes übergeben werden.

Bei der Funktion zzntb() stellt Bit7 im höchsten Byte ebenfalls das Vorzeichen bei der binären Ausgabe dar. Die Funktion selbst gibt jetzt, anders als im ersten Beitrag dargestellt, die Zahl der wertenthaltenden Array-Bytes als Long-Wert zurück. Eine Übergabe der Arraygröße an die DLL-Funktion ist nicht mehr nötig.

Die Funktion zznob() zählt alle Zeichen, die für die binäre Darstellung minimal nötig sind. Anders als bei Integerwerten fester Länge wird hier das Vorzeichen immer mitgezählt (also auch bei positiven Werten die '0').

Die Funktion zzham() zählt wie oft eine '1' in der binären Darstellung vorhanden ist. Bei negativen Werten wird dabei eine '1' für das Vorzeichen-Bit mitgezählt.

Die Funktionen zzand(), zzior() und zzxor() arbeiten jetzt natürlich auch mit negativen Werten.


Der Download im ersten Beitrag wurde aktualisiert.


Es würde mich freuen, wenn jemand die Bit-Funktionen mit den negativen Werten tatsächlich einmal benötigt.
.
Antworten