Programmiersprache für Zahlentheorie?

... komplette Frage anzeigen

11 Antworten

Das Standardverfahren (das vermutlich von dir erwartet wird) ist die Probedivision bis maximal zur Wurzel der zu zerlegenden Zahl. Wenn du vorher einen Faktor findest, teilst du durch diesen und machst mit dem Ergebnis weiter.

Das kann man in jeder Programmiersprache leicht programmieren.

Python hat den Vorteil, dass du mit den Zwischenergebnissen in der Shell interaktiv rechnen kannst, während die anderen hier genannten Sprachen (Java, C# usw.)  zwar deutlich schneller sind, aber eben nur eine Eingabe und eine Ausgabe haben (es sei denn du baust dir selbst eine aufwendige Benutzerobefläche)

Geschwindigkeit ist dabei aber auch relativ unwichtig. Ein long int (2^63) bekommst du mit dem obigen Verfahren weder mit Python noch mit Java schnell zerlegt und ob du auf ein Ergebnis 2 oder 20 Sekunden wartest, ist letztlich auch egal. Du willst ja vermutlich mit handhabbaren Beispielen arbeiten. 10 stellige Zahlen (normales int bis 2^31) gehen in beiden Sprachen fix, da du ja nur ca. 50000 Probedivisionen machen musst. Die (Nicht-)Zerlegung von 10^15+37 dauert bei mir in Python etwa 5 Sekunden.

Schön an Python ist auch, dass es ziemlich wenig Overhead hat.

print "Hallo" 

ist nunmal kürzer als

class Hallo {
public static void main(String[] args) {
System.out.println("Hallo");
}
}
Antwort bewerten Vielen Dank für Deine Bewertung

Solange du nicht mit immens großen Zahlen arbeitest, ist die Wahl der Programmiersprache eher unwichtig. ^^

Wichtiger ist die Wahl des Algorithmus zur Prinfaktorzerlegung - dieser sollte effizient sein.

Ich hoffe, ich konnte dir helfen; wenn du noch Fragen hast, kommentiere einfach. 

LG Willibergi 

Antwort bewerten Vielen Dank für Deine Bewertung

Es kommt ein bisschen darauf an, was dein endgültiges Ziel ist.

Python zum Beispiel ist leicht zu erlernen und das müsste damit auch ganz gut machbar sein. Im Vergleich zu anderen Sprachen ist Python aber recht langsam. Sprich wenn du das Programm dann nicht nur ein Mal kurz, sondern ausgiebig benutzen möchtest, ist es nicht das richtige.

Falls Geschwindigkeit eine wichtige Rolle spielt, würde ich auf eine kompilierte Sprache wie C/C++ zurückgreifen. Die sind dann aber bedeutend schwerer zu erlernen.

Antwort bewerten Vielen Dank für Deine Bewertung

Dafür nimmt man keine Programmiersprache, sondern ein CAS. :)

GNU Octave würde sich anbieten. Das ist kostenlos, hat eine GUI und hält für jedes nur erdenkliche Problem äußerst effiziente Algorithmen vor, ohne dass du dir für jeden Murks erst eine extra Bibliothek beschaffen musst.

Um auf deine Fragestellung zurück zu kommen: Nehmen wir mal an, du willst 12345 in Primfaktoren zerlegen, dann geht das mit folgendem Befehl:

factor(12345)

... was dir diese Ausgabe liefert:

3 5 823

So einfach ist das! :)

Die gängigen CAS-Systeme lassen sich sehr komfortabel skripten, und Bindings für alle möglichen Programmiersprachen gibt es i. d. R. ebenfalls.

Also dann ... viel Spaß! :)

PS: Wenn du nicht glaubst, dass 823 eine Primzahl ist, dann kannst du das mit ...

isprime(823)

... prüfen, und - siehe da - du erhältst:

ans = 1

(wobei die 1 für "wahr" und eine 0 für "falsch" steht)

Eleganter wirst du das in keiner anderen Programmiersprache lösen können. :)

Viel Spaß! :)

PS: Wenn du dir einen RasPi zulegst, bekommst du sogar kostenlos das aktuelle Mathematica dazu! Und wenn du über zu viel Keingeld verfügst, kannst du dir sogar MATLAB oder Maple kaufen, wobei alle genannten unterschiedliche Einsatzzwecke, Stärken und Schwächen haben. Aber mit Primfaktorzerlegung sollte keines Problem haben. :)

PPS: Online geht das ganze auch mit Wolfram Alpha, was eine Art Web-GUI zu Mathematica ist:

https://www.wolframalpha.com/input/?i=factor+12345

Na, dann hau mal rein! :)

Antwort bewerten Vielen Dank für Deine Bewertung

Wie Karajan9 bereits richtig andeutete: Du hast die vielen Randbedingungen vergessen:

§1: wenn Du 100stellige Zahlen mit dem primitivsten Algorithmus (Modulo ungerade Zahlen bis zur Wurzel n) berechnen willst, kannst Du alle Interpretersprachen vergessen, da sie stunden- oder sogar tagelang rechnen würden. Hier würden nur c++ oder andere echte Compiler unter 1 Stunde bleiben. (64 Bit; Multitasking; AVX-Befehle, FFT-Multiplikation,...)

also Angabe der  Obergrenze fehlt

§2: Wenn der Algorithmus gut ist (Elliptic Curve Method; Carmichael-Faktorisierer), kann man selbst 200stellige Zahlen mit mittelschnellen Sprachen (php, Java, c#) berechnen. In JAVA gibt's bereits fertigen Code der auch noch unabhängig vom Betriebssystem arbeitet! 

Es fehlt gewünschte Geschwindigkeit oder maximale Zeitdauer (schwankt extrem stark: 2er Potenzen sehr leicht & schnell; RSA-Zahlen extrem langsam & kompliziert)

§3: warum teure und von zig Faktoren abhängige Fremdsoftware wie Matlab verwenden? Wenn Du mal den Rechner wechselst, muss immer die Fremdsoftware zuerst installiert werden... Außerdem ändert sich mit der Version oft auch einiges. Würde ich abraten...

Außerdem gibt es http://de.mathworks.com/products/matlab-coder/

der c- & c++ Code erzeugt -> warum nicht gleich c++ ohne Umwege?

§4: ist Zugriff auf Datenbank erlaubt? Es gibt im Internet Datenbanken für über 1000 stellige Zahlen, die bereits faktorisiert sind. Andererseits gibt es 300stellige Zahlen, die bis heute immer noch NICHT fakorisiert sind, also unbekannt, ob Primzahl...

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von kordely
13.08.2016, 22:07

Auch wenn sie gute Teste für Primzahlen haben.

0

Prinzipiell geht das zwar mit jeder Programmiersprache, aber typischerweise, z.B. in der Kryptographie, will man es mit ziemlich großen Zahlen machen, für die auch 64 Bit zu wenig sind. Man braucht also Langzahlarithmetik, d.h. Rechnen mit (soweit der Arbeitsspeicher ausreicht) beliebig langen Zahlen.

Programmiersprachen mit Langzahlarithmetik sind hier aufgelistet: https://de.wikipedia.org/wiki/Langzahlarithmetik

Hier ist eine noch umfangreichere Liste: https://en.wikipedia.org/wiki/List\_of\_arbitrary-precision\_arithmetic\_software

Auch jedes Computeralgebrasystem läßt sich dafür verwenden: https://de.wikipedia.org/wiki/Computeralgebrasystem

Antwort bewerten Vielen Dank für Deine Bewertung

Bei uns an der LMU hat Prof. Forster (v.a. bekannt durch seine weit verbreiteten Analysis Lehrbücher), Spezialist für Zahlentheorie, die Programmiersprache ARIBAS entwickelt. Die bietet jede Menge Funktionen der Zahlentheorie an und unterstützt Langzahlarithmetik. Von der Syntax her ist ARIBAS an Pascal angelehnt.

Mehr Infos dazu hier:
https://www.mathematik.uni-muenchen.de/~forster/sw/aribas.html

Antwort bewerten Vielen Dank für Deine Bewertung
Kommentar von Orsovai
13.08.2016, 00:56

Für Dein konkretes Problem: ARIBAS bietet beispielsweise einige Funktionen für Primzahltests an, die Du in anderen Sprachen (wie den hier vorgeschlagen Java und C#) erst programmieren müsstest.

Java und C# sind Allrounder und deshalb sehr beliebt. Für einen so konkreten Zweck such Dir doch eine Spezialsprache und keinen Alleskönner ;)

0
Kommentar von lks72
13.08.2016, 07:31

Das kann ich bedenkenlos unterstützen. Aribas ist ein I Interpreter, mit dem sich zwar keine Stand alone Programme erzeugen lassen, zur Demonstration aller mathematischen Algorithmen aus der Zahlentheorie ist es aber super geeignet, es ist intuitiv und für diesen speziellen Zweck hervorragend geeignet.

0

Ruby eignet sich super für Einsteiger, dort erreichst du schnell gute Erfolge ohne dich zu sehr von der zugrundeliegenden Technik bremsen zu lassen. Ist ähnlich zu Python. Bei Matlab könnte ich mir vorstellen, dass die sogar schon eine Funktion implementiert haben, welche dir Primfaktoren ausspuckt.

Antwort bewerten Vielen Dank für Deine Bewertung

Java und c#, schnell und einfach zu lernen und sehr logisch. Gerade bei Zahlensystemen sind diese sehr praktisch

Antwort bewerten Vielen Dank für Deine Bewertung

Die Ermittlung der Primzahlen ist in jeder Sprache relativ einfach zu bewerkstelligen.

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?