Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Gast
|
Verfasst am: 12. Feb 2006 16:11 Titel: Answers!!! |
|
|
dachdecker2 hat Folgendes geschrieben: | "Sichtbarkeitsangaben" are deklarations of visibility (private/protected/public in C++)
According to your first post: could you post the circumstances of measuring the time usage, please? Interesting are statements about your machine and the solved problem (How many numbers have been tested? Which testing methode has been used?). Have a look at my last two posts, please. |
To answer your question of time usage we use a tool called Rational Application Developer's Profiler to precisely calculate the time it takes to compute the numbers. This test was run on a Sony VAIO series PCG-FR Intel Pentuim 4 CPU with 2.66 GHz with 448mb RAM. I do believe that the algorithm used is quite simple and self explanatory. If you really want to see something more complex being done with NATIVE then I recommend taking a look at our 3d next generation engine that was built. I have made a proposal within the heads of the company to make a daily tutorial on how a developer can create such an advanced 3d engine using NATIVE, and it was approved, so then now everyone can see through the tutorials the true capacity of NATIVE. |
|
Nach oben |
|
|
|
NATIVE Entwickler
Anmeldungsdatum: 09.02.2006 Beiträge: 4
|
Verfasst am: 12. Feb 2006 16:22 Titel: Re: Answers!!! |
|
|
My apologies, I had not logged in with the correct User Name.
basically the guest from above really equals NativeEntwikler. |
|
Nach oben |
|
|
Senior Sanchez Gast
|
Verfasst am: 12. Feb 2006 19:34 Titel: |
|
|
Crotaphytus hat Folgendes geschrieben: | @Senior: Hm... Kannst du da mal den Quelltext posten? Würd mich mal interessieren, wie du das so extrem optimiert hast. |
Den Quelltext will ich noch nicht posten, da ich ihn vllt nächstes Jahr für die Uni zum angeben brauchen *lach* Also nicht das mir jemand den kopiert und wegschnappt
Aber ich kann dir soviel sagen:
- es basiert aufm Sieb
- spart Iterationen dadurch, dass ab 3 nur noch jede zweite Zahl untersucht und multipliziert wird
- es wird nur bis zur Quadratwurzel des Zahlenbereichs gesucht (reicht auch aus)
- Viele mathematische Operationen arbeiten ich sag mal "low-level", sprich mithilfe von Bitmanipulationen, bitweisen Oder/Und usw. Dadurch brauch ich auch nur 1/8 des ursprünglich nötigen Speicherplatzes |
|
Nach oben |
|
|
dachdecker2 Moderator
Anmeldungsdatum: 11.06.2005 Beiträge: 106 Wohnort: Maintal / Hessen
|
Verfasst am: 12. Feb 2006 20:47 Titel: |
|
|
Wenn du wissen willst, ob n eine Primzahl ist, brauchst du nur alle möglichen Teiler bis \sqrt{n} abzuklappern - du kannst es dir zu Optimierung natürlich auch sparen, alle Vielfachen von 2, 3, 5, 7, 11 ... überhaupt zu testen. <-- das ist sozusagen das Sieb des Eratosteles - es kommt komplett ohne Divisionen aus, allerdings musst du immer bei 2 anfangen.
Das Sieb des Eratosteles kannst du natürlich so nicht optimieren. Wenn du bei mit einer k Elemente langen Liste natürlicher Zehlen beginnst und immer bei \sqrt{k} einfach aufhörst, die Nichtprimzahlen aus der Liste zu streichen, endet deine Primzahlenliste schließlich bei \sqrt{k}. Dahinter wären alle Zahlen Primzahlen. Jede gerade Zahl zu überspringen macht genausowenig Sinn - so hast du bestimmt einige gerade Zahlen dabei, die laut deinem Algorithmus Primzahlen sein würden.
Senior Sanchez, poste mal bitte die Primzahlenliste und den nicht optimierten Code, den wird dir hoffentlich keiner klauen - und wenn doch, ist das Urheberrecht auf deiner Seite. _________________ In a world without walls and fences, who needs windows and gates? [Internet]
Gruß, dachdecker2 |
|
Nach oben |
|
|
Senior Sanchez Gast
|
Verfasst am: 12. Feb 2006 21:04 Titel: |
|
|
dachdecker2 hat Folgendes geschrieben: | Wenn du wissen willst, ob n eine Primzahl ist, brauchst du nur alle möglichen Teiler bis \sqrt{n} abzuklappern - du kannst es dir zu Optimierung natürlich auch sparen, alle Vielfachen von 2, 3, 5, 7, 11 ... überhaupt zu testen. <-- das ist sozusagen das Sieb des Eratosteles - es kommt komplett ohne Divisionen aus, allerdings musst du immer bei 2 anfangen.
Das Sieb des Eratosteles kannst du natürlich so nicht optimieren. Wenn du bei mit einer k Elemente langen Liste natürlicher Zehlen beginnst und immer bei \sqrt{k} einfach aufhörst, die Nichtprimzahlen aus der Liste zu streichen, endet deine Primzahlenliste schließlich bei \sqrt{k}. Dahinter wären alle Zahlen Primzahlen. Jede gerade Zahl zu überspringen macht genausowenig Sinn - so hast du bestimmt einige gerade Zahlen dabei, die laut deinem Algorithmus Primzahlen sein würden.
Senior Sanchez, poste mal bitte die Primzahlenliste und den nicht optimierten Code, den wird dir hoffentlich keiner klauen - und wenn doch, ist das Urheberrecht auf deiner Seite. |
Du hast mich da etwas falsch verstanden
Die Iteration der äußeren Schleife läuft bis sqrt(k), Multiplikationen laufen aber darüber hinaus bis zum Ende des Zahlenbereiches
Reichts wenn ich dir letzten Primzahlen schreibe? Weil 78498 Primzahlen zwischen 1 und 1 Million hier zu posten wäre vllt etwas zu viel für die Modemnutzer
PS: ich muss mich korrigieren, mein Rechner hat gerade nen paar Dinge offen (TV Karte, Firefox, Word, Media Player und die Laufzeit lag gerade bei 24 ms auf meinem XP 1800 + )
Code: |
public class Prim {
public static void main(String[] args) {
long time = System.nanoTime();
boolean[] zahlen = new boolean[1000000];
double len1 = Math.sqrt(zahlen.length);
int len = zahlen.length;
int i = 2;
while(i <= len1) {
if(!zahlen[i]) {
int a=2*i;
while(a <= len) {
if(!zahlen[a]) {
zahlen[a] = true;
}
a+=i;
}
}
i++;
}
long time2 = System.nanoTime();
System.out.println(time2 - time);
int counter = 0;
for (i=2; i < zahlen.length; i++ ) {
if(zahlen[i] == false) {
System.out.println(i + " ist eine primzahl");
counter++;
}
}
System.out.println(counter);
}
}
|
Erstmal: Scheiß Einrückung *g* sorry dafür, aber das Forum hats so gebastelt, obwohl ich den Code-Tag benutzte.
Ich hoffe man erkennts trotzdem.
// dachdecker2: ich hab die 3 Posts mal zusammengefasst |
|
Nach oben |
|
|
dachdecker2 Moderator
Anmeldungsdatum: 11.06.2005 Beiträge: 106 Wohnort: Maintal / Hessen
|
Verfasst am: 12. Feb 2006 21:13 Titel: |
|
|
Stimmt bei mir dauerts manchmal etwas länger. Die Zahl der Primzahlen stimmt auch . Dein Code leutet mir auch ein - Boolean zum Speichern zu nutzen finde ich absolut Klasse . _________________ In a world without walls and fences, who needs windows and gates? [Internet]
Gruß, dachdecker2 |
|
Nach oben |
|
|
Senior Sanchez Gast
|
Verfasst am: 12. Feb 2006 21:20 Titel: |
|
|
dachdecker2 hat Folgendes geschrieben: | Stimmt bei mir dauerts manchmal etwas länger. Die Zahl der Primzahlen stimmt auch . Dein Code leutet mir auch ein - Boolean zum Speichern zu nutzen finde ich absolut Klasse . |
Die optimierte Version nutzt kein Boolean mehr. Sondern 32-bittige Integer
Dabei wird dann jedes bit eines integers genutzt um ein boolean darzustellen klingt komisch ergibt aber nen mächtigen perfomanceboost. nur so als klitzekleine info. |
|
Nach oben |
|
|
Crotaphytus
Anmeldungsdatum: 08.05.2005 Beiträge: 213
|
Verfasst am: 12. Feb 2006 22:23 Titel: |
|
|
@Senior: Jetzt weiß ich auch, wo mein Fehler steckt...^^ Auf die Idee mit den Integern zur Darstellung von Booleans bin ich ja auch noch gekommen, nur hat das bei mir nicht so viel gebracht. War immer noch gut über 1800ms.
Aber jetzt wo ichs seh is mir alles klar. Is ja schon irgendwie hohl, wenn man die Ausgabe gleich mit einbaut, dass das Zeit ziehen muss is ja irgendwie logisch... Na ja, es war spät in der Nacht...^^ _________________ Genie oder Wahnsinn? Wer kann es wissen... |
|
Nach oben |
|
|
Senior Sanchez Gast
|
Verfasst am: 12. Feb 2006 22:24 Titel: |
|
|
Crotaphytus hat Folgendes geschrieben: | @Senior: Jetzt weiß ich auch, wo mein Fehler steckt...^^ Auf die Idee mit den Integern zur Darstellung von Booleans bin ich ja auch noch gekommen, nur hat das bei mir nicht so viel gebracht. War immer noch gut über 1800ms.
Aber jetzt wo ichs seh is mir alles klar. Is ja schon irgendwie hohl, wenn man die Ausgabe gleich mit einbaut, dass das Zeit ziehen muss is ja irgendwie logisch... Na ja, es war spät in der Nacht...^^ |
Die Ausgabe ist recht teuer und da das nicht zur eigentlich berechnung gehört, habe ich das nicht mitgemessen gehabt. |
|
Nach oben |
|
|
Tristan
Anmeldungsdatum: 06.02.2006 Beiträge: 22
|
Verfasst am: 06. Apr 2006 22:26 Titel: NATIVE Trial-Version ist da! |
|
|
An alle, die noch an NATIVE interessiert sind!!!
Wir haben in den letzten Wochen viel an unserem Programm gearbeitet. Es wurde nicht nur das Gesicht verändert, sondern auch die zahlreichen Varianten der Editions auf eine reduziert.
Auf euren Wunsch hin wurde die Demo-Version, mit der ihr nicht so viel anfangen konntet, gegen die kostenfreie Trial-Version ausgetauscht. Diese Trial-Version ist eine Vollversion, auf 30 Tage beschränkt.
Ihr könnt hier alle Features nutzen und das Programm auf Herz und Nieren testen. Insbesondere könnt ihr eure eigenen Samples erstellen oder die von uns vorgegebenen nutzen und damit soviele Codes generieren, wie ihr wollt..!
Wir wünschen euch viel Spaß mit NATIVE und freuen uns auf eure Rückmeldungen!
Die Trial-Version findet ihr natürlich auf www.vandinburg.com!!! |
|
Nach oben |
|
|
|
|
Du kannst keine Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum nicht antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum nicht posten Du kannst Dateien in diesem Forum nicht herunterladen
|
|