Beim letzten Mal habe ich einen ganzzahligen Ring implementiert, nachdem ich eine abstrakte Basisklasse für Monoide, Gruppen und Ringe erstellt hatte. Dieses Mal implementieren wir nach dem Erstellen der abstrakten Basisklasse des Feldes das rationale Zahlenfeld, den Restklassenring und den endlichen Körper.
Der Körper ist ein Set, das die folgenden Bedingungen erfüllt
- Ein Ring um den Multiplikator $ \ star $ und das Additiv $ \ oplus $
- Andere Mengen als das additive Einheitselement $ 0 $ bilden eine Gruppe für den Multiplikator $ \ star $
Wenn Sie dies durch ein bekanntes Wort ersetzen,
- Es gibt $ 1 $ und $ 0 $, und Sie können drei Operationen ausführen: Addition, Subtraktion und Multiplikation.
- Andere Elemente als $ 0 $ haben eine umgekehrte Multiplikation, dh sie können durch andere als $ 0 $ geteilt werden
Mit anderen Worten, es ist eine Menge, die vier Betriebsregeln ausführen kann (Addition, Subtraktion, Multiplikation und Division).
Erben Sie beim Implementieren einer Klasse die bisher erstellten Gruppen und Ringe und geben Sie "True" zurück, wenn es nur bei der Durchführung des inversen Tests $ 0 $ ist.
FieldType = TypeVar("FieldType", bound="Field")
class Field(Group, Ring):
def testInverse(self: FieldType) -> bool:
if self * self.identity() == super().zero():
return True
else:
return super().testInverse()
Lassen Sie uns nun ein rationales Zahlenfeld erstellen. Eine rationale Zahl ist eine Zahl, die in der Form $ \ frac {p} {q} $ mit den beiden ganzen Zahlen $ p $ und $ q $ dargestellt werden kann. Behalten Sie daher diese $ p $ und $ q $ in der Instanz der rationalen Zahlenklasse bei.
Wenn Sie nach gleichen Brüchen suchen, verursacht der einfache Vergleich von $ p $ mit $ q $ Probleme. Dies liegt daran, dass der Nenner je nach Instanz unterschiedlich sein kann, auch wenn die Brüche gleich sind. Es gibt zwei Möglichkeiten, damit umzugehen.
Sie können es reduzieren, indem Sie die später implementierte euklidische Methode der gegenseitigen Teilung verwenden. Hier verwenden wir jedoch die einfache Methode zur Bewertung von $ ps = qr $. Grundsätzlich handelt es sich um die Berechnung von Brüchen, wie sie in der Grund- und Mittelschule gelernt wurden, sodass keine besondere Erklärung erforderlich ist.
class Rational(Field):
def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
self.p = p
self.q = q
def __repr__(self: "Rational") -> str:
if self.q == self.q.identity():
return "%s" % self.p
return "%s/%s" % (self.p, self.q)
def __mul__(self: "Rational", x: "Rational") -> "Rational":
return Rational(self.p * x.p, self.q * x.q)
def __add__(self: "Rational", x: "Rational") -> "Rational":
return Rational(self.p * x.q + x.p * self.q, self.q * x.q)
def __eq__(self, x):
if not isinstance(x, Rational):
return NotImplemented
return self.p * x.q == x.p * self.q
def __neg__(self: "Rational") -> "Rational":
return Rational(-self.p, self.q)
def identity(self: "Rational") -> "Rational":
return Rational(self.p.identity(), self.p.identity())
def inverse(self: "Rational") -> "Rational":
return Rational(self.q, self.p)
def zero(self: "Rational") -> "Rational":
return Rational(self.p.zero(), self.p.identity())
Q = Rational
Der Alias für "Rational" ist "Q".
Lassen Sie uns nun die Funktionsweise rationaler Zahlen überprüfen.
a = Q(Z( 8), Z(3))
b = Q(Z(-5), Z(4))
c = Q(Z( 3), Z(7))
y = a * b + c
print(y)
# -> -244/84
print(y.inverse())
# -> 84/-244
Es funktionierte.
Im Moment ist die Reduktion nicht implementiert, kann jedoch zum Zeitpunkt der Anzeige unter Verwendung der später beschriebenen euklidischen Methode der gegenseitigen Teilung reduziert werden.
Python hat eine Klasse "Fraktionen.Fraktion" zum Ausdrücken von Brüchen. Wenn Sie nur mit Brüchen arbeiten möchten, reicht diese Klasse aus.
from fractions import Fraction
a = 0
for i in range(10):
a += 1/10
print(a == 1)
# -> False
a = 0
for i in range(10):
a += Fraction(1, 10)
print(a == 1)
# -> True
Ein Beispiel für Software, die "Fraction" verwendet, ist die Python-Schnittstelle [PyAV] der Videokonvertierungssoftware FFMPEG (https://github.com/mikeboers/PyAV). Wir verwenden Brüche, um die Bildrate zu berechnen.
Von nun an wird es mehr Möglichkeiten für die Kürzung und den Rest geben. Daher wäre es zweckmäßig, eine abstrakte Basisklasse für den euklidischen Ring als "Ring zu erstellen, der abgeschnitten und geteilt werden kann und der Rest kann erhalten werden".
EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")
class EuclidianRing(Ring, metaclass=ABCMeta):
@abstractmethod
def __floordiv__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
pass
@abstractmethod
def __mod__(self: EuclidianRingType, x: EuclidianRingType) -> EuclidianRingType:
pass
Ersetzen Sie dann die übergeordnete Klasse von "Integer" von "Ring" durch "EuclidianRing", um die Kürzungsteilung und den Rest zu definieren.
class Integer(EuclidianRing):
# ~~ snip ~~
def __floordiv__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v // x.v)
def __mod__(self: "Integer", x: "Integer") -> "Integer":
return Integer(self.v % x.v)
Für die ganzen Zahlen $ a $, $ b $ und die natürliche Zahl $ n $ gilt, wenn $ a - b = n \ mathbb {Z} $ ($ \ mathbb {Z} $ ist eine beliebige ganze Zahl) "$ a $ und $ b $ stimmt mit $ n $ als Gesetz überein ", sagt $ a \ equiv b \ pmod n $. Eine Menge, die zwei solcher Zahlen als gleich behandelt, wird als "Überschussring modulo $ n $" bezeichnet.
Lassen Sie uns nun die Restklasse Ringklasse ModRing implementieren.
Eine Instanz der restlichen Ringklasse enthält $ a $ und das Gesetz $ n $. Stellen Sie sicher, dass $ a $ und $ n $ beliebige euklidische Ringe akzeptieren, nicht nur ganze Zahlen. Da $ a $ bei der Anzeige auf dem Bildschirm die kleinste kongruente Zahl von 0 oder mehr sein soll, berechnen wir beim Erstellen der Instanz $ a \ bmod n $.
Als nächstes müssen Sie es unmöglich machen, Zahlen mit verschiedenen Methoden zu berechnen. Aus diesem Grund sollte "ModRing" die Basisklasse für alle Restklassenringe sein, und für jede Methode sollten Unterklassen erstellt werden. Dadurch kann die Typprüfung fehlschlagen, wenn Sie versuchen, Zahlen mit verschiedenen Methoden zu berechnen. Setzen Sie außerdem "init" auf "@ abstractmethod", damit "ModRing" selbst nicht instanziiert werden kann.
ModRingType = TypeVar("ModRingType", bound="ModRing")
ModRingBaseType = TypeVar("ModRingBaseType", bound="EuclidianRing")
class ModRing(Ring, metaclass=ABCMeta):
@abstractmethod
def __init__(self: ModRingType, a: ModRingBaseType, n: ModRingBaseType) -> None:
self.a = a % n
self.n = n
def __repr__(self: ModRingType) -> str:
return "%s (mod %s)" % (str(self.a), str(self.n))
def __mul__(self: ModRingType, x: ModRingType) -> ModRingType:
return self.__class__(self.a * x.a)
def __add__(self: ModRingType, x: ModRingType) -> ModRingType:
return self.__class__(self.a + x.a)
def __neg__(self: ModRingType) -> ModRingType:
return self.__class__(-self.a)
def __eq__(self, x):
if not isinstance(x, self.__class__):
return NotImplemented
return self.a == x.a
def identity(self: ModRingType) -> ModRingType:
return self.__class__(self.a.identity())
def zero(self: ModRingType) -> ModRingType:
return self.__class__(self.a.zero())
Durch Festlegen von "self .__ class__" in jeder Methode können Sie auf eine Instanz einer untergeordneten Klasse mit einem Divisor verweisen, nicht auf die Restklasse.
Gehen Sie wie folgt vor, um eine Restringklasse mit einem Divisor von 5 zu erstellen:
class ModRing_5(ModRing):
def __init__(self, a: Integer) -> None:
super().__init__(a, Integer(5))
Lassen Sie uns nun die Funktion des Restrings überprüfen.
Erstens ist die Berechnung von Zahlen mit verschiedenen Methoden.
mr_3_5 = ModRing_5(Z(3))
mr_2_4 = ModRing_4(Z(2))
print(mr_3_5 + mr_2_4)
$ mypy ./field_extension.py
field_extension.py:238: error: Unsupported operand types for + ("ModRing_5" and "ModRing_4")
Ich habe einen Fehler in mypy. Wenn die Methode dieselbe ist, tritt kein Fehler auf und die Berechnung kann problemlos durchgeführt werden.
mr_3_5 = ModRing_5(Z(3))
mr_4_5 = ModRing_5(Z(4))
print(mr_3_5 + mr_4_5) # -> 2 (mod 5)
Von den Ringen haben andere Elemente als $ 0 $ ein inverses Multiplikatorelement, dh dasjenige, das die folgenden Bedingungen erfüllt, wird als Körper bezeichnet.
$ x \ star x ^ {-1} = x ^ {-1} \ star x = e $ existiert $ x ^ {-1} $
Bei Anwendung auf den Restklassenring ist das Finden der Ganzzahl $ p $, die die folgende Gleichung für $ a \ pmod n $ erfüllt, das inverse Element.
Aus der obigen kongruenten Definition unter Verwendung der Ganzzahl $ q $
Die Summe (Differenz) eines Vielfachen von $ a $ und eines Vielfachen von $ n $ ist ein Vielfaches der maximalen Verpflichtung $ GCD (a, n) $ von $ a $ und $ n $. Dies nennt man Bezoos Gleichung. Das heißt, $ GCD (a, n) = 1 $ (elementar zueinander).
Alle $ a $ kleiner als $ n $ und $ n $, die zueinander Primzahlen sind, sind Primzahlen. Wenn also $ n $ eine Primzahl ist, ist der Restklassenring das Feld. Dies wird als endlicher Körper bezeichnet, da es sich um einen Körper handelt, der aus einer endlichen Anzahl von Elementen besteht.
Sie können die euklidische Methode der gegenseitigen Teilung verwenden, um eine Menge von ganzen Zahlen $ p $, $ q $ und $ r $ zu finden, die die Bezu-Gleichung $ a p + b q = r = GCD (a, b) $ erfüllen.
Die euklidische Methode der gegenseitigen Teilung kann innerhalb des euklidischen Rings durchgeführt werden. Aus diesem Grund ist die euklidische Methode der gegenseitigen Teilung in der euklidischen Ringklasse implementiert.
Verwenden Sie im Typhinweis, wenn das Argument oder der Rückgabewert der Funktion ein Taple enthält, typing.Tuple und geben Sie den Typ jedes Elements in eckigen Klammern an.
from typing import Tuple
EuclidianRingType = TypeVar("EuclidianRingType", bound="EuclidianRing")
class EuclidianRing(Ring, metaclass=ABCMeta):
# ~~ snip ~~
def euclid_gcd(self: EuclidianRingType, b: EuclidianRingType) -> Tuple[EuclidianRingType, EuclidianRingType, EuclidianRingType]:
a = self
p = a.zero()
q = a.identity()
p_1 = a.identity()
q_1 = a.zero()
while True:
c = a % b
if c == c.zero():
break
p_2 = p_1
q_2 = q_1
p_1 = p
q_1 = q
p = p_2 - p_1 * (a // b)
q = q_2 - q_1 * (a // b)
a = b
b = c
return (p, q, b)
Nachdem wir die euklidische Methode der gegenseitigen Teilung implementiert haben, reduzieren wir sie mit der rationalen Zahl "init".
class Rational(Field):
def __init__(self: "Rational", p: Integer, q: Integer = Integer(1)) -> None:
_, _, r = p.euclid_gcd(q)
self.p = p // r
self.q = q // r
Lassen Sie uns nun eine endliche Körperklasse erstellen. Die Finite-Body-Klasse erbt von "ModRing" und definiert die "inverse" Methode. Das endliche $ n $ muss eine Primzahl sein, aber da es schwierig ist, genau zu bestimmen, dass es sich um eine Primzahl handelt, überprüfen wir sie beim Erstellen einer Instanz nicht und überprüfen uns nicht gegenseitig in "invers". Ich werde prüfen, ob es ist.
FiniteFieldType = TypeVar("FiniteFieldType", bound="FiniteField")
class FiniteField(Field, ModRing, metaclass=ABCMeta):
def inverse(self: FiniteFieldType) -> FiniteFieldType:
p, q, r = self.a.euclid_gcd(self.n)
if r == r.identity():
return self.__class__(p)
raise Exception("a and n are not co-prime")
Lass es uns testen.
class FiniteField_11(FiniteField):
def __init__(self, a: Integer) -> None:
super().__init__(a, Integer(11))
ff_5_11 = FiniteField_11(Z(5))
print(ff_5_11.inverse())
# -> 9 (mod 11)
Da $ 5 \ times 9 = 45 \ equiv 1 \ pmod {11} $ ist, ist die Umkehrung der Multiplikation von $ 5 \ pmod {11} $ sicherlich $ 9 \ pmod {11} $.
Das nächste Mal werden wir einen polymorphen Ring definieren und die Klassen "ModRing" und "FiniteField", die diesmal nur auf ganzen Zahlen basierten, auf Polynome anwenden. Und schließlich werden wir das Feld der rationalen Zahlen erweitern.
Recommended Posts