devshare.de - Primzahlcheck

Re: Primzahlcheck

dummy@example.com (HAL9000) — Thu, 07 Mar 2002 23:16:00 +0000

das schnellste um primzahlen effektiv und in unbegrenzter Größe zu berechnen ist

1. sich eine ASM-Anwendung zu schreiben
2. nur register und keine Variablen für die eigentlichen Rechenoperationen verwenden
3. sich von einem zweiten Prozessor während der Berechnungen möglichst viele Priemzahlen schicken lassen (die höchsten die berechnet wurden, sich aber unter der Wurzel der nächsten zu berechnenden Zahl befinden)

Punkt 3 kann natürlich nicht jeder, aber auch ohne Punkt drei ist man mit dieser Methode um ein vielfaches schneller als mit Fortran, c oder anderen hohen Sprachen.

Gerade Zahlen nicht überprüfen (das sollte wohl eh klar sein, oder?)
Zahlen deren Quersumme durch drei teilbar sind sind auch selbst durch drei teilbar.
Ich glaube daß es da noch ein paar solche schmähs gibt.

Re: Primzahlcheck

dummy@example.com (braveheart) — Thu, 07 Mar 2002 17:33:00 +0000

Ich geh das mal ab...

Zitat:
1. sich eine ASM-Anwendung zu schreiben

- nuja, bei nem guten Compiler bringt das wenig und macht viel Mehraufwand. Manchmal wird C als eine Art Makro-Assembler angesehen...

Zitat:
2. nur register und keine Variablen für die eigentlichen Rechenoperationen verwenden

- das is klar, aber nich immer unbegrenzt möglich, in C bspw. gibt es das "register", das bei Möglichkeit auf ein Register umsetzt.

Zitat:
3. sich von einem zweiten Prozessor während der Berechnungen möglichst viele Priemzahlen schicken lassen (die höchsten die berechnet wurden, sich aber unter der Wurzel der nächsten zu berechnenden Zahl befinden)

- naja, du hast selten die Möglichkeit, das allein zu entscheiden. Habe du lieber das richtige OS (Unix/Linux, dev0 würde aber für Windows NT plädieren *g*) und setze Threads ein, die dann ja auch verteilt werden können.

Zitat:
Punkt 3 kann natürlich nicht jeder, aber auch ohne Punkt drei ist man mit dieser Methode um ein vielfaches schneller als mit Fortran, c oder anderen hohen Sprachen.

- jetz übertreib mal nich *g*, vielleicht 1,7 so schnell, aber so viel schneller als C... kaum möglich. (Ausser du bist ein Ultra-Maesto-ASM-Coder...)

Zitat:
Gerade Zahlen nicht überprüfen (das sollte wohl eh klar sein, oder?)

- BLÖDSINN. Wenn ich sowieso als erstes zwei überprüfe, macht das keinen Unterschied.

Zitat:
Zahlen deren Quersumme durch drei teilbar sind sind auch selbst durch drei teilbar.
Ich glaube daß es da noch ein paar solche schmähs gibt.

- theoretisch wahr, aber bis du die Zahl in in nen "String" (im numerischen Sinne, einfach ein Polynom) und von dem dann die Quersumme hast, hast du zehnmal Modulo gemacht.

Nichtsdestotrotz bin ich froh, dass manche sich trotz meiner Kommentare "trauen" etwas zu dem Thema hier zu äussern.

Re: Primzahlcheck

dummy@example.com (braveheart) — Sun, 03 Feb 2002 18:14:00 +0000

Code:


 for (i = 2; i < max; i++)
   arr[i] = i;
 for (i = 2; i < max; i++)
   for (j = 2*i; j < max; j += i)
     arr[j] = 0;
 for (i = 2; i < max; i++)
   if (arr[i])
     printout(arr[i]);

Re: Primzahlcheck

dummy@example.com (braveheart) — Sun, 03 Feb 2002 18:04:00 +0000

tut mir leid, aber deine Methode ist doch Blödsinn ... ob ich die Zahlen in einem if teste, oder ob ich n for bemühe ist doch herzlich egal! daher: (das ist die beschissenste Methode)

Code:


 pz = true;
 for (i = 2; i <= intsqrt(zahl); i++)
   if (zahl % i) {
     pz = false;
     break;
   }
 /*
 pz ... true - prim / false - unprim
 intsqrt(x) ist eine Funktion wie Math.floor(Math.sqrt(x)) bzw. (int)sqrt(x)
 */

[ 03.02.2002: Beitrag editiert von: whitehouse ]

Re: Primzahlcheck

dummy@example.com (Robert2718) — Sat, 02 Feb 2002 14:07:00 +0000

Hallo !

Zu meiner vorigen Antwort eine Korrektur. Ich habe mir die div. Links nicht angeschaut.

Ich hätte eine weitere Idee den Algorithmus zu verbessern. Im Unterschied zu meinem Programm, wo ich eine Zahl in ein Formular eingebe, bräuchtest du von Anfang an nur die Zahlen zur Überprüfung heranziehen, die nicht durch 2, 3 und 5 teilbar sind. Da es sich ja um sehr viele Zahlen handelt, könnte man die Zahlen, die durch 7, 11, 13, usw. teilbar sind auch von vorneherein überspringen.
Bei der Zahl durch die du dividierst gehts du genauso vor. Und dividieren bräuchtest du die Zahl überhaupt nur durch die bereits gefundenen Primzahlen, hat aber wohl nur dann einen Sinn, wenn sie noch im Hauptspeicher sind und nicht von der Datei gelesen werden müssen.

mfG Robert

Re: Primzahlcheck

dummy@example.com (Robert2718) — Sat, 02 Feb 2002 13:00:00 +0000

Hallo !

Ich weiss nicht, ob ich dir damit helfe, weil ich die div. Links für die Primzahlen, die in diesem Forum genannt wurden angeschaut habe, aber vielleicht ja doch.
Ich habe ein Primzahlenprogramm unter http://members.chello.at/robert.weixelb … zahlen.htm welches nicht nur die geraden Zahlen beim Primzahlentest überspringt, sondern auch die die durch 3 und 5 teilbar sind. Dieses Programm sollte exakte Ergebnisse liefern. Für sehr grosse Primzahlen kann man den Primzahltest von Rabin verwenden, den ich allerdings nicht näher kenne. Er liefert aber keine exakten Ergebnisse, sondern sagt nur aus, das eine Primzahl mit sehr hoher Wahrscheinlichkeit eine Primzahl ist.

mfG Robert

Re: Primzahlcheck

dummy@example.com (braveheart) — Sat, 26 Jan 2002 23:53:00 +0000

axo, ich kannte den Begriff nur nicht, das heisst also, die Nullstelle von f ist x für das f(x) = 0
für f(x) = mx ist sie natürlich 0 und für f(x) = mx + c ist sie -c/m
Beweis:
f(x) = 0
mx + c = 0
mx = -c
x = -c/m

für f(x) = c:
f(x) = 0
c = 0
also entweder allgemeingültig oder inkonsistent

[ 26.01.2002: Beitrag editiert von: whitehouse ]

Re: Primzahlcheck

dummy@example.com (wintelknecht) — Fri, 25 Jan 2002 09:59:00 +0000

Sorry.
Kommt in der 8ten für lineare Funktionen.
Bsp.: Du fährst mit dem Fahrrad konstant 30km/h. Dann ist die Gleichung für den Zusammenhang zwischen Weg s (in km) und Zeit t (in h) s=30*t.

Die Nullstelle ist der x-Wert, bei dem y=0 ist (im Bsp. natürlich y==s=0 --> x==t=0).

Für s=30*t+5
(das würde bedeuten, dass Du erst zu einem Kumpel fährst, der 5 km entfernt wohnt und Du Deine Losfahrzeit t=0 bei ihm festlegst)
ist die Nullstelle (s=0) hier t=-5/30=-1/6. D.h. Du bist VOR (deshalb das Minus) 1/6h=10min bei Dir zu Hause losgefahren.

Und so sieht dann das Diagramm aus:

Code:


 Weg s (in km)
       |
    20 |           *
       |         *
    15 |       *
       |     *
    10 |   *
       | *
     5 *
     * |
 __*___|_________________ Zeit t (in h)
  |    0           |
 -1/6             1/2

Gerade in der Darstellung = Lineare Funktion, da
y=a*x^1+b, d.h. x steht selber da. Quadratisch ist es, wenn x^2=x*x da steht usw. usf.

Eine lineare Funktion schneidet die y-Achse maximal 1 mal (also da wo y=0). Maximal deshalb, weil auch kein Schnittpunkt da sein muß (Beispiel: v=30 bedeutet, daß Du konstant 30km/h fährst und weder schneller noch langsamer wirst - Deine Geschwindigkeit v ist somit unabhängig von der Zeit).
Je höher das n bei x^n ist, um so mehr Schnittpunkte hast man mit der y-Achse (maximal n). Und dass kann man dann oftmals nicht analytisch (per Hand) berechnen, sondern nur noch nummerisch.

Falls Du das alles schon kanntest, brauchst Du nicht sauer sein, ich wollte es Dir nur anschaulich erklären!

Ups, Diagramm verrutscht

[ 25.01.2002: Beitrag editiert von: wintelknecht ]

Re: Primzahlcheck

dummy@example.com (braveheart) — Thu, 24 Jan 2002 19:51:00 +0000

Was sind Null-Stellen?
PS: "Gesegenet sei dein Compiler..." - falsch. C sei gesegnet, denn es ist standardisiert, in C++ gibt es noch valarray

[ 24.01.2002: Beitrag editiert von: whitehouse ]

Re: Primzahlcheck

dummy@example.com (wintelknecht) — Tue, 22 Jan 2002 12:13:00 +0000

@whitehouse
"...das erste (matrix[0][0]) wird explizit mit 0 initialisiert, die anderen implizit" - gesegnet sei Dein Compiler und Deine Zuversicht in dessen Fähigkeiten.

Initialisiere mal die Matrix/den Vektor mit 1.0 und dann verstehst Du, was ich meine.
Im Fortran90 siehts so aus:
real :: fMatrix(10,10), fVektor(10)
fVector=1.0
fMatrix=1.0
Und zwar nicht die jeweils 1. Elemente, sondern alle!

Ich hoffe mich jetzt etwas verständlicher ausgedrückt zu haben.

Fortran ist zum Rechnen komfortabel (nur zur Info - Ich kann folgende Prog-Sprachen: Fortran, VB/VBA, Java und Pascal - C etwas und C++ noch etwas weniger). Das HTML- und DB-Zeugs laß ich mal wech. D.h. ich kann mir schon ein beschränktes Urteil erlauben.

Wenn man einen netten Compiler hat (oder ne Numeric-Bibo und davon gibt es jede Menge) dann kann man z.B. zum Finden der Nullstellen von
p(z) = z^3 - 3z^2 + 4z -2
einfach aufrufen:
CALL ZPLRC (NDEG, COEFF, ZERO)
wobei
- COEFF = (-2.0 4.0 -3.0 1.0) die Koeffizienten sind
- ZERO das Ergebnis der Nullstellensuche ist
- NDEG die Dimension des Polynoms (3) ist

Immer noch Fragen warum Fortran? Wenn ja, dann könnte ich Dir auf 90% aller Deiner Mathe-Probleme eine fertige numerische Lösung bieten. Ich bin zwar ein Freund von selberschreiben, aber manchmal ist so eine nette "kleine" Unterroutine schon sehr hilfreich.

Als Hardware-Nah würde ich persönlich Fortran nicht bezeichnen. Das ist ne Frage wie gut oder schlecht der Compiler arbeitet.
Vielleicht "Hardware-Nah" insofern, als dass ich mit Fortran schon mehrere Programme geschrieben habe um aus einer wüsten Binärdatei die Daten rauszuholen. Und das hätte ich mit keiner anderen Sprache machen wollen!!! Geht mit Fortran am einfachsten (sag ich [img]images/icons/wink.gif" border="0[/img] ).

Achso:
Fortran 90 ist das 77 weiterentwickelt. Alle Sprachelemente von 77 sind in 90 enthalten! Ich kann also ein 77 Prog mit nem 90iger-Compiler übersetzen. Für einige überholte Sprachelemente von 77 wurden in 90 neue geschaffen und die 77iger als obsolescent deklariert. Selbstverfreilich sind in 90 auch noch neue Sprachelemente hinzugekommen.

[ 22.01.2002: Beitrag editiert von: wintelknecht ]

Re: Primzahlcheck

dummy@example.com (braveheart) — Sat, 19 Jan 2002 21:16:00 +0000

noch was: normal nutze ich für Non-OOP-Sachen das C ähnliche Subset von C++ (das heißt mit Überladen usw.)

Re: Primzahlcheck

dummy@example.com (braveheart) — Sat, 19 Jan 2002 21:10:00 +0000

Code:


 double matrix[4][4] = {0};

- das erste (matrix[0][0]) wird explizit mit 0 initialisiert, die anderen implizit

Re: Primzahlcheck

dummy@example.com (braveheart) — Sat, 19 Jan 2002 21:05:00 +0000

hä? Fortran 77 und Fortran 90 hätten dann ja NULL miteinander zu tun. Inwieweit Hardware-nah? Kann mir das mal jemand erklären? Und wozu überhaupt Fortran, was ist der Vorteil?
(OT, aber sonst sagt hier niemand was *g*)

Re: Primzahlcheck

dummy@example.com (wintelknecht) — Fri, 18 Jan 2002 10:03:00 +0000

Nur ganz "kurz" - gehört ja eigentlich auch nicht hier her.

WH hat recht, wenn er die Variante 77 (oder noch älter) meint. Hier mal ein Auszug aus solch einem Prog:
if(iret) 142,10,142 --> falls iret<0;=0;>0 dann springe zu marke ...
10 if(idr-3) 12,15,12
12 write(iout,*) f
15 if(istart) 30,18,18
18 iret=0
do 20 i=1,kk --> entspricht einer for...next schleife, wobei das next bei Sprungmarke 20 steht
do 20 j=1,kk
20 vl(i+(j-1)*kk)=0.0
do 24 i=1,kk
vl(i+(i-1)*kk)=1.0
vl(kq+i)=abs(swa)
if(swa) 22,24,24 ! 24,22,22
22 vl(kq+i)=abs(swa*x(i))
24 continue
30 iter=iter+1
* print*,lo(4,50),'Iterationsschritt : ',iter
do 32 i=1,kk
vl(kq2+i)=2.0
32 vl(kq1+i)=0.0
40 ii=1
50 abm=0.0
do 54 i=1,kk
aba=vl(kq+ii)*vl(i+(ii-1)*kk)
abr=abs(aba)/(abs(y(i))+1.e-20)
if(abr-abm) 54,54,52
52 abm=abr
54 y(i)=y(i)+aba
if(abm-epsmi) 130,130,56
56 call ziel(y,f1)

Wer diesen Code verstehen will, der braucht schon ne Weile dazu. Ein typischer Spaghetti-Code. Der Vorteil: Kurz und schnell.

Doch Fortran ist nicht stehengeblieben. Eine wichtige Entwicklung war Fortran 90 (das benutze ich) und dessen konsequente Weiterentwicklung Fortran 95. Wer C (nicht ++) versteht, der versteht auch nahezu jedes Fortran 90 Prog.

Fortran 90 unterscheidet sich von den Möglichkeiten her (in Hinsicht auf ingenieurmäßige Belange) in keiner Art von einer anderen modernen Prog-Sprache. Außer expliziten Vererbungsmechanismen (und die braucht man im Normalfall zum Rechnen nicht) und Überladungen stehen alle Möglichkeiten einer sauberen und übersichtlichen Programmierung zur Verfügung. Es stehen weiterhin eine Vielzahl von vordefinierten Routinen zur Verfügung (und damit auch sehr leistungsfähig). In welcher Sprache kann ich einfach:
fMax1=MAXVAL(fFeld1(:,1))
fMin1=MINVAL(fFeld1(:,1))
schreiben und habe sofort den Min/Max-Wert der Spalte 1 des Feldes fFeld1 da? Oder ich schreibe:
fMatrix=MATMUL(fMatrixA,fMatrixB)
und habe das Matrizenprodukt da. Wobei ich einfach vorher definieren kann:
fMatrix=0.0, d.h. ich muß keine Schleife über alle Elemente der Matrix machen. Oder, oder, oder

Fortran ist aus meiner Sicht eine fein Sprache um übersichtliche und für den Programmierer komfortable Programme zu schreiben.

Achso - die Mechanismen der Mehrprozessorenfähigkeit (die sind dann aber Compilerabhängig) habe ich noch nicht genannt [img]images/icons/wink.gif" border="0[/img]

Was persönliches:
Ich habe 1 Woche vor Abgabe einer Arbeit noch Rechenergebnisse benötigt und war gerade so mit Programmieren fertig. Also Prog gestartet und dann mit Entsetzen festgestellt, das ich ca. 6 Wochen benötigen werde, bis ich alles durch habe. Was nun? Programm hergenommen und auf 3 Workstations und 5 PC verteilt. Bei den PC hab ich die exe natuerlich gleich laufen lassen können. Bei den Großrechnern hab ich die Sache compiliert (gerade auf ner Alpha waren da zwar noch einige Änderungen zu machen, da die 64-bitig rechnen kann, aber im Normalfall eigentlich nicht) und ab gings. Nach 4 Tagen war ich fertig und konnte die Sachen noch auswerten. Und jetzt frage ich: Mit welcher Sprache außer C geht das noch. Mit JAVA vielleicht, mußt aber erst das jdk installieren und brauchst damit admin-Rechte...

Re: Primzahlcheck

dummy@example.com (Manuel) — Thu, 17 Jan 2002 20:17:00 +0000

servus,
fortran... ist (soweit das mein horizont zu lässt)
glaub ich eine sehr hardware nahe sprache... und gerade deswegen...
ES GEHT HIER UM PERFOMANCE
und wenn da fortran besser ist...
allerdings hab ich da net wirklich die AHNUNG...
allerdings sehen progs in fortran für mich recht kryptisch aus. total anderes konzept wie bei sprachen wie c. (hab ich mir mal sagen lassen.. also erzählt mit mehr und berichtigt mich...)

übrigens die Software der vermittlungsstellen werden auch in fortran entwickelt. und ich würde sagen das ist PERFOMACNE UND ZUVERLÄSSIGKEIT BIS IN DEN LETZTEN WINKEL

grüsse & fetten segen
manu