Teilbarkeitskriterium - Geschwindigkeit optimieren

[Nocta]

Guten Abend


Einfache Version des Posts: Kann ich in Python irgendwie Zahlen beliebig genau darstellen lassen? 1 + 1/10^x wird bei einem genügend großen x einfach zu 1 abgerundet.
Ich glaube aber, dass genauere Zahlen die Geschwindigkeit schon genügend beschleunigen könnten.



Jetzt folgt die kompliziertere Version, in der ich detaillierter erkläre, um was es geht.


Ich versuche eine Aufgabe bei Project Euler zu lösen, da ich aber weiß, dass man die Ergebnisse und Lösungswege möglichst nicht verraten soll, werde ich hier allgemein bleiben.

Ich habe ein Programm geschrieben, welches es mir erlaubt, eine Teilbarkeitsregel basierend auf der alternierenden oder nichtalternierenden Quersumme für jede beliebige Zahl, die teilerfremd zu 10 ist, zu errechnen.
Wie das geht, habe ich mir bei Wikipedia angeguckt: http://de.wikipedia.org/wiki/Teilbarkeit#Weitere_Regeln
genaues Zitat:

Will man für eine Zahl x eine Teilbarkeitsregel mit Quersummen aufstellen, so sucht man nach einem Vielfachen, das entweder 10^n − 1 oder 10^n + 1 für ein beliebiges n ist. Ist das Vielfache 10^n − 1, dann gilt die Teilbarkeitsregel „Eine Zahl ist genau dann durch x teilbar, wenn ihre nichtalternierende n-Quersumme durch x teilbar ist.“ Ist das Vielfache hingegen 10^n + 1, dann gilt die Teilbarkeitsregel „Eine Zahl ist genau dann durch x teilbar, wenn ihre alternierende n-Quersumme durch x teilbar ist.“

Diese Teilbarkeitsregel suche ich für alle Primzahlen bis zu einer gewissen Grenze, welche dem Programm vorher nicht bekannt ist.

Nun geht es ja erst mal darum, ein geeignetes n zu finden. Dies tue ich, indem ich die Zahl x mit einer Laufvariable multipliziere, so lange, bis ich zu einer Zehnerpotenz plus/minus 1 komme.
Also zu 9, 11, 99, 101, 999, 1001, ...

Hier der Code: http://pastebin.com/2dsn2HWs (Zeile 20-42 ist wichtig)
Es ist eigentlich nur die 2. Funktion wichtig, da sie die Teilbarkeitsregel findet, bzw eben das gesuchte n findet.
Ich weiß, es ist nicht schön und manche Dinge sind nicht "sauber" und "pythonisch" gelöst, aber darum geht es mir bei so einem "Wegwerfprogramm" nicht. Es soll ein mal funktionieren, dann weg damit

So jetzt zu meiner Frage, nach dem ich so lange geschwafelt habe:
Das Programm scheint einwandfrei zu funktionieren, aber es ist trotz meiner Optimierungsversuche zu langsam, da es sehr viele Primzahlen überprüfen muss.
Hat irgendjemand Verbesserungsvorschläge?

Meine Optimierung beruht darauf: Normalerweise müsste ich die Laufvariable i in der Funktion find_n(x) jedes mal um einen Schritt erhöhen, was bei Zahlen mit n=22 ziemlich lange dauern würde, da ich ja 10^22 Schleifendurchläufe für eine einzige Zahl hätte.
Daher versuche ich die Zahl i möglichst schnell, möglichst viel zu erhöhen, ohne dabei auf die nächste Zehnerpotenz zu kommen, da ich ja gerade dort meine Überprüfung ansetze, ob die Zehnerpotenz +- 1 ein Vielfaches von x ist.
Daher habe ich mir gedacht, ich erhöhe den Wert so weit wie möglich, bestenfalls auf das 20fache.
Da ich aber dann immer noch kleinere Abstufungen brauche, um nicht zwischen den Vielfachen, die im Programmcode durch die Variable k gekennzeichnet sind, lauter 1er Schritte zu machen, habe ich dann diese 1.01 und 1.0001 etc. noch eingefügt, was die Berechnungszeit aufs extremste verringert hat, wenn man die vorherige als Vergleich nimmt.
Immerhin sind 1/1000000000 von 10^22 trotzdem sehr sehr viel und erspart mir viele viele Schleifendurchläufe.
Leider gibt es eine gewisse Grenze, ab der Python einfach zu 1 abrundet, auch mit Decimals. Ich denke das würde mein Problem ansonsten schon beseitigen.

Nun ja, wer mir bis hier hin folgen konnte und es auch geschafft hat, sich in den Programmcode und die mathematische Grundlage einzuarbeiten: Respekt
Vielen Dank schon mal, ich hoffe jemand blickt hier durch und hat noch einen Tipp für mich.

Falls das hier zu kompliziert dargestellt ist, kann ich gerne noch mal einen Anlauf starten und mich noch mehr auf das wesentliche beziehen und ein paar Dinge genauer erläutern.
Ich kann auch versuchen, ein paar Fragen komplett von dem Problem loszulösen und in vereinfachter Form darzustellen.
Ich will natürlich nicht eure Intelligenz beleidigen, aber ich persönlich würde glaube ich nicht, ohne mir etwas länger Zeit zu nehmen, verstehen, worum es in diesem Post genau geht

PS: Wer mein Programm mal ausprobieren möchte, um sich einen besseren Überblick zu verschaffen, der sollte im unteren Teil, den ich als Hauptprogramm gekennzeichnet habe, einfach mal die Kommentare entfernen (jaja, ich weiß, __main__ wäre angebracht).
Einfach mal ein paar Zeilen ausgeben lassen und angucken

[BlackJack]

@Nocta: Ohne jetzt in die zweite Funktion tiefer eingedrungen zu sein: Hast Du eigentlich mal nachgemessen wo am meisten Zeit verbraucht wird? `prim()` ist ja sehr naiv implementiert. Davon abgesehen, dass man die innere ``for``-Schleife auch *abbrechen* sollte wenn `check` an `False` gebunden wird, sollte das auch mit weniger Tests auf Teilbarkeit gehen. Statt mit allen geraden Zahlen <√i zu testen, kann man sich zum Beispiel die bisher gefundenen Primzahlen merken und nur durch diese teilen.

[Nocta]

`prim()` ist ja sehr naiv implementiert.

Das Ding rennt schon recht schnell, vorerst muss ich das wohl nicht optimieren, aber ich werds im Hinterkopf behalten
Wenn ich nur `for i in prim()` aufrufe, läuft i ziemlich schnell durch, mir jedenfalls schnell genug.


Die Funktion find_n() verlangsamt das aber logischerweise ziemlich stark.
Die braucht teilweise für eine einzige Zahl schon eine deutlich wahrnehmbare Verzögerung in der Ausgabe, wenn ich die Funktion für eine Zahl mit einem großen n aufrufe.
zB:

Code: Alles auswählen

>>> find_n(71)
(Decimal('20.000000000000000000'), 'nicht alternierend')

Dort müssen beispielsweise auch über 1000 1er Schritte für i hingelegt werden und jedes mal wird dann auch ctx.log10 aufgerufen, was merklich ausbremst, wenn man es einfach mal so 1000 mal aufruft.
Deshalb ja die untere for-Schleife, um möglichst wenige dieser 1er Schritte machen zu müssen.
Da liegt also das eigentliche Geschwindigkeitsproblem: Ich rufe den Logarithmus zu oft auf.

Ich glaube aber, ich habe irgendeine ganz elementare Möglichkeit übersehen, wie man mit Mathematik, statt mit "Ausprobieren" auf das gesuchte n, oder zumindest auf die nächste Zehnerpotenz kommt.

Gibt es in Python vielleicht eine deutlich effizientere Möglichkeit, als das hier, um zu Prüfen, ob man bei einer 10er Potenz ist?

Code: Alles auswählen

a = ctx.log10(i*x + 1)
        b = ctx.log10(i*x - 1)
        if a == int(a):
            print (count)
            return a, "nicht alternierend"
        if b == int(b):
            return b, "alternierend"

[Anm. ctx = Context(prec=20)]

[numerix]

Ich bin nicht sicher, ob ich es richtig verstanden habe:
Du erzeugst aufeinanderfolgende Primzahlen bis zu einer noch unbekannten Grenze und möchtest für jede Primzahl p das kleinste n finden, so dass entweder (10**n-1) % p = 0 ist oder (10**n+1) % p = 0, richtig?

Edit: Gibt es für n eine Obergrenze?

Edit: Hilft das?

Code: Alles auswählen

pow10s = []

def newfind_n(p):
    i = 0
    for u,v in pow10s:
        i += 1
        if not u % p: return (i,"alternierend")
        if not v % p: return (i,"nicht alternierend")
    return (0,"not found")

def main():
    # precalc
    max_n = 5000 # max. Exponent fuer 10^n
    pow = 10
    for i in range(1,max_n):
        pow10s.append((pow-1,pow+1))
        pow *= 10
    # find min. n
    for p in prim():
        if p == 2 or p == 5: continue
        if p > 10000: break
        print(p,newfind_n(p))
main()

[Nocta]

Du erzeugst aufeinanderfolgende Primzahlen bis zu einer noch unbekannten Grenze und möchtest für jede Primzahl p das kleinste n finden, so dass entweder (10**n-1) % p = 0 ist oder (10**n+1) % p = 0, richtig?

Ja, ich glaube, so kann man das formulieren.
Im Programm gehe ich allerdings so vor, dass ich ein Vielfaches von x (die Laufvariable i) suche, für das der Logarithmus von i*x-1 bzw i*x+1 einen Integer zurückgibt.

Edit: Gibt es für n eine Obergrenze?

Weiß ich nicht, aber ich gehe nicht davon aus.


PS: Ich glaube ich habe einen Fehler im Programmcode:
find_n(71) ==> n=20
(10**20 - 1) % 71 ist aber nicht 0.
Ich habe vermutlich irgendwie eine 10er Potenz übersprungen und erst die nächste erwischt, oder so.
Zu viel wegoptimiert



Edit: Wow, dein Code ist aber schnell Scheint auch richtig zu sein, der bekommt zwar viel höhere Werte für n raus als ich, aber wie ich festgestellt habe, waren meine ja teilweise falsch. Irgendwo war da ein Fehler, obwohl ansonsten alle Werte mit Wikipedia übereingestimmt hatten.
Ich guck mir das jetzt mal genauer an, könnte aber sehr gut sein, dass der Code mir hilft - wenn er fehlerfrei ist
Vielen Dank schon mal.

[numerix]

Zu viel wegoptimiert

Nein, der Fehler ist, dass du künstlich eine Grenze von n=20 annimmst ... damit kommst du aber nicht sehr weit.
Alle Primzahlen, für die n>20 wäre, werden bei n=20 beendet ...

Edit:

Code: Alles auswählen

>>> (10**35-1)%71
0

[Nocta]

Ich hab aber auch schon n=22 oder so rausgehabt.
Wo habe ich die künstliche Grenze denn eingebaut? Ich muss wohl ausversehen irgendeinen Schwachsinn gemacht haben.

[numerix]

Hast du meinen Code oben ausprobiert? Hilft dir das?

[Nocta]

Also so wie es momentan ist, stellt es wohl noch ein Problem dar, dass das n begrenzt ist.
Ich habe momentan keine Lust auf das Problem, werde aber später oder morgen mal ein bisschen rumexperimentieren
Ich weiß aber nicht, ob deine Lösung schon schnell genug ist, oder ob ich vielleicht einen komplett anderen Ansatz für das Problem brauche.
Komische Aufgabe, in der man die ersten 40 Primfaktoren einer 10^9 stelligen Zahl aus 1en berechnen muss
Ich dachte, es wäre wie geschaffen für diese Aufgabe, wenn man die alternierende bzw nichtalternierende Quersumme für die Teilbarkeitsprüfung nimmt, da eine Kette aus 1ern da wirklich nicht so anspruchsvoll ist.

[BlackJack]

@Nocta: Euler-Probleme sind in der Regel so ausgelegt, dass man sie in sagen wir mal ≈5 Minuten ausrechnen (lassen) kann. Wenn man ein Programm hat, was Stunden oder gar Tage bräuchte, sollte man noch einmal über den Lösungsansatz nachdenken. Die Probleme sind als mathematische Herausforderungen gedacht, und nicht als Hardware-Leistungstests.

Oft ist es bei solchen Problemen leider so, dass man einen bestimmten Kniff kennen muss, um es effizient lösen zu können. Dann kommt man bei diesem Problem zum Beispiel auf einen Algorithmus, der nur ein paar Sekunden benötigt.

[Nocta]

Oft ist es bei solchen Problemen leider so, dass man einen bestimmten Kniff kennen muss, um es effizient lösen zu können. Dann kommt man bei diesem Problem zum Beispiel auf einen Algorithmus, der nur ein paar Sekunden benötigt.

Yep, ich dachte das könnte einer sein Vielleicht krieg ich das noch irgendwie mit dem Ansatz hin, mal gucken.
Eine andere Idee habe ich nicht, wie ich Primfaktoren einer 10^9 stelligen Zahl finden kann ...

[BlackJack]

@Nocta: Wie gesagt ist das oftmals ein Kniff den man einfach kennen muss. Eine Formel oder Identität, oder irgendeinen Zusammenhang. In diesem Fall wie man eine grosse Zahl, die in einem gewissen Zusammenhang zu R(10⁹) steht auf Teilbarkeit mit einem bestimmten Rest testet, ohne tatsächlich diese grosse(n) Zahl(en) ausrechnen zu müssen.