| |
|
 Autor: |
|
Thema: Primzahlenprogramm - Datentypen?
|
|
|
Balduran
(offline)
Newbie
Beiträge: 2
Geschlecht: 
Mitglied seit: 04.10.2006
Deutschland
|
|
Primzahlenprogramm - Datentypen? #1
|
Datum: 04.10.2006, 09:47 
|
Hallo,
bin schon seit längerer Zeit interessiert am Programmieren von Primzahl-Such-Programmen, ist wirklich sehr interessant das Phänomen der Primzahl.
Nun habe ich schon mehrfach probiert Programme zu schreiben die Primzahlen suchen, klappt auch ganz super. Man gibt ein "Suche Primzahlen im Bereich von 0 bis 10000" und er sucht. Nur wie realisiert man es, dass er durchgehend sucht also bis ins Unendliche? Ich mein so ziehmlicher jeder Datentyp(Integer, Double) hat ja auch irgendwann eine Grenze? Gibt es irgendwie eine Möglichkeit die Datentypen ziehmlich weit zu spannen um halt möglichst große Zahlen zu speichern?
Programmieren wollt ich das ganze in C, Java oder C#
Besten Dank schonmal im vorraus,
Bruno
|
|
|
Triton
(offline)
Newbie
Beiträge: 21
Geschlecht:
Mitglied seit: 17.08.2006
Deutschland
|
|
|
Re: Primzahlenprogramm - Datentypen? #2
|
Datum: 05.10.2006, 17:31
|
Ich kann nur von meinen eigenen Erfahrungen berichten, und ich programmiere in BlitzBasic.
Dort habe ich mir eine Funktionssammlung geschrieben (mit Addition, Subtraktion, Multipl., Division, Wurzel, Modulo, a^b, Vergleich, Log, Primzahl, Mersenne-Pz, Runden, Quersumme, Fakultät) die auf Strings
(also Zeichenketten) basiert.
Die können in BlitzBasic beliebig lang werden (sprich, bis der Speicher platzt :)) und daher sind auch die Zahlen theoretisch bis 10^2^31 groß
(2^31 Stellen "nur" weil irgendwo immer auch noch Zähler mit drin sind,
die weiterhin Integer sind).
Jedenfalls habe ich so oben genannte Funktionen komplett neu geschrieben und überwiegend quasi das umgesetzt, was man in der Schule beim schriftlichen Rechnen lernt.
Natürlich kann man da bei Computern viel optimieren. z.B muss ein Computer bei der Multiplikation von 2 Zahlen nicht jede Zahl mit jeder
durchrechnen, sondern kann bis zu 9-Stellige abschnitte der langen Zahlen miteinander verrechnen (da jede 9-Stellige, nicht aber jede 10-Stellige Zahl im bereich Integer liegt).
Trotzdem ist der Nachteil davon, das Rechnen mit Strings prinzipiell langsamer ist, als auf normalem wege. Auch belegen die natürlich mehr Platz im Speicher - die Zahl 2147483647 würde bei Integer 4 Byte belegen, in der Zeichenkette aber 10 Byte, eben für jede Ziffer ein Byte.
Natürlich ist auch das Rechnen nachher nicht ganz so einfach.
Man kann z.B nicht schreiben
code:| Print primzahl$(10^11 + 3) |
Sondern
code:| Print primzahl$(addition$(ahochb$("10","11"),"3")) |
Aber das bekommt man schnell auf die Reihe.
Jedenfalls konnte ich so bisher allerhand Dinge errechnen, die mir
zuvor verwährt waren. etwa der test, ob 10^13 + 37 (dauerte 23 min..) oder 2^607 -1 tatsächlich Prim ist (dauerte 26 min). Naja, waren noch unoptimierte Algorithmen :)
Meine momentanen Probleme sind aber folgende Dinge:
- Division schneller (habe bisher nur einen selbst erdachten Algo der nur fast so schnell ist wie der vom normalen schriftlichen Rechnen - werd da noch optimierungsarbeit leisten müssen..)
- bessere umsetzung Wurzelrechnen (bisher auch nur alternativer, langsamer Algo)
- Beliebige Potenzen (bisher nur ganzzahlig a^b)
- beliebige Wurzeln
- beliebige Logarithmen mit beliebiger Genauigkeit (bisher nur ganz simpel dekadischer Log. mit ganzzahliger Genauigkeit..)
Wär schön, wenn mir einer vorallem bei den letzten 3 Problemen helfen
könnte - da ich eben nicht weiß, wie man billig und effizient und vorallem schriftlich (!) beliebige Potenzen, Wurzeln und Logarithmen mit beliebiger genauigkeit errechnen kann.
(Bisher wurde dieser Beitrag 2 mal editiert, als letztes von Triton am 05.10.2006 @ 17:38)
|
|
|
Gast
|
|
|
Re: Primzahlenprogramm - Datentypen? #3
|
Datum: 18.10.2006, 20:08
|
In verschiedenen Programmiersprachen gibt es schon vorgefertigte Langzahlarithmetiken. Ich habe ihn C++ dennoch einmal mir selber etwas programmiert. Ich habe die Zahle einfach in viele kleine Zahlen aufgeteilt (so ähnlich wie Triton). Aber ich habe dafür den Datentyp integer genommen. Das heißt ich hatte 80 Integers, die zusammen eine lange Zahl ergaben. Den Rest, also die Verknüpfungen die man auf diese Zahlen anwenden kann, muss man selber schreiben. Ich kann dir mal meine Versuche zeigen:
[url=]http://kuhlmann.ku.funpic.de/files/LNA.cpp[/url]
So ist das...
Grüße
Malte
|
|
|
Balduran
(offline)
Newbie
Beiträge: 2
Geschlecht:
Mitglied seit: 04.10.2006
Deutschland
|
|
|
Re: Primzahlenprogramm - Datentypen? #5
|
Datum: 08.12.2006, 15:25
|
So schnell kanns passieren das man etwas einfach vergisst, bin letztens erst wieder aufs Thema Primzahlen gestoßen und hab mich gleich drann errinert "Ah da war doch irgendwo was in einem Forum"
Gut also die Idee mit den Zahlen aufteilen ist hilfreich, besten Dank ich werd mal ein wenig rumprobieren
|
|
|
|
|
|
