Jacobisymbol: effiziente Implementierung |
21.12.2022, 17:10 | Malcang | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Jacobisymbol: effiziente Implementierung ich grüble aktuell an einer effizienten Implementierung des Jacobisymbols. Ich habe dazu zwar bereits viel gesucht, aber noch nicht das Richtige gefunden. Mir fällt das Thema leider auch immer wieder schwer, daher frage ich um euren Rat. Ich habe bisher folgendes gemacht (jeweils programmiert in phyton): Eine Funktion prime_decomp(n), die mir für die Liste
ausgibt. (Hier achte ich aktuell nicht auf Effizienz, daher habe ich den Code hier nicht geschrieben). Eine Funktion isprime(n), welche mir zwei Werte zurückgibt. True bzw. False, falls die Zahl prim ist bzw. zusammengesetzt, und die Liste der Teiler aus prime_decomp(n). So, dann habe ich eine Funktion zur Berechnung des Legendresymbols. Dies funktioniert nur wenn eine Primzahl ist. Berechnet wird dann das Euler-Kriterium:
Diese Codes funktionieren auch. Was mir Sorgen macht, ist der folgende Code:
Das funktioniert aber noch nicht. Die Eingabe
Kann mir jemand helfen? |
||||||||||||||||||||||
21.12.2022, 19:06 | IfindU | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Der Code ist in einer Endlosrekursion gefangen. Am Ende der Funktion ruft er die Funktion noch einmal auf: mit den gleichen Werten verdreht. Am Ende setzt du wegen und rufst dann wieder die Funktion auf, diesmal mit 0 als zweites Argument. Dafür ist Jacobi nicht definiert. Ich würde ganz oben eine Prüfung einbauen, ob ist. Wenn ja, dann die Jacobi einfach 0. Ansonsten sieht das nach einer guten Erklärung aus: https://planetmath.org/calculatingthejacobisymbol. Damit du besseres Gefühl hast, was deine Funktion macht: nutze einen Debugger oder gib dir aus, wo er ist: Ganz am Anfang print("Ich starte Jacobi-Berechnung mit den Werten a = .. und n = ... "). Dann siehst du was er macht und erkennst schneller wenn er was seltsames macht. |
||||||||||||||||||||||
22.12.2022, 12:13 | Malcang | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Hallo IfindU, vielen Dank für die Hinweise. Ich habe den Code mit einigen Sätzen versehen:
Nun muss ich aber noch den Fall unterbringen, dass der Zähler eine gerade Zahl ist. Da bastle ich gerade noch dran. Edit: Ich habe nun folgenden Code, der auch zu funktionieren scheint. Jedenfalls habe ich es mit einigen Werten ausprobiert und mit denen von wolframalpha verglichen.
|
||||||||||||||||||||||
22.12.2022, 15:11 | IfindU | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Du kannst ja mal die Funktion hier nehmen: Link. Und einfach mal 1000 random-Werte für deine und die andere Funktion einsetzen und schauen, ob immer das gleiche rauskommt. Edit: Oder einfach die Library nutzen: SymPy |
||||||||||||||||||||||
22.12.2022, 23:35 | Malcang | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Die hatte ich schonmal ausprobiert, machte mir aber auch Probleme, wenn ich auch gerade nicht mehr weiß, was genau
Das ich da nicht drauf gekommen bin Die nehme ich auch ab jetzt. Danke für die geduldige Hilfe! |
||||||||||||||||||||||
23.12.2022, 12:37 | IfindU | Auf diesen Beitrag antworten » | ||||||||||||||||||||
Schön, dass es geklappt hat Ich hoffe nur, du hast es implementiert, weil du es üben/verstehen wolltest und nicht, weil du es einfach gebraucht hast und einfach die Bibliothek mit allen diesen Funktionen übersehen hast |
||||||||||||||||||||||
Anzeige | ||||||||||||||||||||||
|
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|