Autor Beitrag
Amateur
ontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic starofftopic star
Beiträge: 777

(Win98, WinMe) WinXP Prof
D3 Prof, D6 Pers, D2k5 Pers., Turbo C++ Explorer
BeitragVerfasst: Fr 26.08.05 23:07 
also es geht darum dass ich wie manche andere auch nen algorithmus zum finden von primzahlen schreiben bzw. geschrieben haben...
das ist auch nicht das problem sondern das problem besteht darin, dass es ja nix bringt ne funktion dafür zu schreiben aber man kann nur bis zu einer bestimmten zahl berechnen da ne int64 oder normale integervariable nur bis zu ner gewissen größe zahlen speichern kann...

jetzt is die frage:
wie kann man zahlen speichern, die größer sind als ne int64 variable speichern kann?
man muss natürlich auch mit damit weiterrechnen können...
sonst könnte man sie ja in ner txt datei ablegen aber man muss sie ja überprüfen ob es ne primzahl is...

so für alle die es noch net verstanden haben nen kleines beispiel:

ich hab ne function primzahl(zahl:int64);

an diese funktion wird ne zahl übergeben. gehn wir ma davon aus dass int64 nur zahlen bis 6000 (was natürlich nicht stimmt) speichern kann.

also wird primzahl(6000) noch funktionieren...

jetzt will ich aber weiterprüfen ob 6001 und 6002 etc. auch primzahlen sind, da man ja bestrebt is die größte primzahl zu finden...

was kann ich also machen um 6001 auch an die funktion zu übergeben und damit zu rechnen???

hoffe das haben alle verstanden (int64 kann natürlich größere zahlen als 6000 speichern war nur zur verdeutlichung gedacht)

gibts da ne möglichkeit oder geht das einfach mit normal delphi und homepcs net?
denn wensn net geht brauch man ja gar keinen algorithmus zu schreiben oder ihn als verbessern wenn man eh nix damit anfangen kann außer nen haufen zahlen und ne riesen txt datei die die festplatte vollmüllt...

_________________
"Kein dummes Gerede. Kein Rumrätseln. Denkt an nichts anderes mehr, nur noch an das, was vor euch liegt. Das ist die wahre Herausforderung. Ihr müßt euch vor euch selbst schützen, Leute." (Rennes in "Cube")
Beiträge: >700
JayEff
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2971

Windows Vista Ultimate
D7 Enterprise
BeitragVerfasst: Fr 26.08.05 23:11 
Sorry aberich fürchte da gibts keine andere möglichkeit als dir selbst eine art variablentyp zu schreiben. Dieses Thema gabs aber schon öfter, glaub ich, such doch mal danach...

_________________
>+++[>+++[>++++++++<-]<-]<++++[>++++[>>>+++++++<<<-]<-]<<++
[>++[>++[>>++++<<-]<-]<-]>>>>>++++++++++++++++++.+++++++.>++.-.<<.>>--.<+++++..<+.
negaH
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17



BeitragVerfasst: Sa 27.08.05 00:11 
Jede CPU kann per spezieller Software sehr wohl mit Zahlen rechnen die in ihrer Größe weit über die Standardoperationen der CPU hinaus gehen. Das machen übrigens alle Programme so die solch große Primzahlen berechnen.

Eine 32Bit CPU hat zb. alle nötigen Operationen um mit 32 Bit Zahlen rechnen zu können. Die nötige Software macht nun genau das was du machst wenn du zwei große Zahlen zb. multiplizieren sollst. Du wirst also auf deinem Papier diese beide Dezimalzahlen nebeneinander aufschreiben und darunter Schritt für Schritt sequentiell aber nur die einzelnen Dezimalziffern dieser Zahlen multiplizieren. Du zerlegst also auf mathematische Art und Weise die großen Zahlen in kleinerer und rechnest so über Zwischenprodukte das Ergebnis aus. Genau dies machen alle Programme die solch großen Zahlen benötigen und nutzen.

Nun zu deinen Primzahlen:
Du musst dir klar darüber werden WAS du für Primzahlen berechnen willst. Also:

a) möchtest du eher statistische Analysen über die Verteilung von Primzahlen anstellen, dann benutze ein Sieb wie es im anderen Thread beschrieben wurde

b) möchtest du eine beliebig große Zahl testen und eventuell verifizieren ob sie eine Primzahl ist. Dann schau dir mal Marcel Martin's Primo (Titanix/ Certifix) genau an das per Elliptischen Kurven mathematisch beweisbare Zertifikate über die Primality einer Zahl erzeugen kann

c) möchtest du auf Primzahl-Jagd gehen und eventuell die größte bekannte Primzahl berechen mit deiner Software. Dann musst du dich von vornhinein auf Zahlen mit ganz spezieller Form konzentrieren, zb. Lucas-/Fermat- oder Mersenne- Zahlen. Für diese gibt es ganz spezielle mathematische Konstruktionsverfahren die teilweise ohne große Integerberechnungen auskommen

d) möchtest du sogenannte industrielle Primzahlen erzeugen die zb. in der heutigen Kryptographie üblich sind. Dort nutzt man Strenge Pseudo Primzahl Test wie das zb. Rabin-Miller Verfahren oder den Baillie-Selfridge-Wagstaff-Pomerance-Strong-Lucas-Pseudo-Prime-Test. Je nach benutzten Test wurde die Wahrscheinlichkeit das diese Tests eine Falsch-Antwort liefern in Bereiche verschoben die fast schon unendlich unwahrscheinlich sind. Dafür kann man mit solchen Verfahren aber auch am Fließband große Primzahlen erzeugen. Meine eigene Library erzeugt zb. 1024 Bit Primzahlen innerhalb von 500ms.

Das Gebiet ist also sehr weit abgesteckt und je weiter du die Zahlengrenzen ausdehnst um so spezieller müssen deine Implementierungen und Ziele sein.

Wenn du dich umfasssender informieren möchtest dann solltest du hier primes.utm.edu/ reinschauen.

Gruß Hagen
GTA-Place
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
EE-Regisseur
Beiträge: 5248
Erhaltene Danke: 2

WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
BeitragVerfasst: Sa 27.08.05 07:46 
1. nach Suche bei Google DELPHI "GROßE ZAHLEN" suchen
2. Link zur DP folgen: Delphi-PRAXiS :: sehr sehr große zahlen
3. Link im Thread folgen: Mage* Zahlen
4. Link zu Google folgen: HugeInt Delphi
5. 1. Link folgen: efg's Reference Library: Delphi Cryptography and Multiple ...
6. Bis "HugeInt**" scrollen.
7. "HugeInt" downloaden: HugeInt.zip


*Schreibfehler des Autors, sollte "Mega" heißen.
**Speichert so viele Zahlen, wie der Speicher zu lässt.

EDIT: Der Google-Suchlink geht mit den " nicht. Musst halt manuell eingeben.


EDIT2: Und weil die Unit nicht funktioniert, zumindest bei Personal Edition nicht, nehmen wir die hier:
www.delphiforfun.org...ary/big_integers.htm

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)
negaH
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17



BeitragVerfasst: Sa 27.08.05 12:22 
Da HugeInt nicht komplett als Source vorliegt wäre es eventuell interessant für dich diesen Thread anzuschauen -> www.delphipraxis.net...achkommastellen.html
Dort gibts dann ebenfalls eine binäre Distributation einer solchen Library.

Gruß Hagen
GTA-Place
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
EE-Regisseur
Beiträge: 5248
Erhaltene Danke: 2

WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
BeitragVerfasst: So 28.08.05 09:02 
Ich guck mir mal deine Libary heute an.
Klingt interessant. Hast du vielleicht auch ne upgedatete Version?
In dem Thread sind ja viele Verbesserungsvorschläge.

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)
GTA-Place
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
EE-Regisseur
Beiträge: 5248
Erhaltene Danke: 2

WIN XP, IE 7, FF 2.0
Delphi 7, Lazarus
BeitragVerfasst: So 28.08.05 16:22 
Die ist wirklich genial die Libary!
Respekt!

_________________
"Wer Ego-Shooter Killerspiele nennt, muss konsequenterweise jeden Horrorstreifen als Killerfilm bezeichnen." (Zeit.de)
negaH
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 17



BeitragVerfasst: Mo 29.08.05 06:32 
Zitat:

Klingt interessant. Hast du vielleicht auch ne upgedatete Version?
In dem Thread sind ja viele Verbesserungsvorschläge.


Um genau zu sein war meine NRoot() Funktion noch buggy. Diese Änderungen habe ich natürlich in die Lib eingearbeitet, aber eben noch nicht wieder gepostet :( In der Zwischenzeit habe ich eh noch einige größere Umbauarbeiten gemacht, sprich die inoffizielle Version 5.0 vom DEC Part I in die Library eingearbeitet.

Am besten EMail an mich, mit der Angabe der Delphi Version, schicken.

Gruß Hagen
zemy
ontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic starofftopic star
Beiträge: 207

Win XP Prof.
D7
BeitragVerfasst: Do 08.09.05 14:20 
user profile iconAmateur hat folgendes geschrieben:
user profile iconGausi hat folgendes geschrieben:
user profile iconAmateur hat folgendes geschrieben:
die größte primzahl is ja irgendwas mit 2^6000 -1 oder so...

"Oder so" ist richtig: :lol:
de.wikipedia.org/wiki/Mersenne-Primzahl: hat folgendes geschrieben:
Im GIMPS-Projekt wurde die 42. Mersenne-Primzahl entdeckt: 2 hoch 25.964.951 -1 hat 7.816.230 Stellen.

Eine größte Primzahl gibt es übrigens nicht - es gibt ja bekanntlich unendlich viele.


ja ok viell doch nen bisschen größer.. ich meinte natürlich die größte bekannte bzw. gefundene primzahl...sry.

naja aber wie will man sowas abspeichern? nen variablentyp in delphi der so ne zahl speichert is mir net bekannt...

kann man das also umgehn? denn sonst bringt son primzahl algorithmus ja eh nix... lässt man seinen pc die ganze laufen und spamt seine platte mit ner riesen textdatei voll voller primzahlen und im endeffekt wird man eh keine größere finden können da nen normaler hauspc gar net so große zahlen speichern kann...

bringt also im endeffekt nix außer dass man sagen kann ich hab nen primzahlenalgoritmus geschrieben...

oder?

Mal aus dem Primzahlenthread qequotet...

Gerade die Mersene-Primzahlen haben eine sehr günstige Binäre bzw. Hexadezimale Form. Durch die Definition 2^n-1, also Zweierpotenz-1 kommt man immer auf ein Haufen einsen oder Hexadezimal $FFFFFFFF...........FF. Speziell für die Zahlen ist es nicht nötig, alles im Speicher zu halten und sie eigenen sich dadurch auch ganz gut für Primzahlrecorde. Gerade weil es für Mersenneprimzahlen noch nen extra algo gibt (Stichwort Lucas Lehmer Test)

So, das mal eingeschoben, zurück zu den Libs...

_________________
LifeIsToShortToThinkAboutTheShortness