Das deutsche Python-Forum

Hi BlackJack,

Zu Deinem 2. Punkt: Wieso Flop
Das verstehe ich nicht ganz. Bei Dir ist der Rechner doch auch schon bei etwa 10**18 (999999999999999999) mit Fehlermeldung ausgestiegen!

Der letzte Punkt ist klar, aber mit Rabin-Miller werden Primzahlen konstruiert, er eignet sich aber nicht zum Primzahltest, sonst wären alle Verschlüsselungsverfahren unsicher.

Ich kopiere mal mein Programm, um es zur Diskussion zu stellen,
(Danke Leonidas, für Deinen Hinweis) :

Code: Alles auswählen

def isprime(aNumber):
    '''return True if the number is prime, false otherwise'''
    if aNumber < 2    : return False
    
    for k in (2,3,5,7) :
        if ((aNumber%k) == 0) : return False
    #
    
    k = 11
    list = (2,4,2,4,6,2,6,4,2,4,6)
    i = 0
    while i < len(list) :
        if ((aNumber%k) == 0) : return False
        k += list[i]
        i += 1
    #
    # Im folgenden Programmstück werden für die Modulo-Operation
    # nur Divisorenbenutzt, die keine Vielfachen von 2, 3, 5, 7 sind.
    kmax = int(aNumber**0.5)
    list = (6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,
            4,2,4,6,2,6,4,2,4,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6)
    lenlist = len(list)
    while True :
        i = 0
        while i < lenlist :
            if ((aNumber%k) == 0) : return False
            k += list[i]
            i += 1
        #
        if k > kmax : break
    #
    return True
#

Edit (Leonidas): Code in Python-Tags gesetzt.

benutze am besten die code-tags.
findest du im editor neben dem quote und bei den anderen buttons,,,

Leonidas hat geschrieben:
Bernd Jonsson hat geschrieben: Trotzdem würde ich das verbesserte Programm gern hier ins Netz stellen,
zur Diskussion, Anregung und zur Kritik. Wie und wo mache ich das?
Du kannst es entweder, wenn es nicht zu lang ist direkt hier rein stellen oder anderfalls einen Paste-Service verwenden. Mein Lieblingspaste ist inzwischen paste.e-scribe.com geworden, weil es mit Python gemacht ist

....und pygments nutzt

Bernd Jonsson hat geschrieben:Zu Deinem 2. Punkt: Wieso Flop
Das verstehe ich nicht ganz. Bei Dir ist der Rechner doch auch schon bei etwa 10**18 (999999999999999999) mit Fehlermeldung ausgestiegen!

Wenn ich mit einem Grafikprogramm kein Bild bearbeiten kann das die Grösse eines Fussballfeldes bei 4000dpi besitzt, dann heisst das nicht, dass das Grafikprogramm ein Flop ist. Es ist einfach nur das falsche Werkzeug für so eine Datenmenge.

Und "schon" bei 10**18? Es müsste eine Liste mit so vielen Elementen angelegt werden. Eine Liste enthält intern Zeiger auf ihre Elemente; so ein Zeiger ist auf 32-Bit-Plattformen 4 Bytes gross; der Speicherbedarf wäre also *mindestens* 4000 *Petabytes*!

Der letzte Punkt ist klar, aber mit Rabin-Miller werden Primzahlen konstruiert, er eignet sich aber nicht zum Primzahltest, sonst wären alle Verschlüsselungsverfahren unsicher.

Mit dem Miller-Rabin, den ich meine, werden Zahlen auf "ist (wahrscheinlich) Prim" getestet. Und das macht keine Verschlüsselungsverfahren unsicher. Der Knackpunkt dort ist eine sehr grosse Zahl in ihre Primfaktoren zu zerlegen, was etwas anderes als ein Primzahltest ist.

Ich kopiere mal mein Programm, um es zur Diskussion zu stellen, [...]

Indexvariablen die man dann auch noch selbst in ``while``-Schleifen "verwaltet" sind in "unpythonisch" weil man direkt über die Elemente von Listen und andere Containerobjekten iterieren kann. Die erste ``while``-Schleife kann man z.B. ganz einfach durch eine kürzere ``for``-Schleife ersetzen:

Code: Alles auswählen

    k = 11
    for i in (2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6):
        if aNumber % k == 0:
            return False
        k += i

In der zweiten Schleife könnte man die Erzeugung der Zahlen die nicht durch 2, 3, 5 und 7 teilbar sind, in eine Generatorfunktion auslagern und dann über die Elemente iterieren:

Code: Alles auswählen

from itertools import cycle

# ...

def divisors(start_k):
    k = start_k
    for step in cycle((6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4,
                       6, 2, 4, 6, 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2,
                       10, 2, 10, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6)):
        yield k
        k += step

# ...

    kmax = int(aNumber**0.5) 
    for k in divisors(k):
        if aNumber % k == 0:
            return False
        if k > kmax:
            break

Beim letzteren muss man in diesem speziellen Fall aber wohl abwägen ob die "hässlichere" Variante nicht die schnellere ist.

Hi BlackJack,

wieder etwas gelernt, danke für die Programmiertips. Bin halt noch ein Python-Newby.
Auch Dank für die Verschönerung meines Scripts!

Zu Punkt 1) sind wir uns im Grunde doch einig, denn der Algorithmus 410662 von gian paolo ciceri sollte eine Beschleunigung für Algorithmus 366178 sein, versagt aber wegen des range-Befehls und beim späteren Listenaufbau vorzeitig. Nur in einem engen Zahlenbereich ist er gegenüber dem Hauruckverfahren schneller. Und auch meine Lösung oben steigt nicht mit Fehler aus, einzige Hürde ist die Rechenzeit bei sehr großen Zahlen.

Zu Punkt 2) sind wir wir auch einer Meinung. Mein Primzahltest(und andere) versucht ja auch eine Zerlegung und endet beim ersten Erfolg, meldet den Faktor jedoch nicht. Die nachfolgende Faktorisierung ist dann ein Kinderspiel.

Nun muss ich doch noch einmal auf das ursprüngliche Problem:
"Virtueller Speichermangel Hängenbleiben in Dauerschleife"
zurückkommen

Habe den Algorithmus 366178/410662 aus Versehen noch einmal mit einer sehr großen Zahl n = 10**11 laufen lassen und bekam wie Du ordnungsgemäß den MemoryError beim Befehl "s = range(3,n+1, 2)".
Das heißt, bei mittelgroßen Zahlen wie n = 10**8 funktioniert der range-Befehl noch fehlerfrei, aber beim Aufbau der Liste im return-Befehl
"return [2] + [x for x in s if x]"
erfolgt der virtuelle Speichermangel ohne jede Fehlermeldung.

Frage: Ist das dann doch nicht ein Fehler des Python-Interpreters?
Gruß Bernd

Bernd Jonsson hat geschrieben:Zu Punkt 2) sind wir wir auch einer Meinung. Mein Primzahltest(und andere) versucht ja auch eine Zerlegung und endet beim ersten Erfolg, meldet den Faktor jedoch nicht. Die nachfolgende Faktorisierung ist dann ein Kinderspiel.

Bei Zahlen in der Grössenordnung von 10**300 dauert das Kinderspiel bloss ein paar Jahrzehnte.

Das heißt, bei mittelgroßen Zahlen wie n = 10**8 funktioniert der range-Befehl noch fehlerfrei, aber beim Aufbau der Liste im return-Befehl
"return [2] + [x for x in s if x]"
erfolgt der virtuelle Speichermangel ohne jede Fehlermeldung

Die Frage ist, ob Du nicht vielleicht ein bisschen ungeduldig warst.

Bei 10**8 erzeugt das Programm eine Liste mit Zahlen die mindestens 800 MB belegt. Das ``return`` baut dann eine zweite Liste mit den Primzahlen auf, indem alle 10**8 Elemente untersucht werden und eine Ergebnisliste aufgebaut wird, die nochmal mindestens 46 MB belegt (5761455 Primzahlen). Durch die Art wie neuer Speicher bei wachsenden Listen dynamisch angefordert wird, kann man aber auch ruhig das doppelte annehmen, zusammen also ca. 900 MB an Daten. Wie sieht's bei Dir mit Speicher aus? Bei mir (512 MB RAM) ist die Kiste einfach nur noch am Swappen, das fängt schon beim Anfordern der ersten Liste mit `range()` an.

Frage: Ist das dann doch nicht ein Fehler des Python-Interpreters?

Solange der virtuelle Speicher noch nicht wirklich zuende ist, würde ich nein sagen.

Solange der virtuelle Speicher noch nicht wirklich zuende ist, würde ich nein sagen.

Da ich nach einer der Endlosschleifen - abgebrochen mit AltGr F4 - den Windows-Fehler "virtueller Speichermangel" erhielt, kam der Abbruch nicht zu früh, was somit auf einen Windows- oder Python-Fehler hindeutet.
Meine Frage ist nun, ob man diesem Fehler weiterhin nachgehen sollte oder nicht.
Mir ist es ziemlich egal.
Eine weitere Frage wäre, ob der Fehler auch unter Python 2.5 auftritt? Habe es selbst nicht, könnte es mir aber besorgen lassen. (Habe nur langsames Modem)

Hier noch kurz die Daten meines Systems:
Siemens-Fujitsu Scaleo, Windows XP m. Service Pack 2, Pentium(R)4 2,53 GHz, 768MB.
Gruß Bernd

Bernd Jonsson hat geschrieben:
Solange der virtuelle Speicher noch nicht wirklich zuende ist, würde ich nein sagen.
Da ich nach einer der Endlosschleifen - abgebrochen mit AltGr F4 - den Windows-Fehler "virtueller Speichermangel" erhielt, kam der Abbruch nicht zu früh, was somit auf einen Windows- oder Python-Fehler hindeutet.

Ich sehe den Fehler immer noch nicht. Ich weiss das ist schwer zu widerlegen aber IMHO war das keine Endlosschleife.

Du könntest die Listcomprehension aus der ``return`` Anweisung ja mal in eine ``for``-Schleife umschreiben und in der Schleife die Zahlen auch ausgeben, dann sieht man ob der Interpretierer da wirklich hängebleibt oder das System einfach nur furchtbar langsam wird.

Oh,
da hast Du mir ja einen ziemlich unverdaulichen Brocken vorgelegt.
Ich habe vor das return-Statement eine Schleife gesetzt, in der alle Primzahlen(x<>0) des range() in eine Ergebnisliste kopiert werden.
Wegen der hohen Zahl der gefundenen Primzahlen drucke ich nach jeweils 1000 Primzahlen einen Punkt und nach jeweils 50000 einen Zeilenwechsel.
Die Primzahlen sind relativ schnell berechnet, aber an meiner Ausgabe hapert es, sie ist viel zu langsam. Aber jetzt hatte ich Zeit zum Denken!
Bei einer Zahl etwa 10**11 lief das Programm 1 oder 2 Minuten. Aber erst bei ca. 10**16 passiert der Hänger. Dann kann ich meinen Rechner 2 Monate nicht mehr nutzen!
Doch die Ausgabe-Schleife kriege ich mit meinem bescheidenen Python-Wissen nicht um eine, geschweige denn um fünf 10-er Potenzen schneller.
Gruß Bernd

kannst du nicht die ausgabe umleiten?
dann hast du später halt ne txt. du willst ja wahrscheinlich die sowieso nicht vom terminal aus weiterbenutzen...sonst kannst du auch eine eigene klasse machen, die die ausgabe in ein file umleitet und jede xte zahl printet, damit der user weiß, dass nohc was passiert osä.

Hallo murph,
Du hast meine Anfrage als erster beantwortet, Dir werde ich auch als Letzten antworten.
Ich bin nämlich die ewige Frotzelei hier im Forum leid!

Deine Idee mit der Text-Ausgabe funktioniert leider auch nicht, da einfach zu viele Daten anfallen würden, bis der Fehler (Systemaufhänger) auftritt. In dem fraglichen Programm, BlackJack hat es sich ja heruntergeladen (Algorithmus 410662 und 366178), gibt es quasi 3 Zahlenbereiche. Im ersten, bei kleinere Zahlen bis ca. 10**14 läuft alles prima, im dritten, bei Zahlen > 10**18 ebenfalls, aber mit ordnungsgemäßer Fehlermeldung.
Der zweite Bereich liegt irgendwo dazwischen.
Wie bereits ausdiskutiert verbraucht das Eratosthenes-Sieb für den range-Befehl eine Unmenge Speicherplatz und für die nachfolgende Listenoperation (im return-Befehl) fehlt - vielleich bei der 10-Mllionsten Primzahl - der Speicherplatz. Ich müsste möglicherweise 10000000 Daten speichern.

Es ist ja auch nicht nötig zu wissen, bei welcher Primzahl der Fehler auftritt. Die Zahl wäre auch von Rechner zu Rechner verschieden, sogar auf dem gleichen Rechner würde sie je nach Vorgeschichte verschieden ausfallen.

Es bräuchte nur einer aus der Python-Gemeinde das Programm mit entsprechenden Zahlen laufen zu lassen. Ich kann mir nicht vorstellen, dass der Fehler nur bei mir auftreten sollte.

Die Frage ist nur noch, ob dieser Fehler in Version 2.5 möglicherweise schon behoben ist? Dann könnte man das Problem auf sich beruhen lassen.

Für mich ist das Thema "Virtueller Speicher-Überlauf" hiermit abgeschlossen.

Gruß Bernd

Bernd Jonsson hat geschrieben:Es bräuchte nur einer aus der Python-Gemeinde das Programm mit entsprechenden Zahlen laufen zu lassen. Ich kann mir nicht vorstellen, dass der Fehler nur bei mir auftreten sollte.

Ich habe bei mir mal nicht gleich abgebrochen und auch eine Schleife geschrieben die mir jeden 10000 Index ausgibt.

Beim Zusammenstellen der Ergebnisliste ging dann das grosse Swappen los, die Platte war richtig schön beschäftigt. Grob geschätzt hätte das Ergebnis nach ca. 7 Stunden festgestanden. So lange wollte ich meiner Platte die Dauerbelastung nicht zumuten.

Das stützt meine These das es kein Hänger ist, sondern einfach nur sehr lange dauert. Also kein Fehler.

Das deutsche Python-Forum

Virtueller Speicher Überlauf