| |
| Autor |
  Polynomdivision und Multiplikation umsetzen |
|
juergenX
Aktiv 
Dabei seit: 08.07.2019
Mitteilungen: 946
 |  Themenstart: 2020-12-20
|
Hi!
Kann jemand ein einfaches Programm schreiben oder eine Idee geben wie man Polynomdivision und Multiplikation in Q[X] oder Z{X] in eine beliebige Programmiersprache umsetzen kann, oder hat das schon mal gemacht?
Mit GGT Berechnung.
Ich meine nicht ein CAS wie Maple, sondern eher C, PHP, Pascal oder Pari?
Eine 3rd generation language.
Danke jeden Tip! Auch für dem euklidischen Algorithmus verwendbar.
man kann evtl. den Pseudocode aus
https://de.wikipedia.org/wiki/Euklidischer_Algorithmus als Vorlage nehmen.
EUCLID_OLD(a,b)
\sourceon txt
1 wenn a = 0 dann
3 Ergebnis = b
4 sonst
5 solange b ≠ 0
6 wenn a > b dann
8 a ← a- b
9 sonst
10 b ← b - a
11 //
12 //
13 Ergebnis = a
14 //
\sourceoff
|
 Profil
|
DerEinfaeltige
Senior 
Dabei seit: 11.02.2015
Mitteilungen: 3300
 | Beitrag No.1, eingetragen 2020-12-21
|
Polynommultiplikation und -division lassen sich mit dem bekannten Schulbuchalgorithmus implementieren.
Für die ggT-Berechnung sollte man wenn möglich die Operatoren für Ganzzahldivision bzw. Divisionsrest überladen.
Dann kann man den euklidischen Algorithmus und ähnliches ohne weitere Modifikation verwenden.
Hier ein Ausschnitt aus einer Quick-and-Dirty-Implementierung in Python:
\sourceon Python
class Polynom():
def __init__(self,lst=[]):
self.coeff = lst
def __getitem__(self,idx):
return self.coeff[idx]
def __str__(self):
# ...
def __repr__(self):
return str(self)
def __len__(self):
return len(self.coeff)
def __neg__(self):
return Polynom([-c for c in self.coeff])
def __add__(self,B):
if len(B) > len(self):
return B + self
C = [c for c in self.coeff]
for i in range(len(B)):
C[i] += B[i]
while C and 0==C[-1]:
C = C[:-1]
return Polynom(C)
def __sub__(self,B):
return self + (-B)
def __mul__(self,B):
C = [0] * (len(self) + len(B))
for i in range(len(self)):
for j in range(len(B)):
C[i+j] += self[i] * B[j]
return Polynom(C)
def __floordiv__(self,B):
Q = Polynom([])
R = Polynom([c for c in self.coeff])
while len(R)>=len(B):
e = len(R)-len(B)
M = Polynom([0]*e + [R[-1]/B[-1]])
Q += M
R -= M*B
return Q
def __mod__(self,B):
Q = Polynom([])
R = Polynom([c for c in self.coeff])
while len(R)>=len(B):
e = len(R)-len(B)
M = Polynom([0]*e + [R[-1]/B[-1]])
Q += M
R -= M*B
return R
def gcd(A,B):
if not B:
return A
return gcd(B,A%B)
>>> A = Polynom([-3,2,1])
>>> B = Polynom([3,1])
>>> C = Polynom([-1,1])*Polynom([2,2])*Polynom([1,4,1])
>>> A
1x^2 + 2x - 3
>>> B
1x + 3
>>> C
2x^4 + 8x^3 - 8x - 2
>>> gcd(A,C)
8.0x - 8.0
>>> gcd(B,C)
- 32.0
>>> gcd(A,B)
1x + 3
\sourceoff
|
Profil
|
ThomasRichard
Senior
Dabei seit: 08.04.2010
Mitteilungen: 476
Wohnort: Aachen
| Beitrag No.2, eingetragen 2020-12-21
|
Hallo Jürgen,
klar geht das, aber wozu der Aufwand?
Zu Studentenzeiten hatte ich mal an einer effizienten C-Implementierung von Kreisteilungspolynomen versucht (aus Interesse, nicht als Übungsaufgabe). Es wurde ein Riesenprojekt, fraß immer mehr Freizeit, und war auch nicht schneller als Maple.
Pari ist übrigens in deiner Aufzählung ein Sonderfall, denn es bietet ja schon Polynomarithmetik inkl. Division und ggT. Es ist auch keine universelle Programmiersprache.
[Die Antwort wurde vor Beitrag No.1 begonnen.]
|
Profil
|
juergenX
Aktiv
Dabei seit: 08.07.2019
Mitteilungen: 946
| Beitrag No.3, vom Themenstarter, eingetragen 2020-12-22
|
Ja Danke für die python implementation!
Dass das bei Pari schon drin ist, wusste ich nicht.
Eine Programmierung erscheint mir nützlich, da man (ich.. und nicht nur ich) sehr schnell verrechnet.
Finde ggt und Qouotient mit Rest
$X^5-4x^4+5x^3-2x+9 \div x^3+3x^2-8$
Eben noch dazu die nächtliche Idee: asoziiere Polynome aus $Z_{10}[X]$ wie $X^5-4x^4+5x^3-2x+9$ bzw. $x^3+3x^2-8$ mit positiven Integers hier $165089 \div 1302$.
Habe das eben noch nicht zu Ende gerechnet..so käme man weg von Polynomen zu Zahlenrechnungen. wenn diesr Ersatz ein bijektiver Homomorphismus ist.
einfacheres Beispiel $x^2+2x+1 \div x+1 = x+1$ bzw. $121 \div 11 = 11$
|
Profil
|
gonz
Senior
Dabei seit: 16.02.2013
Mitteilungen: 4955
Wohnort: Harz
 | Beitrag No.4, eingetragen 2020-12-23
|
Ich hätt da dieses zu bieten... (ist sozusagen ein rudiment):
\sourceon python
import numpy as np
from fractions import Fraction as frac
# (X5−4x4+5x3−2x+9)/(x3+3x2−8) test gg
poly_1 = [9,-2,0,5,-4,1]
poly_2 = [-8,0,3,1]
def div_rest(myPoly_1,myPoly_2):
for move in range(len(myPoly_1)-len(myPoly_2),-1,-1):
faktor=frac(myPoly_1[len(myPoly_2)+move-1]
,myPoly_2[len(myPoly_2)-1])
for stelle in range(len(myPoly_2)):
myPoly_1[stelle+move]-=myPoly_2[stelle]*faktor
rest=[]
for loop in range(len(myPoly_2)-1):
rest.append(myPoly_1[loop])
while len(rest)>1 and rest[len(rest)-1]==0:
rest.pop()
return rest
def ggT(myPoly_1,myPoly_2):
rest = div_rest(myPoly_1,myPoly_2)
if len(rest)<2:
if rest[0]==0:
return myPoly_2
else:
return 1
else:
return ggT(myPoly_2,rest)
print("Polynome :",str(poly_1)," vs. ",str(poly_2))
if len(poly_1)>len(poly_2):
print("ggT=",ggT(poly_1,poly_2))
else:
print("ggT=",ggT(poly_2,poly_1))
\sourceoff
|
Profil
|
viertel
Senior
Dabei seit: 04.03.2003
Mitteilungen: 27787
Wohnort: Hessen
 | Beitrag No.5, eingetragen 2020-12-23
|
\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
\quoteon(2020-12-22 18:57 - juergenX in Beitrag No. 3)
$X^5-4x^4+5x^3-2x+9 \div x^3+3x^2-8$
einfacheres Beispiel $x^2+2x+1 \div x+1 = x+1$ bzw. $121 \div 11 = 11$
\quoteoff
Du solltest dir angewöhnen, ordentlich Klammern zu verwenden.
Denn $a+b\div c+d$ ist gänzlich etwas Anderes als $(a+b)\div(c+d)$.
Das Erste ist $a+\frac{b}{c}+d$, hingegen das Zweite $\frac{a+b}{c+d}$.\(\endgroup\)
|
Profil
|
thureduehrsen
Senior
Dabei seit: 13.11.2007
Mitteilungen: 1780
Wohnort: Kiel, Deutschland
 | Beitrag No.6, eingetragen 2020-12-24
|
\(\begingroup\)\(\newcommand{\id}{\operatorname{id}}\)
Hallo juergenX,
\quoteon(2020-12-20 19:20 - juergenX im Themenstart)
Polynomdivision und Multiplikation in Q[X] oder Z{X]
\quoteoff
habe ich zufällig auf Platte rumliegen, mit Ansätzen für \(\mathbb Q[X]\).
Siehe hier (tar-Archiv einer Sammlung von Java-Klassen).
Copyright 2002-2020, Robert Sedgewick and Kevin Wayne (GNU GPL); meine eigenen Ansätze stammen aus den Jahren 2010 bis 2018.
Du kannst dich also nach Lektüre des Codes an der Implementierung des ggT versuchen.
Frohe Festtage!
mfg
thureduehrsen
\(\endgroup\)
|
Profil
|
juergenX
Aktiv
Dabei seit: 08.07.2019
Mitteilungen: 946
| Beitrag No.7, vom Themenstarter, eingetragen 2020-12-29
|
\quoteon(2020-12-23 23:29 - viertel in Beitrag No. 5)
\quoteon(2020-12-22 18:57 - juergenX in Beitrag No. 3)
$X^5-4x^4+5x^3-2x+9 \div x^3+3x^2-8$
einfacheres Beispiel $x^2+2x+1 \div x+1 = x+1$ bzw. $121 \div 11 = 11$
\quoteoff
Du solltest dir angewöhnen, ordentlich Klammern zu verwenden.
Denn $a+b\div c+d$ ist gänzlich etwas Anderes als $(a+b)\div(c+d)$.
Das Erste ist $a+\frac{b}{c}+d$, hingegen das Zweite $\frac{a+b}{c+d}$.
\quoteoff
Ja so ist es richtig:
$\displaystyle \large \frac {X^5-4x^4+5x^3-2x+9}{x^3+3x^2-8}$
Ich habe gerade zurück aus Weihnachts"urlaub" noch nicht die Idee des Ersetzens der Polynome aus $\displaystyle \large Z[X] \Leftrightarrow \mathbb Q_{+}$ weiterverfolgt, finde das aber eine interessante Idee:)
J
|
Profil
|
juergenX
Aktiv
Dabei seit: 08.07.2019
Mitteilungen: 946
| Beitrag No.8, vom Themenstarter, eingetragen 2020-12-29
|
\quoteon(2020-12-24 11:16 - thureduehrsen in Beitrag No. 6)
Hallo juergenX,
\quoteon(2020-12-20 19:20 - juergenX im Themenstart)
Polynomdivision und Multiplikation in Q[X] oder Z{X]
\quoteoff
Siehe hier (tar-Archiv einer Sammlung von Java-Klassen).
Frohe Festtage!
mfg
thureduehrsen
\quoteoff
Ja Danke
Ich habe gerade zurück aus Familien Weihnachtserholung Deinen Post gelesen und das .tar entpackt.
Früher hatte ich mal mit Java unter eclipse gearbeitet.
siehe
https://www.eclipse.org/downloads/packages/release/kepler/sr1/eclipse-ide-java-developers
Sogar eine Primzahlzerlegung beliebiger Integer etwas abgewandelt.
Modifiziert aus https://www.alpertron.com.ar/ECM.HTM
Es lohnt sich sicher, mal wieder daran/damit zu arbeiten.
J.
|
Profil
|
juergenX hat die Antworten auf ihre/seine Frage gesehen.
juergenX hat selbst das Ok-Häkchen gesetzt. |
|
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2023 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die
Nutzungsbedingungen,
die Distanzierung,
die Datenschutzerklärung und das Impressum.
[Seitenanfang]
|
Home / Seite ohne Frame
Wie unterstütze ich den Matheplaneten mit Geld?
