8-Bit-Nirvana Startseite  
?CPU MELTDOWN ERROR IN 52910
[ Home | Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info ]

8-Bit-Forum

"Re: Primzahlenproblem" von Sascha Hoogen
(11.1.2000, 22:18)

(Dieser Artikel wurde 1220 mal seit dem 16.10.2001, 22:56 aufgerufen)

Bezugsnachricht: Re: Primzahlenproblem (Thorsten Nickel)
Antworten: Re: Primzahlenproblem (Thorsten Nickel)

[ Antwort schreiben | Übersicht | Thema ]

Thorsten Nickel schrieb am 11.1.2000, 10:09:36:

> Auch muesste ein Primzahlkandidat nur mit ungraden Teilern getestet werden,
> wobei Teiler mit einer 5 an der Einerstelle gar nicht infrage
> kommen. (Warum ? ... ,....)

Guter Punkt, aber unter Basic dürfte der Einertest auf 2 und 5 länger dauern
als das sofortige Teilen durch die bereits errechneten Primzahlen (siehe
Listing 2 mit dem eigens dafür angelegten Array). Da die ersten Tests sowieso
die häufigsten Teiler (2, 3, 5 und 7) checken, wäre ein evtl. möglicher
Geschwindigkeitsgewinn wohl eher gering. Aber ich lasse mich durch ein
entsprechendes Listing gerne überzeugen. :)

> Nur ist eine Abfrage beim Teiler, ob eine 5 an der
> einer Stelle vorliegt genauso teuer, als wenn unnoetigerweise mit
> solch einem Teiler die Primzahl-eigenschaft getestet wird.

Hups, genau das wollte ich oben sagen. ;)

> (Einschub:
> Natuerlich muss auch nur bis zur Wurzel des Primzahlkandidaten
> getestet werden. Trick hier: quadriere den Teiler und schau, ob
> er grosser gleich ist dem Primzahlkandidaten.
> Bsp: 49=7*7, 21=3*7 )

Das ist allerdings eine geradezu geniale Verkürzung! :) Klar, Teiler
größer als SQR(Testzahl) muß man gar nicht erst berücksichtigen.

> Ausweg: kompletter Basenwechsel, weg vom Dezimahlsystem zu einem
> geeigneteren Zahlensystem, waehrend beim 10er-System die 2 und die 5
> unnoetig zu testen sind an der Einerstelle, kann man bei einem
> Basenwechsel daruber hinaus noch andere Teiler einsaparen...

Unter Basic leider keine Option, da das Umrechnen in ein anderes, evtl.
geeigneteres Zahlensystem (welches denn?) zuviel Rechenzeit verbraten
würde. Aber auch hier könnte mich ein entsprechendes Listing durchaus
vom Gegenteil überzeugen und tief beeindrucken. :)

> Bleibt man beim Dezimalsystem , so beobachtet man bei den notwendiger
> weise ungraden Teilern die zyklische sich wiederholende Folge 1,3,7,9
> (ohne die 5)
>
> von 1 nach 3 betraegt die Differenz 2 ,
> von 7 nach 9 betraegt sie ebenfalls 2,
> nur von 3 nach 7 ist sie 4 , da 5 als Einerstelle beim Teiler unsinnig
> ist.
>
> Mit einb bischen Knobeln bekommt man effiezienten Basic Code hin, dass das
> Einsparen der 5 nicht mit zusaetzlichem Rechenaufwand erkauft werden muss.
>
> einfachste Idee: haeng den Primzahlalgo 4 mal hintereinander.
> in den 4 Teilen werden jeweils die Teiler mit Einerstelle 1,3,7,9
> durchlaufen.

Igitt, wie unelegant! Mir stinkt schon das Verzichten auf FOR...NEXT und
IF...THEN aus Performancegründen. ;))

> moechte man das Primzahlprogramm nicht 4 mal hintereinander haengen,
> muss man die Teiler mit der Endstelle 1,3,7,9 berechnen ohne "zuviel"
> Rechenzeit zu verbrauchen.
>
> es geht..., ist aber raffiniert ;-)

Wenn eine Modulo-Funktion vorhanden ist, dann isses recht einfach:
I=I+2-2*(MOD(I/10)=3)

Andernfalls schätze ich jetzt mal rein intuitiv den Aufwand, um die 5
zu überspringen, höher ein als das zusätzliche Teilen durch 5.

> hach, waren das Zeiten , als sich Zahlentheorie noch so intuitiv
> angehen liess ...
>
> Gruss & viel Spass, den hat man damit wirklich :)

Kann ich nur bestätigen. :)

> Thorsten (, der mal das Fermatproblem fuer n>=3 versucht hat
> zu implementieren,huuua haha, lang ists´ her ;-)

Was ist denn das für ein Problem? Klingt ein wenig wie Ausschlag an
ungünstig gelegenen Körperteilen... ;))))

Tschö,
Sascha


Lesezeichen für diesen Beitrag: del.icio.us del.icio.us Bei Mister Wong speichern Mister Wong Seite bei LinkARENA speichern LinkARENA Digg it Digg Slashdot it Slashdot StumbleUpon StumbleUpon


Antwort schreiben

Hier kannst Du auf die angezeigte Nachricht antworten. Beachte bitte die folgenden Punkte:
  • Dieses Forum befasst sich ausschließlich mit 8-Bit-Computern und Videospielen, Artikel zu anderen Themen sind off-topic und unerwünscht (für Computer mit mehr als 8 Bit gibt es hier aber auch ein eigenes Forum). Wenn der Vorschreiber schon vom Thema abweicht und Du unbedingt antworten möchtest, dann schreibe ihm lieber per e-mail.
  • Schreibe bitte so, dass sich niemand beleidigt oder angegriffen fühlt, auch wenn der Vorschreiber sich bereits im Ton vergriffen haben sollte. Solche Sachen löst man eh besser privat per e-mail.
  • Im Eingabefeld wird der komplette Text zitiert. Kürze die Zitate bitte so weit wie möglich, damit unnötiger Ballast vermieden wird. Hinweise zu richtigem und falschem Quoting findest Du hier: learn.to/quote.
Name:
E-mail:
Betreff:
Antwort:
Klicke bitte das Feld links an, falls Du Antworten auf diese Nachricht auch per E-mail bekommen möchtest.


       

Achtung: "SPAMFALLE" heißt nicht ohne Grund so, keinesfalls benutzen!



Mozilla Sidebar Opera Sidebar RSS 0.91 Newsfeed RSS 2.0 Newsfeed Add to Google Add to MyYahoo Spam Poison
Mozilla Sidebar Opera Sidebar RSS 0.91 Feed RSS 2.0 Feed Add to Google My Yahoo! Spam Poison

[ Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info | Impressum/Datenschutz | News | Credits | Webmasters | Seitenanfang ]