Rechnen ohne Limit mit Brüchen, Vorzeichen und bis zu 2 Mrd STELLEN!

Maxi

hehe, 2 zahlen mit 2Mrd stellen passen ja auch kaum in den Ram
also wenn sie aus ASCII-Basis gespeichert werden. Es ging ja auch nur ums Prinzip, dass es eben doch ein Limit gibt. Ob man das Limit dann erreicht, ist ja was anderes.

btw: Was hat das denn mit Jugend forscht zun tun? Was forscht man denn da? Ichmein, eigentlich stehen die algorithmen dafür doch fest, oder? ODer hast du da was neues erfunden?

etlam

Maxi schrieb:

btw: Was hat das denn mit Jugend forscht zun tun? Was forscht man denn da? Ichmein, eigentlich stehen die algorithmen dafür doch fest, oder? ODer hast du da was neues erfunden?

Schau mal hier: http://forum.etlamsoft.de/viewtopic.php?f=9&t=12
und hier: http://www.jugend-forscht.de/
Jugentliche können dort ihr Projekt einreichen.
Dann kommen sie zuerst in einen Regionalwettbewerb, können, falls sie gewinnen können sie in den Landeswettbewerb und in den Bundeswettbewerb kommen.
Man muss nicht umbedingt etwas forschen oder neu erfinden, es heißt nur so...
Ich kam dieses Jahr mit diesem Projekt in den Landeswettbewerb Hessen.

etlam

matimatiker

etlam schrieb:

Die gröste Primzahl, hat in etwa 10 Millionen Stellen.

Stimmt nicht. Gibts unendlich davon. Und kannst unendlich viele davon sehr leicht erzeugen, auch mit > 10 Mio stellen.

Ansonsten habe vor sowas ähnliches selbst zu programmieren, was aber nur auf ganze zahlen beschränkt sein wird.

Was fuer Algorithmen verwendest du denn fuer die Multiplikation und Division?

Ben04

Ich find irgendwie den Download link nicht.

Ich hatte vor einiger Zeit auch eine Bibliothek gebaut um mit großen Zahlen zu jonglieren. Meine gibt es hier. (Falls irgendwer das einsetzen will bitte melden, dann gibt es bug update.)

Sind deine 2 Milliarden Festkommazahlen oder Gleitkommazahlen? Wie sieht es mit komplexeren Operationen aus wie zum Beispiel Wurzel ziehen?

etlam

Also das ganze funktioniert in etwa so, wie ein Mensch auf Papier rechnen würde.
2Mrd Stellen heißt, das die Zahl aus 2Mrd Zeichen aufgebaut sein darf. (Als Zeichen zählt auch das Komma, der Bruchstrich...).
Es sind Festkommazahlen.
Download findet man hier: http://forum.etlamsoft.de/viewtopic.php?f=9&t=10&st=0&sk=t&sd=a&start=10
Das Installationsscript ist dem letzten Post angehängt.
Das Installationsscript macht ihr einfach ausführbar und führt es als root aus.
Das script lädt dann die eigentliche Libary herunter.
Wurzel gibt es noch nicht, kommt aber zur nächsten Version!

etlam

etlam schrieb:

Also das ganze funktioniert in etwa so, wie ein Mensch auf Papier rechnen würde.

Dann ist die Library also noch ausbaufaehig, um es mal diplomatisch auszudruecken :).

Achso, eine Sache wundert mich noch: Warum kannst du das ganze nicht unter eine Open-Source-Lizenz stellen, nur weil du an "Jugend forscht" teilnimmst?

Ben04

Naja, weißt du es gibt auch noch Leute die ein Windows haben und keinen Bock haben irgendeinen Bash Port zu installieren nur um mal schnell eine Lib anzuschauen.

Wie wäre es mit einem Zip mit einem src Verzeichnis wo alle *.cpp Dateien drin liegen, einem include Verzeichnis mit den Headern, ein Readme wo drin steht wie man das ganze benutzt und vielleicht noch ein makefile?

So hab mir die Adresse mal von Hand ausgelesen.
http://www.etlamsoft.de/rechnen_ohne_limit/rol_1.4.0.zip

Die ist in der Tat sehr verbesserungsfähig. Als erstes solltest du dir mal anschauen wie ein Header auszusehen hat. (Stichwort include guards) Danach solltest du dir mal ein geeigneteres Format für Zahlen überlegen. Ein String ist da eine sehr schlechte Wahl.

typedef string rol;
extern rol& operator+(rol&,rol&);

Kompiliert das überhaupt? Es gibt doch bereits ein std::string std::operator+(const std::string&, const std::string&). Das muss doch Konflikte geben. Desweiteren glaub ich kaum, dass der Rückgabe-Type kein Bug ist.

etlam

Doktor Prokt schrieb:

etlam schrieb:

Also das ganze funktioniert in etwa so, wie ein Mensch auf Papier rechnen würde.

Dann ist die Library also noch ausbaufaehig, um es mal diplomatisch auszudruecken :).

Wenn du Ideen hast, nur her damit
Ich arbeite natuerlich noch daran und verbessere es.
Mit "Die groeste Primzahl hat 10Millionen Stellen" meinte ich natuerlich, die groesste bekannte! Primzahl!
Das ich bei JugendForscht mitmache, ist nicht der Grund dafuer, dass ich jetzt nicht GPL benutze, das ist nur mein Zeitpunkt, zu dem ich das aendere.
@Ben04 Wieso brauchst du den Pfad zur Zip Datei?
Benutze doch einfach das Installationsscript?
Ja, das mit dem include aendere ich und das mit dem string ueberlege ich auch noch einmal.
Und: Ja, es kompiliert!

etlam

matimatiker

etlam schrieb:

Mit "Die groeste Primzahl hat 10Millionen Stellen" meinte ich natuerlich, die groesste bekannte! Primzahl!

Glaub ich nicht so recht. Ich kann noch ne größere ausrechnen.

edit: http://de.wikipedia.org/wiki/Arithmetik_in_Stellenwertsystemen hilft dir vielleicht für bessere algorithmen.

Ben04

etlam schrieb:

Benutze doch einfach das Installationsscript?

[nicht diplomatisch]Es gibt da ein Programm, es nennt sich Windows, welches von einer Minderheit (nur etwa 75%) von Usern eingesetzt wird. Auf dem Laufen keine Bash-Shell Scripts und mit "shared Objects" kann es leider auch nicht umgehen.[/nicht diplomatisch]

etlam schrieb:

Ja, das mit dem include aendere ich und das mit dem string ueberlege ich auch noch einmal.
Und: Ja, es kompiliert!

Fragt sich nur ob

std::string a("a"), b("b"), c;
c = a + b;

noch das tut was man erwartet.

Mario Sandler

Hm das würd mich aber jetzt auch mal interessieren
Wäre es nicht besser eine neue Klasse rol zu definieren
statt "nur" ein typedef?

Und warum nimmst du überhaupt strings zur Darstellung
von solchen Zahlen. Das ist doch totale Platzverschwendung!
Schau dir mal den Link an:
http://www.uni-leipzig.de/~sma/pi_einfuehrung/langzahlc.html

tesuji

hi,
schau dir auch mal die Algorithmen von gmp (GNU Multiple Precision) an.
vg tesu

etlam

Ben04 schrieb:

[nicht diplomatisch]Es gibt da ein Programm, es nennt sich Windows, welches von einer Minderheit (nur etwa 75%) von Usern eingesetzt wird. Auf dem Laufen keine Bash-Shell Scripts und mit "shared Objects" kann es leider auch nicht umgehen.[/nicht diplomatisch]

Wenn du Windows benutzt, geht es eben nicht.
Entweder legst du dir Linux zu, oder du benutzt es eben nicht...

Ben04 schrieb:

Fragt sich nur ob
std::string a("a"), b("b"), c;
c = a + b;
noch das tut was man erwartet.

Hmm, ich aender das noch und machs ohne Typedef...
@Storm.Xapek.de:
jA, machs dann mit einer Klasse.
Den Link kann ich hier nicht oeffnen, blockiert...
Was steht denn dort?
Ich machs lieber erstmal ohne andere algorithmen, da ich so erstmal besser noch neue Sachen machen kann. Hinterher aender ich das dann.
@matimatiker:
Wenn du groessere Primzahlen ausrechnen kannst, dann reichs bei eef ein und du bekommst 100 000 Euro!!!!
Bei 1Mrd Stellen bekommst du eine viertel Millionen!

Mfg,
etlaM

matimatiker

Ok, sorry. du hast recht. Ich hatte den Beweis über die unendliche Anzahl der Primzahlen falsch verstanden.

etlam

Inzwischen hat sich bei RoL einiges getan...
Die aktuelle Version ist Version 1.5.0

RoL ist immer noch eine Shared Object Libary (librol.so) die es dem C++-Programmierer erlaubt, mit Zahlen von bis zu 2G Stellen zu rechnen.

Hier ein Auszug aus der Neuigkeitsliste:
-Es gibt jetzt die Klasse rol (!,+,-,*,/,<<,>>,<,>,== ueberladen)
-Es werden keine Dateien mehr benötigt, alles wird intern über Arrays verwaltet.
-Alles ist viel schneller geworden
-Neue Funktionen

abs
a^b
natürlicher Logarithmus
exp
Wurzeln
Fakultät
min und max
sin, cos, tan (jeweils eine Funktion mit Winkel und eine als Bogenmaß - also z.B. sina und sinx)
cot, sec, csc (z.Z. nur als Bogenmaß - also cotx...)
sinh, cosh, tanh, coth, sech, csch

Hier ist die Ankündigung der neuen Version mit Download des Installationsscript
Das Installationsscript muss nur als root ausgeführt werden, schon kann man RoL benutzen.

Über Kritik und Anregungen würde ich mich sehr freuen!

Vielen Dank im voraus,
etlam

Mario Sandler

etlam schrieb:

Es gibt jetzt die Klasse rol[...]

Was war es den vorher?
Ein typedef auf std::basic_string<int>

Irgendwie gibt es sehr wenig Beispiele zur Benutzung von rol.
Ich hab nur grad sowas gesehen zahl.roli("4535"), dass könnte
man mit einer überladenen Funktion besser lösen (falls das Beispiel noch aktuell ist)
Hast du den Quellcode inzwischen eigentlich offengelegt?

etlam

Storm.Xapek.de schrieb:

Irgendwie gibt es sehr wenig Beispiele zur Benutzung von rol.

Ich bin gerade dabei, Beispiele zu schreiben und die Seite zu überarbeiten.

Der Quellcode ist noch nicht offengelegt, da musst du noch etwas warten, wenn du verbesserungsvorschläge hast baue ich sie aber gerne für dich ein.

etlam

DerGhost

matimatiker schrieb:

etlam schrieb:

Die gröste Primzahl, hat in etwa 10 Millionen Stellen.

Stimmt nicht. Gibts unendlich davon. Und kannst unendlich viele davon sehr leicht erzeugen, auch mit > 10 Mio stellen.

Ansonsten habe vor sowas ähnliches selbst zu programmieren, was aber nur auf ganze zahlen beschränkt sein wird.

Ja, es gibt unendlich viele Primzahlen. Aber die größte momentan bekannte davon hat etwas weniger als 10 Millionen Stellen (soweit ich weiß 9,8 Millionen, die wurde vor etwas mehr als nem Jahr entdeckt) und leider ist es überhaupt nicht leicht unendlich viele beliebig große zu erzeugen.
Genau genommen ist es jedesmal ne kleine mathematische Sensation wenn jemand ne größere findet. Nebenbeibemerkt liefen bei der Suche dieser bislang größten Zahl 700 Rechner fast ein Jahr lang um sie zu finden.
Wäre dies algorithmisch leicht, würden viele der momentan signifikantesten Probleme in der Kryptographie trivial werden.