Sehr geehrter Herr Schnoor,
Sie haben Ihr persönliches "Spezialprogramm" zur Prüfung des Strings <ziffern>
auf Mehrfachzeichen bisher nicht vorgelegt. Andererseits hat bislang keiner der
Mitforisten an meinem Nachweis genau dieses Defekts von <ziffern> Kritik geübt.
Wie es scheint, sind Sie als einziger davon überzeugt, dass Ihr <ziffern>String
ein taugliches Gebilde zur fehlerfreien Kodierung und Dekodierung von Zahlen
zur Basis 4096 ist.
Anyway.
Machen wir ein neues Faß auf. Untersuchen wir die Frage: Was ist problematisch,
wenn ein solcher Ziffernstring ein Zeichen mehrfach enthält?
(1) Als Beispiel betrachte ich Hexzahlen mit dem Standard-Ziffernstring ziffern
= '0123456789ABCDEF'.
Als Studienobjekt wähle ich – angregt durch wikipedia – die Dezimalzahl z1 =
45054 (eine Palindromzahl), umgewandelt in HexForm ergibt sich z2 =
hex(z1)[2:].upper() = 'AFFE'.
Konvertiert man z2 zurück in eine Dezimalzahl, erhält man mit z3 = int(z2, 16)
= 45054 die Ausgangszahl z1.
Wenn <ziffern> OK ist, hat man eine "Reise" von z1 zu z2, von z2 zu z3
absolviert. Und prüft abschließend, ob z1 und z3 gleich sind, ob man also ein
Rundreise absolviert hat. Das Umgekehrte gilt auch: Wenn die Reise eine
Rundreise war, ist <ziffern> OK.
Man kann dies kompakt so formulieren:
int(hex(z1)[2:].upper(), 16) == z1,
mit dem Output True.
(2) Jetzt sei <ziffern> defekt, enthalte aber weiterhin 16 Zeichen, jedoch
eines doppelt, etwa statt D ein F, also
ziffern2 = '0123456789ABCFEF', kurz Hexgestört.
Jetzt benötigt man zum Kodieren und Dekodieren zwei selbstgestrickte Funktionen.
Man kann sich freilich jetzt schon klar machen: Die Kodierung von Dezimal z1
via Hexgestört zu z2 geht ohne Probleme. Denn zum Kodieren einer Dezimalzahl
nach einer anderen Basis wird der Euklidische Divisionsalgorithmus verwendet.
Der berechnet aus z1 iteriert die Reste bei Division von z1 durch 16 (rest = z1
% 16), wobei z1 schrittweise ebenfalls verkleinert wird durch Ganzzahldivision
z1 = z1 // 16.
Daraus folgt für den Kodierschritt: Auch mit einem defekten Ziffernstring geht
das problemlos.
Mit der folgenden Funktion
def dezToBase(basis, zahl, ziffern=None):
#
https://stackoverflow.com/questions/2267362/how-to-convert-an-integer-to-a-string-in-any-base
# etwas erweitert.
if zahl == 0:
if ziffern: return '0'
else: return [0]
# Methode: Euklidischer Divisionsalgorithmus
reste = []
while zahl:
reste.append(zahl % basis)
zahl //= basis
reste = reste[::-1] # Reihenfolge der Reste umkehren
if ziffern:
return ''.join([ ziffern[x] for x in reste ])
else:
return reste
und basis = len(ziffern2)
ergibt sich z2 = zahl2Base(basis, z1, ziffern2) = 'AFFE'.
(3) Beim Dekodierschritt stößt man auf ein mögliches Problem: Hier wird z2 zu
einer (Pseudo-)Dezimalzahl
z3 = A*16**3 + F*16**2 + F*16**1 + E*16**0
umgewandelt. Man sieht, wo das Problem (für den Algorithmus) liegt: Welchen
Wert für F nehme ich aus <ziffern2>? Das linke F (der Ersatzspieler für D) hat
den Index-Wert 13, das rechte (=richtige) F hat weiterhin den Index-Wert 15.
Wegen der Wahl des Buchstabens aus <ziffern2> mittels ziffern2.index(.) fällt
die Wahl des Algorithmus auf das linke F (weil der Indexwert 13 < 15 ist).
Mit der Funktion
def bas2dez(basis, zahl, ziffern):
z10 = 0
for i in range(len(zahl)):
z10 = z10*basis + ziffern.index(zahl[i])
return z10
ergibt sich z3 = 44510 != z1, also eine Fehl-Dekodierung
(4) Wie prüft man das gesamte Zahlensystem (aus <ziffern> und davon
abgeleiteter basis) auf Korrektheit?
Dazu genügt es, jede Zahl im Intervall [0, basis] zu Kodieren und zu
Dekodieren, und die Ergebnisse auf Gleichheit zu prüfen. Etwa so:
for z1 in range(basis):
z2 = dezToBase(basis, z1, ziffern)
z3 = bas2dez(basis, z2, ziffern)
if z1 != z3:
print("%s == %s" % (z1, z3))
Für das defekte <ziffern2> oben ergibt sich damit:
45054 == 44510 # eine richtige Fehl-Dekodierung
(5) Man könnte jetzt noch weitere Defekte durchspielen (E ersetzen durch F, C
ersetzen durch D, ...). Es mag sein, dass in EINZELFÄLLEN z1 gleich z3
resultiert. Schön, aber irrelevant. Es geht einzig um die
Frage: Arbeitet das System in ALLEN Fällen korrekt?
(6) Zusammenfassung:
Ein Zahlensystem zu einer "höheren" Basis mit einem
Nicht-Standard-Ziffernstring funktioniert nur genau dann (in ALLEN Fällen)
korrekt, wenn dieser Ziffernstring kein Zeichen mehrfach enthält.
(7) Prüft man das System ziffern4096 von Ihnen, Herr Schnoor, -- hier
publiziert, von Ihnen bis heute als tauglich und insbesondere frei von
Mehrfachzeichen behauptet -- so ergibt sich (nach Tilgung der untauglichen, da
unsichtbaren whitespace-Zeichen, unter Beibehaltung der 60+ Mehrfachzeichen,
und unter Voranstellung der (bislang fehlenden) Ziffer '0', folgender Output
mit 77 Fehl-Dekodierungen:
Basis : 4059 # bewirkt durch die eben beschriebenen "Reinigungsmaßnahmen"
ziffern : "0123456789 ... ꇰꇱꇲꇳꇴꇵꇶꇷꇸꇹ"
[ 1] 877 == 844 [ 2] 878 == 876 [ 3] 879 == 845 [ 4] 880
== 876
[ 5] 881 == 846 [ 6] 882 == 876 [ 7] 883 == 851 [ 8] 884
== 876
[ 9] 885 == 856 [10] 886 == 876 [11] 888 == 876 [12] 890
== 876
[13] 892 == 876 [14] 964 == 943 [15] 966 == 944 [16] 967
== 965
[17] 968 == 956 [18] 969 == 965 [19] 1047 == 1025 [20] 1049
== 1026
[21] 1050 == 1048 [22] 1506 == 1505 [23] 1516 == 1515 [24] 1517
== 1507
[25] 1522 == 1521 [26] 1523 == 1507 [27] 1528 == 1527 [28] 1529
== 1507
[29] 1534 == 1533 [30] 1535 == 1507 [31] 1548 == 1503 [32] 3885
== 857
[33] 3886 == 858 [34] 3887 == 859 [35] 3888 == 860 [36] 3889
== 861
[37] 3890 == 862 [38] 3891 == 863 [39] 3892 == 864 [40] 3893
== 865
[41] 3894 == 866 [42] 3895 == 867 [43] 3947 == 3077 [44] 3948
== 3078
[45] 3949 == 3079 [46] 3950 == 3080 [47] 3951 == 3081 [48] 3952
== 3082
[49] 3953 == 3083 [50] 3954 == 3084 [51] 3955 == 3085 [52] 3956
== 3086
[53] 3957 == 3090 [54] 3959 == 3461 [55] 3960 == 3462 [56] 3961
== 3463
[57] 3962 == 3464 [58] 3963 == 3465 [59] 3964 == 3466 [60] 3965
== 3467
[61] 3966 == 3468 [62] 3967 == 3469 [63] 3968 == 3470 [64] 3969
== 3471
[65] 3970 == 3472 [66] 3971 == 3473 [67] 3972 == 3474 [68] 3973
== 3475
[69] 3974 == 3476 [70] 3975 == 3477 [71] 3976 == 3478 [72] 3977
== 3479
[73] 3978 == 3480 [74] 3979 == 3445 [75] 3980 == 3446 [76] 3981
== 3447
[77] 3982 == 3448
Erst nach Tilgung der Mehrfachzeichen durch
ziffern = ''.join(sorted(list(set(ziffern))))
gibt es keine Fehler mehr.
Dafür hat man aber auch die Basis 4096 "verloren" und gegen die Basis 3982
getauscht. Will man die Wunschbasis 4096 wiederhaben, muß man halt – wie schon
früher gesagt – nachbessern.
W. Büchel
_______________________________________________
python-de Mailingliste -- python-de@python.org
Zur Abmeldung von dieser Mailingliste senden Sie eine Nachricht an
python-de-le...@python.org
https://mail.python.org/mailman3/lists/python-de.python.org/
Mitgliedsadresse: arch...@mail-archive.com
