Erweiterter euklidischer Algorithmus

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Kalira hat geschrieben:
numerix hat geschrieben:Dann nimm doch einfach die gepostete Lösung von yipyip - die liefert doch (u.a.) das von dir gewünschte Endergebnis.
Naja, das Problem ist einfach nur ich will nicht einfach etwas übernehmen.. ich will es verstehen! sonst bin ich nachher bei meiner Lehrerin aufgeschmissen...
Wo genau liegt denn jetzt das Problem? Beim Verständnis von Python oder beim Verständnis des Algos?
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

den Algorithmus kann ich ja man rechnet einfach den größten gemeinsamen Teiler von a und b raus.. formt alle Gleichungen zum Rest um und setzt dann die jeweiligen Zahlen die man in der ersten Gleichung also 1 = ... sieht durch vorherige Terme der Reste ein und das macht man so lange bis man wieder ne aussage hat von 1 = (irgendeine Zahl) * a - (irgnedeineZahl)*b

aber wie programmiere ich das ???? das ist das Problem ich kann mir das gar nicht vorstellen...

Bis jetzt sieht es ja so aus:

Code: Alles auswählen

a = 187
b = 115
c = a%b
modul = []
vielfach = []
rest = []
multi = [] 
while c > 0:
    print (a, "=", a//b, "*", b, "+", c)
    modul.append(a)
    vielfach.append(b)
    multi.append(a//b)
    rest.append(c)
    a = b
    b = c
    c = a%b
    if a%b == 0:
        break
    
print ("--------------------------------------------------------------------")

rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
        print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
        i = i + 1

print ("--------------------------------------------------------------------")
und es funktioniert auch für jede erdenkbare natürliche Zahl... also es rechnet mir den ggT aus und formt zu den Resten um...

nur jetzt weiß ich nicht mehr weiter
also das Programm muss mir ja jetzt nicht mehr die Rechenschritte angeben er soll mir jetzt einfach nur diese 2 Zahlen berechnen mit denen man a und b multipliziert und dann durch eine Subtraktion den Wert 1 der Gleichung erhält...

kannst du mir bitte einfach schritt für schritt erklären wie man das macht???
also erstmal wie man die schleife begrenzt und dann wie man dem Programm den Befehl gibt vorherige Zeilen einzusetzen...

für die größere Zahl, (also die ohne dem Minuszeichen) muss man ja stets den Term einsetzen der vor zwei Gleichungen berechnet wurde... für die vielfach Zahl, (also die Zahl mit dem Minuszeichen) muss man den Term in der nächsten Gleichung einsetzen...
also ist es für modul immmer i+2 und für vielfach stets i+1....

kann man das verwenden?

Liebe Grüße
Kalira
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Also an Deinem Code zumzudoktern bringt irgend wie nicht viel imho. Kannst Du mir mal nen Link zu dem Algo posten? Um welchen genau handelt es sich? Bei wikipedia finde ich nichts, was so auf Anhieb zu Deinem Code passt ;-)

Generell denke ich, dass mathematische Probleme sich i.a. sehr schön für den Programmier-Einstieg eignen, da häufig stark aus dem Pseudo-Code hervorgehen und diesem extrem ähneln. Außerdem sind mathematische Operatoren am Anfang auch meist eher verständlich, als andere ...
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

du versuchst die "stift und papier" variante des algos in ein programm zu pressen. will man einen algorithmus implementieren nimmt man sich den pseudocode her und implementiert den.

eweiterter euklid:

Code: Alles auswählen

b0 = b
n0 = n
t0 = 0
t = 1
q = n0 / b0 (abgerundet)
r = n0 - q * b0
while r > 0 do
    temp = t0 - q * t
	if temp >= 0 then temp = temp mod n
	if temp < 0 then temp = n - (( -temp) mod n)
	t0 = t
	t = temp
	n0 = b0
	b0 = r
	q = n0 / b0 (abgerundet)
	r = n0 - q * b0
if b0 != 1 then
	b hat kein Inverses modulo n
else
	b-1 = t mod n


rekursiv:

Code: Alles auswählen

extended_euclid(a,b)
  wenn b = 0
      dann return (a,1,0)
  (d',s',t') =  extended_euclid(b, a mod b)
  (d,s,t)  = (d',t',s' - floor(a/b)t')
  return (d,s,t)
http://www.kinderpornos.info
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Hallo Kalira,
schau Dir (noch)mal den 1. Algorithmus aus dem
Wikipedia Artikel an.
http://de.wikipedia.org/wiki/Erweiterte ... lgorithmus
(Rekursive Variante, aber keine Angst, rekursive Algorithmen
kommen bei der Berechnung nicht vor.)

Versuche, mit Bleistift und Papier diesen Algorithmus anhand
einiger Zahlenbeispiele nachzuvollziehen.

Dann solltest Du dich etwas vertraut mit Listen und Tupeln machen
und was man mit ihnen so alles in Python anstellen kann.

Danach schau Dir nochmal den Kern meines Programmes,
die Funktion 'get_ggt_equations()', an und versuche, den
Wikipedia-Algorithmus wiederzuerkennen.

Wenn Dir das dann alles etwas klarer wird, kannst Du
ja nochmal versuchen, es eigenständig zu implementieren.

(Das ist das, wozu ich Dir momentan raten würde.)

:wink:
yipyip
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi Leute,

Also was die mathematik angeht, so hab ich das verstanden, ich habs ja schon an ein paar Beispielen auf einem Blatt papier durchprobiert... also das ist kein Problem... mein Problem ist einfach nur, dass ich ganz ehrlich keine Ahnung von informatik habe :!: .. ich meine ich hatte es nie in der Schule und ich hab auch nie jemanden gehabt der mir mal so sachen über informatik erklärt hat oder mir gezeigt hat wie man das macht.. ich hab einfach nur internet seiten verwendet und logisch überlegt... nur jetzt hab ich einfach keine Zeit mehr um das so weiter zu machen denn ich muss schon nächste Woche Freitag abgeben und muss noch einen haufen dazu schreiben....
Also vielen Dank für die vielen Lösungen aber ich verstehe sie einfach nicht... wenn ich da so einen code bekomme dann blicke ich nicht durch weil ich so viele Abkürzungen nicht verstehe und so weiter...

daher yipyip kannst du mir bitte einfach nur den Teil raussuchen, der die wirkliche Erweiterung ist... also den Teil wo du dem Programm sagst, dass es die einzelnen Zahlen durch vorherberechnete Terme ersetzen soll...
und wenn es dir nichts ausmacht, dann kannst du mir bitte einfach nur jeden Schritt dazu erklären?? Also wie man darauf kommt, wie man anfängt, worauf man achten muss und so???? und vielleicht einfach nur in Wörtern dahinter schreibst was das Programm jetzt durch diesen Befehl machen soll....Denn sonst kann ich dir wirklich nicht mehr folgen :(

Vielen, vielen Dank
und liebe Grüße

Kalira

PS: ich kann leider erst wieder morgen schreiben!
yipyip
User
Beiträge: 418
Registriert: Samstag 12. Juli 2008, 01:18

Um Missverständnissen vorzubeugen:
Mein Programm macht keine Termersetzung
wie bei Numerix:

Du erhältst bei mir eine Augabe der Form:
> ggt.py 1234 24
Euclid Equations:
1234 = 24 * 51 + 10
24 = 10 * 2 + 4
10 = 4 * 2 + 2
4 = 2 * 2 + 0

Rest Equations:
0 = 4 - 2 * 2
2 = 10 - 2 * 4
4 = 24 - 2 * 10
10 = 1234 - 51 * 24

ggt Equations:
2 = 1 * 2 + 0 * 0
2 = 0 * 4 + 1 * 2
2 = 1 * 10 - 2 * 4
2 = -2 * 24 + 5 * 10
2 = 5 * 1234 - 257 * 24
Hatte das jetzt so verstanden, dass Dir diese
Art der Ausgabe, also ohne Termersetzung,
prinzipiell ausreicht.

Der für Dich wichtige Teil steht in
'get_ggt_equations()', der die Faktoren
für die obigen letzten 5 Gleichungen liefert.
(Ich mache Dir dann in Kürze noch eine
genau kommentierte Version.)

:wink:
yipyip
Zuletzt geändert von yipyip am Mittwoch 6. Mai 2009, 20:08, insgesamt 1-mal geändert.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7478
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

@Kalira: Wieso machst Du denn bitte schön eine Programmieraufgabe, wenn Du davon keine Ahnung hast und auch keine Vorbildung? Zudem wenn die eigentlich Aufgabe über das simple Implementieren des Algos hinausgeht? Evtl. wäre es da geschickter, das Thema noch zu wechseln ...
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Hallo Kalira,
Dein unvollendetes Programm, welches immerhin glatt durchläuft und die richtigen Ergebnisse liefert, finde ich für eine(n) Anfänger(in) sehr ordentlich. Man braucht auch gar keine tiefgehende Python-Kenntnisse, um es zu vollenden; ich bin da nicht der Meinung einiger anderer Forumsteilnehmer. (Aber dem Mathematikeer :-) ist ja nichts zu schwer) Die meisten Vorschläge im folgenden Code, den ich dir mit kollegialen Grüßen zusende, sind reine Schönheitskorrekturen:

Code: Alles auswählen

(a,b) = (187,115)  #Vorschlag
assert a%b>0  #Trivialfaelle verbleiben als Hausaufgabe

c = a%b
modul = []
vielfach = []
rest = []
multi = []
while c > 0:
#   print (a, "=", a//b, "*", b, "+", c) #unschoen bei Python_2.x
#   print  a, "=", a//b, "*", b, "+", c  #falsch bei Python_3.x
#   print( "%i = %i * %i + %i" %(a, a//b, b, c) )  #Vorschlag_1
    print( "%3i = %3i * %3i + %3i" %(a, a//b, b, c) )  #Vorschlag_2
    modul.append(a)
    vielfach.append(b)
    multi.append(a//b)
    rest.append(c)
    a = b
    b = c
    c = a%b
    if a%b == 0:
        break
   
print ("--------------------------------------------------------------------")

#Vorsicht: folgende Listen sind leer falls b%a==0 gilt!
rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
#   print (rest[i], "=", modul[i], "-", multi[i], "*", vielfach[i])
    print("%3i = %3i - %3i * %3i" %(rest[i],modul[i],multi[i],vielfach[i])) #V
    i = i + 1

print ("--------------------------------------------------------------------")

ggn = rest[0]
(multA,zahlA, multB,zahlB) = (0,0, 1,ggn)

i = 0
while len(rest) > i:
    #Tupel werden komponentenweise zugewiesen:
    ( multA, zahlA,  multB, zahlB ) = (
        multB, modul[i],  multA-multB*multi[i], vielfach[i] )
    print("%3i = (%3i) * %3i + (%3i) * %3i" %(ggn, multA,zahlA, multB,zahlB))
    i = i + 1
Viel Vergnügen beim Entziffern!
Zuletzt geändert von Goswin am Donnerstag 7. Mai 2009, 08:37, insgesamt 2-mal geändert.
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

derdon hat geschrieben:Zeile 24 und 38 würdest du so lassen? Die stechen mir beim Überfliegen als erstes ins Auge.
Ich denke, das sollen sie doch gerade!
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

So kann man es natürlich auch sehen. Ich meinte, das mir bei den Zeilen sofort etwas wie

Code: Alles auswählen

print('-' * 68)
einfiel.
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

ich habe mal den rekursiven algo implementiert.
vorteil: hier kann man viel natürlicher die rechenschritte darstellen.
nachteil: evtl. schwer verdaulich, da rekursiv.

Code: Alles auswählen




def extended_euclid(a, b):
    if b == 0:
        print "\nggT: %d\nFinde jetzt Linearkombination des ggT aus Ausgangszahlen:\n" % a
        return a, 1, 0
        
    else:
        print "%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d" % {"a":a, "faktor":a/b, "b":b, "a_mod_b":a%b}
        
        d_, s_, t_ = extended_euclid(b, a % b)
        d, s, t = d_, t_, s_ - (a/b) * t_
        
        print("%(d)d = %(s)d * %(a)d + %(t)d * %(b)d") % {"d":d, "s":s, "a":a, "t":t, "b":b}
        
        return d, s, t

Code: Alles auswählen

>>> extended_euclid(99, 78)
99 = 1 * 78 +  21
78 = 3 * 21 +  15
21 = 1 * 15 +  6
15 = 2 * 6 +  3
6 = 2 * 3 +  0

ggT: 3
Finde jetzt Linearkombination des ggT aus Ausgangszahlen:

3 = 0 * 6 + 1 * 3
3 = 1 * 15 + -2 * 6
3 = -2 * 21 + 3 * 15
3 = 3 * 78 + -11 * 21
3 = -11 * 99 + 14 * 78
(3, -11, 14)
http://www.kinderpornos.info
BlackJack

Verbesserungsvorschlag für's einsetzen der Werte in die Zeichenketten:

Code: Alles auswählen

def extended_euclid(a, b):
    if b == 0:
        print ('\nggT: %d\n'
               'Finde jetzt Linearkombination des ggT aus Ausgangszahlen:\n'
               % a)
        return a, 1, 0
    else:
        faktor, a_mod_b = divmod(a, b)
        print '%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d' % locals()
        
        d_, s_, t_ = extended_euclid(b, a % b)
        d, s, t = d_, t_, s_ - (a/b) * t_
        
        print '%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals()
        
        return d, s, t
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

wow, sehr hübsch! was es nicht alles gibt.
richtig sexy langsam der code :)
http://www.kinderpornos.info
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

:D my cody isch nosch mehr sexxi: :D

Code: Alles auswählen

def extended_euclid(a, b):
  #liefert (ggt, mul_a, mul_b) mit ggt==mul_a*a+mul_b*b

  if b==0:
    print( "\nggT = %(a)d" %vars() )
    print( "Linearkombination des ggT aus Ausgangszahlen:\n" )
    #
    return (a, 1, 0) #a==1*a+0*b
   
  else:
    (faktor, rest) = divmod(a,b)  #a==faktor*b+rest
    print( "%(a)4d  = %(faktor)4d * %(b)4d   +  %(rest)4d"%vars() )
    #
    (ggt, inn_mul_a, inn_mul_b) = extended_euclid(b, rest)  #innere mul
    (mul_a, mul_b) = (inn_mul_b, inn_mul_a-faktor*inn_mul_b)
    print("%(ggt)4d  =  (%(mul_a)4d) * %(a)4d  +  (%(mul_b)4d) * %(b)4d"%vars())
    #
    return (ggt, mul_a, mul_b) #ggt==mul_a*a+mul_b*b


(a,b) = (374, 230)
extended_euclid(a, b)
Benutzeravatar
Dill
User
Beiträge: 470
Registriert: Mittwoch 10. Januar 2007, 14:52
Wohnort: Köln

mehr rundungen hat deiner auf jeden fall :shock:
ich steh aber auf weniger üppig.
in meiner neuen version verschwinden jetzt die hilfsberechnungen in print() und trüben so nicht den blick auf den eigentlichen algo :)
(und: ich bleibe bei den namen aus der wikipedia wo ich den algo herhabe)

Code: Alles auswählen

def extended_euclid(a, b): 
    if b == 0: 
        print('\nggT: %d\nggT:= Linearkombination(Ausgangszahlen):\n' % a) 

        return a, 1, 0 

    else: 
        print('%(a)d = %(faktor)d * %(b)d +  %(a_mod_b)d' 
        	% dict({"faktor":a/b, "a_mod_b":a%b}, **locals())
        )
        
        d_, s_, t_ = extended_euclid(b, a % b) 
        d, s, t = d_, t_, s_ - (a/b) * t_ 
        
        print('%(d)d = %(s)d * %(a)d + %(t)d * %(b)d' % locals())
        
        return d, s, t
http://www.kinderpornos.info
Kalira
User
Beiträge: 14
Registriert: Mittwoch 29. April 2009, 11:10

Hi Leute^^

Also erst mal danke für die Verbesserungsvorschläge und Dill, versteh mich nicht falsch aber ich glaub ich verstehe den Algo von Goswin etwas besser :wink:

Also Danke ich hab das jetzt auch ein bisschen schöner gemacht, so dass es jetzt so aussieht:

Code: Alles auswählen

a = 9013
b = 1556
g = a
h = b
c = a%b
modul = []     
vielfach = []  
rest = []
multi = [] 
while c > 0:
    print ("%d = %d * %d + %d" % (g, g//h, h, c))
    modul.append(g)
    vielfach.append(h)
    multi.append(g//h)
    rest.append(c)
    g = h
    h = c
    c = g%h
    if g%h == 0:
        break
    
print ("--------------------------------------------------------------------")

rest.reverse()
modul.reverse()
vielfach.reverse()
multi.reverse()

i = 0
while len(rest) > i:
        print ("%d = %d * %d + %d" % (rest[i], modul[i], multi[i], vielfach[i]))
        i = i + 1

print ("--------------------------------------------------------------------")


g = a
h = b

def extgcd(a, b):
    c=b 
    u=1
    s=0
    while b>0:
        q=a//b
        a, b = b, a-q*b
        u, s = s, u-q*s
    if u < 0:
        u = u + c
    return u

d = extgcd(h, g)

print ("d = ", extgcd(h, g))
print ("b = ", b)
print ("a = ", a)
print ("(d * b) % a = ", (d*b)%a)
und vielen Dank yipyip, jetzt hab ich endlich mal verstanden, was du die ganze Zeit mit Wikipedia gemeint hast.. ich hab das gar nicht gesehen, dass die das so da berechnet haben!

Also es funktioniert jetzt endlich :)
und es sieht hoffentlich nicht mehr alzu "unschön" :wink: aus

Liebe Grüße
Kalira
Benutzeravatar
Goswin
User
Beiträge: 363
Registriert: Freitag 8. Dezember 2006, 11:47
Wohnort: Ulm-Böfingen
Kontaktdaten:

Aha, BAHNHOF!


@Kalira: Deine Aufgabestellung (was dein extgcd(a,b) ausgibt) ist offenbar NICHT, was andere Leute unter dem "Erweiterten Euklidschen Algorithmus" verstehen, sie geht wohl mehr in Richtung eines "Mysteriösen Kaliraschen Algorithmus".

Ich denke, die Forumsteilnehmer haben nach all diesem Aufwand schon ein Recht auf eine mathematische Beschreibung von was GENAU du die ganze Zeit über gesucht hast; dazu brauchst du ja kein Python, nur Deutsch und Mathe. Du wolltest lineare Ausdrücke in andere lineare Ausdrücke einsetzen, aber MIT WELCHEM ZIEL? Nur Python lernen war es wohl auch nicht auch nicht so ganz.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Meine Euclid()-Implementation liefert für

Code: Alles auswählen

e = Euclid(9013, 1556)
print e.steps
print e.extended
diese Ausgabe:

Code: Alles auswählen

9013 = 5·1556+1233
1556 = 1·1233+323
1233 = 3·323+264
 323 = 1·264+59
 264 = 4·59+28
  59 = 2·28+3
  28 = 9·3+1
   3 = 3·1+0

1 = 1·28-9·3
  = 1·28-9·(59-2·28) = 19·28-9·59
  = 19·(264-4·59)-9·59 = 19·264-85·59
  = 19·264-85·(323-1·264) = 104·264-85·323
  = 104·(1233-3·323)-85·323 = 104·1233-397·323
  = 104·1233-397·(1556-1·1233) = 501·1233-397·1556
  = 501·(9013-5·1556)-397·1556 = 501·9013-2902·1556
Da weiß man wenigstens, was man hat ...
Antworten