8-Bit-Nirvana Startseite  
?GRAPHICS TOO COLOURFUL ERROR IN 15800
[ Home | Index | Werbung | Forum | Flohmarkt | Gästebuch | Links | Info ]

8-Bit-Forum

"Re: Primzahlenproblem" von Thorsten Nickel
(12.1.2000, 08:28)

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

Bezugsnachricht: Re: Primzahlenproblem (Sascha Hoogen)
Antworten: Re: Primzahlenproblem (Sascha Hoogen)

[ Antwort schreiben | Übersicht | Thema ]

Sascha Hoogen schrieb am 11.1.2000, 22:18:40:

> > 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

ja fuer fuer die Datenstrukturen die Basic bereitstellt verhaelt
es sich bei dem wiederholten Ausschliessen von Teilern so.

(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. :)

fuer grosse Primzahlen durchaus, wenn der Ausschlauss der 5 an der
Einerstelle wirklich effizient implementiert ist.
fuer jede Primzahl laesst sich halt exakt angeben, wieviel
Teiler mit einer 5 an der Einerstelle getestet werden
(Groessenordnungsmaessig: (P^0.5)/5, p sei prim)

>
> > 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. ;)

es sei denn man es kostet nix die 5 wegzulassen, d.h man
erzeugt Teilerfolgen mit 1,3,7,9 and er Einerstelle, das
aber kostenneutral hinzubekommen ist in Basic schon raffiniert ;-)

>
> > (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.

naja, man koennte auch die wurzel nehmen vom Primzahlkandidaten und
und mit dem Testteiler vergleichen.
>
> > 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. :)

beliebig, beim 10er-System sparst du die 2 und 5, da 10=2*5,
mit jedem anderen halt andere weitere Teiler ...
ist fuer Basic aber in der Tat nur mit erneutem Overhead moeglich
(habs nie ausprobiert in Basic)

>
> > 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. ;))

naja, es ist die simelste Umsetzung, das laesst sich natuerlich
mit 2 gosub spruengen zu 2 im prinzip identischen algos effizient verkuerzen. Hast du einen, musst du die 1,3,7,9 berechnen, was teuerer
kommt als stumpf 2 auf den Testteiler drauf zu addieren

die gosub variante ist noch am effiezientesten, weil sie nix zusaetzliches kostet
>
> > 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)

tja, MOD als unterprogramm zu simulieren,ist aber tuerer als schlicht
2 zu addieren oder die gosub-variante (1,3, 7,9) zu verwenden

>
> 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.

yep , wenn man nur abtestet
>
> > 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... ;))))

a^n+b^n=c^n ist bekanntlich Phytagoras fuer n=2
alle erfuellende tripel a,b,c aufzuzaehlen ist simpel, gibt
eine schoene "Formel" oder halt brute force ;-)

fuer n>2 war seit einigen Hundert jahren fuer bestimmte n gezeigt
worden, dass keine Loesung existiert. Fermat gab im 16. Jhd. an einen
Beweis zu kennen, aber erst 1993/1994 konnte der Englaender Wiley
den endgueltigen Beweis erbringen, dass es keinen Loesung gibt

Als Schueler hab ich halt die Phytagoreischen Zahlentripel fix
runter programmiert und angenommen, dasses fuer n>2 auch Loesungen
gaebe... wenn der Zahlenbereich nicht so mickrig waere, liefe
mein Prog heute noch ;-)

Waehrend das n via professionelle Computersuche laengst in
unendliche (fuer PC´s) Spaheren hochgedrueckt worden war ...

sprich die Anzeichen , dass das Fermatproblem (a^n+b^n=c^n, fuer n>2)
wohl keine Loesung hat, waren mir schlicht nicht bekannt in den 80ern

Gruss Thorsten

ps:die Phytagoreischen Zahlen finden sich in jeder Formelsammlung

>
> 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 ]