Restklassen/Kongruenzen ausdünnen

Heute ist Stammtischzeit:
Jeden Donnerstag 20:30 Uhr hier im Chat.
Wer Lust hat, kann sich gerne beteiligen. ;)
  • Hallo raspbastler,

    hätte ich fast gemacht, meinen Quellcode hier hochzuladen. Dann gäbe es aber wieder Ärger mit den Oberen, die mir einstens verboten haben, Icon-Quellcode im Python-Unterforum zu posten.

    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

  • und die Anzahl der Elemente in {4,5,7,10,12,14,15,17,19,20,22,24,25,27,29,32 oder 34} interessiert Dich als Ergebnis?

    Wenn ja, dann habe ich was verstanden, was sich programmieren lässt.

    Genau. Denn ist diese Anzahl = 0 , wurden alle Restklassen und damit alle natürlichen Zahlen erfasst.

    Gnom : Der Zahlenraum wird nur größer, wenn sich das kgV ändert. Beispiel:

    Nach zweimaligem Durchlauf wurde [ [1,5], [1,7] ] geliefert. Also muss ich die Restklassen zwischen 1 und 35 wegstreichen.

    Im dritten Durchlauf kommt [3,5] dazu. Das kgV ändert sich nicht und im Gegenteil werden sogar jetzt mehr Restklassen als vorher gestrichen.

  • Schaut euch aber bitte einmal meinen Code an. Bei dem was ihr postet werde ich nicht mitreden können.

  • Da fällt mir auch gleich eine Frage ein. Ich habe die Funktion kgv nun ausgelagert:

    Code
    def kgv(liste):
        kgv = 1
        for element in liste:
            kgv = math.lcm(kgv, element)
        return kgv

    Wenn ich dieser Funktion jetzt eine Liste mit Teillisten oder Tupeln übergebe, wie sage ich dann, dass er sich jeweils das Element an zweiter Stelle anschauen /davon das kgv berechnen soll?

  • Hallo,

    entweder du nimmst den Index, also 'element[1]' oder, da du ja eh jedes mal 'kgv' überschreibst, bis du einmal durch die Liste bist, kannst auch auch eine Liste erstellen, die nur die zweiten Elemente enthält und die an 'lcm' übergeben. Entweder mit 'functools' wie __blackjack__ gezeigt hat (Er hat eine Tuple anstatt eine Liste verwendet) oder so wie ich das gemacht habe. Ich würde blackjack's Variante nutzen.

    Grüße

    Dennis

    🎧 With the music execution and the talk of revolution, it bleeds in me and it goes 🎧

  • Danke Dennis89 .

    Ich hätte es vorher erwähnen sollen, aber der Code soll möglichst >>intuitiv lesbar<< sein. Effizienz ist nicht Priorität. Insbesondere deshalb versuche ich auch, die Funktionen die ich benötige, selbst zu schreiben.

    Für das kgV habe ich das nun so erledigt:

    Code
    def kgv(liste, modulposition = 1):
        kgv = 1
        for element in liste:
            kgv = math.lcm(kgv, element[modulposition])
        return kgv

    In der Abgabe meiner Arbeit kann ich dann ja auch argumentieren, dass man diese Funktion universell nutzen kann (was mit anderen Funktionen sicher auch geht. Ich muss aber ja zeigen, dass ich das auch kann).

  • Gnom : Der Zahlenraum wird nur größer, wenn sich das kgV ändert. Beispiel:

    Klar. Aber du sagtest, KgV kann > 100.000.000 werden und selbst das ist klein, wenn man von Primzahlen mit 9 Mio Stellen spricht. In diesen Dimensionen wirst du mit Streichlisten nicht weit kommen. Was willst du also dann eigentlich erreichen?

    Oh, man kann hier unliebsame Nutzer blockieren. Wie praktisch!

  • Klar. Aber du sagtest, KgV kann > 100.000.000 werden und selbst das ist klein, wenn man von Primzahlen mit 9 Mio Stellen spricht. In diesen Dimensionen wirst du mit Streichlisten nicht weit kommen. Was willst du also dann eigentlich erreichen?

    Also, das Ziel ist, für ein vorgegebenes h eine Menge D zu finden, sodass für jeden Exponenten k ein p aus D existiert, sodass das Jacobisymbol ungleich eins. Dies ist nicht immer möglich.

    Wohl ist aber möglich, diese Menge soweit aufzubauen, dass zumindest (1-epsilon) aller Fälle abgedeckt werden.

    Angenommen, ich habe zumindest diejenigen Elemente aufgefunden, sodass alle Restklassen bis auf 0 mod 6 und 2 mod 6 gelöst werden können.

    Dann suche ich einfach eine Lösung für k = 2 (die gibt es). Wenn ich Glück habe, ist die Ordnung dieser Lösung 2 oder 3, denn dann ändert sich das kgV nicht und der Anteil der lösbaren Exponenten steigt von 2/3 auf 5/6.

    Wenn sich das kgV nun allerdings ändert, dann bekomme ich ja eine neue Restklasse. Im neuen "kgV" ist der Anteil der gelösten Exponenten dann 2/3 + (irgendwas).

    ich hoffe ich bekomme das möglichst gut ausgedrückt, ohne zu tief in die Zahlentheorie einzusteigen.

  • Hallo neuernutzer,

    es bleibt verdammt schwierig, als Mathematiker mathematisch Interessierten eine Problemstellung zu erläutern.

    Wir hatten Anfang der 80er Jahre einen Mathe-Prof. O.H., der hatte uns die Vektor-Multiplikation erklärt. Er sprang aus dem Stand auf den Labortisch im Hörsaal. Das war schon Respekt einflößend. Der eine Fuß stellte den ersten Vektor dar, der andere Fuß den anderen Vektor. Dann kam die Rechte-Hand-Regel zum Einsatz. Und einigen Studenten war klar, dass der resultierende Vektor vom Fuß in Richtung Kopf zeigen musste. Ich grübelte, warum er bloß diese Wahl für die Vektoren wählte - warum nicht in der anderen Reihenfolge?

    Er nahm die Antwort vorweg: "Jetzt verstehen sie auch, warum der erste Vektor dieser Fuß hier war. Hätte ich die Reihenfolge anders gewählt, wäre das Ergebnis aus Ihrer Perspektive zwar deutlich lustiger. Für mich als 60-jähriges Säugetier wäre das zwar machbar - aber mühsamer. Ich müsste einen Handstand machen, Kopf auf dem Tisch und die Füße würden in der Luft baumeln."

    Hallo Leroy Cemoi,

    hyle Vielleicht könnte man eine Ausnahme machen bzgl. icon code?

    nee, ich geb's auf. Dann müsste ja jemand einen Fehler von 2016 oder 2015 zugeben, dass es oftmals nicht gut war, dass KnowHow nicht einfließen konnte.

    Ich mache 'nen eigenen Thread mit meinem Code auf.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    2 Mal editiert, zuletzt von Andreas (2. März 2023 um 13:02)

  • neuernutzer Die `kgv()`-Funktion hat eine schlechte API. Von so einer Funktion würde man erwarten, dass sie das KGV von gegebenen Zahlen ausrechnet, wenn sie allgemein benutzbar sein soll. Dazu müsste man dann die Zahlen aber noch mal einzeln in Sequenzen verpacken, *und* auch noch die 0 als Index angeben, damit die Funktion dann die einzelnen Zahlen wieder aus den eigentlich unsinnigen zusätzlichen Sequenzen zu holen. Das das eine Liste mit Listen bei Dir ist, ist ja schon nicht mehr der allgemeine Fall, sondern eine Besonderheit von *Deinen* Daten.

    Einerseits gibt keinen Code der ”intuitiv” lesbar ist, man braucht immer Vorwissen, auf der anderen Seite sollten Mathematiker mit Funktionen höherer Ordnung kein Problem haben. `map()`, `filter()`, und `reduce()` sind die Grundlage von so ziemlich allen funktionalen Programmiersprachen, die ja deutlich näher an ”der Mathematik” dran sind, als prozedurale Sprachen. Die Funktionen heissen nicht immer genau so, aber diese drei Grundoperationen gibt es immer.

    Wenn Effizienz keine Rolle spielt, kann man auch einfach nur `math.lcm()` und einen Generatorausdruck als Einzeiler verwenden:

    Python
    kgv = math.lcm(*(modul for _, modul in liste))

    Die `ausduennen()`-Funktion hat auch eine schlechte API. Erstens ist dieser Indexkram unnötig flexibel. Das macht das einfach nur komplizierter und schwerer zu verstehen als notwendig ohne das man wirklich etwas gewonnen hat. Dann hat die Funktion ein Argument das entscheidet welches von *drei* total unterschiedliche Rückgabewerten zurückgegeben wird. Es ist dann schwer nachzuvollziehen was denn bei einem Aufruf denn nun konkret zurückgegeben wird, denn beim Aufruf kann dieses Argument ja auch wieder eine Variable sein, wo man erst einmal schauen muss wie die zustande kommt. Das dieses Argument entweder die Zahl 0 oder der Buchstabe "v" oder *irgend etwas anderes* sein kann, ist vollkommen willkürlich und nicht nachvollziehbar.

    “Dawn, n.: The time when men of reason go to bed.” — Ambrose Bierce, “The Devil's Dictionary”

  • Der Icon-Code im anderen Thema bringt ja nicht wirklich Neues. Der Icon-Quelltext zurück nach Python übersetzt sieht letztlich genau so aus wie das was hier auf der ersten Seite schon stand — nur noch ineffizienter was den Speicherverbrauch angeht als eine Liste mit 1en und 0en:

    Die Menge durch eine Liste ersetzt und das Beispiel läuft hier ca. 3× schneller und verbraucht nur 205 MB statt 2,2 GB Arbeitsspeicher. Und ich denke nicht, dass das schwerer verständlich ist:

    Mit einem Bitvektor sinkt der Speicherverbrauch für die Liste mindestens um den Faktor 8, dafür steigt die Rechenzeit — zumindest wenn der Bitvektor in Python implementiert ist, weil das berechnen der Bitpositionen und maskieren der Bits natürlich etwas mehr Zeit verbraucht als einfach eine 0 an einem Index zuzuweisen. Wobei man da wohl von der hier schon verwendeten BitVector-Klasse deutlich abraten sollte, denn das folgende Programm braucht damit bei mir 27 MB *mehr* Speicher als die Liste mit 1en und 0en und *deutlich* mehr Rechenzeit: 29× mehr als mit der Liste:

    “Dawn, n.: The time when men of reason go to bed.” — Ambrose Bierce, “The Devil's Dictionary”

  • Hallo neuernutzer,

    Hallo ihr beiden, danke für eure Antworten.

    Tell :Das ist nicht so leicht, da häufig auch Überschneidungen eintreten. Eine feste Formel gibt es da nicht.

    Na komm. Eine Formel gibt's da schon. Die ist sogar recht einfach.

    Du hast es mit durch das kgV nach oben beschränkte Mengen zu tun. Also handelt es sich um abzählbare Mengen, deren Größe sogar berechenbar ist.

    Die Formel lautet: Größe_Menge = Größe_Ausgangsmenge - Größe_Menge1 - Größe_Menge2 + Größe_Schnittmenge(Menge 1, Menge2). Ggf. iterativ anwenden.

    Größe _Ausgangsmenge beginnt bei kgV.

    Das ließe sich hier auch anwenden - solange es nur auf die Anzahl und nicht auf die Repräsentanten selber ankommt. Die Anzahl der Mengen ergibt sich als Quotient aus kgV und der jeweiligen Schrittgröße, mit der die Ausdünnung jeweils erfolgt.

    Damit ist dann auch die zeitintensive Ausdünnung (nur um die Anzahl der Restklassen zu erhalten) obsolet.


    Beste Grüße

    Andreas

    Ich bin wirklich nicht darauf aus, Microsoft zu zerstören. Das wird nur ein völlig unbeabsichtigter Nebeneffekt sein.
    Linus Torvalds - "Vater" von Linux

    Linux is like a wigwam, no windows, no gates, but with an apache inside dancing samba, very hungry eating a yacc, a gnu and a bison.

    2 Mal editiert, zuletzt von Andreas (5. März 2023 um 09:03)

Jetzt mitmachen!

Du hast noch kein Benutzerkonto auf unserer Seite? Registriere dich kostenlos und nimm an unserer Community teil!