Programmierwettbewerb: Zahlen faktorisieren
- Ersteller i_hasser
- Erstellt am
Hi
Jetzt, wo wir Fibonacci Zahlen und Primzahlen durchhaben, wie wärs damit?
Irgendwo hat eine Uni ein Preisgeld auf einen Algorithmus ausgesetzt, der beliebige Zahlen mit einem Aufwand linear zur Zahlengröße in Primfaktoren zerlegt ($1.000.000 wenn ich mich richtig erinnere).
Sowas wird vll nicht rauskommen, aber da kann man sicher eine Menge optimieren.
Für alle die nicht wissen was eine Primfaktorenzerlegung ist:
jede beliebige ganze Zahl n>0 kann man durch folgenden Ausdruck darstellen:
n=(p[1]^x[1])*(p[2]^x[2])*(p[3]^x[3])*...*(p[m]^x[m])
(x ist eine natürliche Zahl)
p ist dabei die i-te Primzahl. Man kann also jede Zahl durch ein Produkt von potenzierten Primzahlen darstellen.
An einem Beispiel: n=528
528=2*264=2*2*132=2*2*2*66=2*2*2*2*33=2*2*2*2*3*11
528=(2^4)*(3^1)*(11^1) bzw. =(2^4)*(3^1)*(5^0)*(7^0)*(11^1) (da x^0=1)
Interessant wäre sicherlich auch ein Zahlensystem auf Primfaktorenbasis. Also wenn ich eine Zahl mit den Ziffern ABCDEF habe, könnte man diese so in eine Dezimalzahl umwandeln: Dez=(2^F)*(3^E)*(5^D)*(7^C)*(11^B)*(13^A)
Interessant daran ist, dass einige Rechenoperationen sehr einfach werden.
zb. (p)ABC*(p)DEF=(p)GHI -> G=A+D, H=B+H und I=C+F
Jetzt, wo wir Fibonacci Zahlen und Primzahlen durchhaben, wie wärs damit?
Irgendwo hat eine Uni ein Preisgeld auf einen Algorithmus ausgesetzt, der beliebige Zahlen mit einem Aufwand linear zur Zahlengröße in Primfaktoren zerlegt ($1.000.000 wenn ich mich richtig erinnere).
Sowas wird vll nicht rauskommen, aber da kann man sicher eine Menge optimieren.
Für alle die nicht wissen was eine Primfaktorenzerlegung ist:
jede beliebige ganze Zahl n>0 kann man durch folgenden Ausdruck darstellen:
n=(p[1]^x[1])*(p[2]^x[2])*(p[3]^x[3])*...*(p[m]^x[m])
(x ist eine natürliche Zahl)
p ist dabei die i-te Primzahl. Man kann also jede Zahl durch ein Produkt von potenzierten Primzahlen darstellen.
An einem Beispiel: n=528
528=2*264=2*2*132=2*2*2*66=2*2*2*2*33=2*2*2*2*3*11
528=(2^4)*(3^1)*(11^1) bzw. =(2^4)*(3^1)*(5^0)*(7^0)*(11^1) (da x^0=1)
Interessant wäre sicherlich auch ein Zahlensystem auf Primfaktorenbasis. Also wenn ich eine Zahl mit den Ziffern ABCDEF habe, könnte man diese so in eine Dezimalzahl umwandeln: Dez=(2^F)*(3^E)*(5^D)*(7^C)*(11^B)*(13^A)
Interessant daran ist, dass einige Rechenoperationen sehr einfach werden.
zb. (p)ABC*(p)DEF=(p)GHI -> G=A+D, H=B+H und I=C+F
Sargnagel
Commodore Special
- Mitglied seit
- 31.12.2001
- Beiträge
- 477
- Renomée
- 1
Nach ein wenig Recherche begreife ich jetzt, warum 1 Mio $ auf einen Algorithmus mit linearer Komplexität ausgesetzt wurden. Hier ist ein wenig Literatur:
Referat: Faktorisierung natürlicher Zahlen
Quanten-Computer (1.9 MB PDF)
Die Uni scheint genau zu wissen, daß ein solcher Algorithmus nicht existiert (?).
Referat: Faktorisierung natürlicher Zahlen
Quanten-Computer (1.9 MB PDF)
Die Uni scheint genau zu wissen, daß ein solcher Algorithmus nicht existiert (?).
Zuletzt bearbeitet:
mj
Technische Administration, Dinosaurier, ,
Die Idee an sich gefällt mir und ich werde mich auch diesmal wieder beteiligen an der Faktorisierung von Primzahlen. Wir sollten allerdings einige Regeln festlegen damit hier wieder eine gleiche Basis herrscht.
Also intel_hasser, es war deine Idee daher stellst du diesmal die Regeln auf.
Also intel_hasser, es war deine Idee daher stellst du diesmal die Regeln auf.
Tja, mal überlegen...
Als Programm kann so ziemlich alles herhalten, was man (auch wenn über Umwege) unter Linux und/oder Windoofs ausführen kann.
Programmiersprachen ist eigentlich auch ziemlich egal - sucht euch was raus
Ich werd bei meinem C/C++ bleiben
Benchmarks:
Ich denke da muss der Alg alle Zahlen in mehreren Intervallen Faktorisieren.
Also zb. alle in [1000;2000], [11000;12000] und [1001000;1002000], damit man auch sieht wie die Rechenzeit ansteigt.
Als schmankerl vielleicht noch eine sehr komplexe, sehr große Zahl (zb. 1'128'394'172, nur als Beispiel).
Aber alle Zahlen bleiben unter 2^31-1, also 32bit Integer dürften ausreichen.
Bei dem Algorithmus dürften auch Primzahlen eine große Rolle spielen, da kann sich jeder nehmen was er will - von meinem Alg hab ich ja den Source hingestellt, damit kann auch jeder machen was er will (nur gegen Geld verkaufen dürft ihr net).
Mit ein paar Modifikationen kann man da in praktisch 0s alle Primzahlen zwischen 0 und 1Mio ausrechnen (und die braucht man ja schließlich).
Tja, da fällt mir erstmal nix weiter ein. Ich fang denn mal an...
Als Programm kann so ziemlich alles herhalten, was man (auch wenn über Umwege) unter Linux und/oder Windoofs ausführen kann.
Programmiersprachen ist eigentlich auch ziemlich egal - sucht euch was raus
Ich werd bei meinem C/C++ bleiben
Benchmarks:
Ich denke da muss der Alg alle Zahlen in mehreren Intervallen Faktorisieren.
Also zb. alle in [1000;2000], [11000;12000] und [1001000;1002000], damit man auch sieht wie die Rechenzeit ansteigt.
Als schmankerl vielleicht noch eine sehr komplexe, sehr große Zahl (zb. 1'128'394'172, nur als Beispiel).
Aber alle Zahlen bleiben unter 2^31-1, also 32bit Integer dürften ausreichen.
Bei dem Algorithmus dürften auch Primzahlen eine große Rolle spielen, da kann sich jeder nehmen was er will - von meinem Alg hab ich ja den Source hingestellt, damit kann auch jeder machen was er will (nur gegen Geld verkaufen dürft ihr net
).Mit ein paar Modifikationen kann man da in praktisch 0s alle Primzahlen zwischen 0 und 1Mio ausrechnen (und die braucht man ja schließlich).
Tja, da fällt mir erstmal nix weiter ein. Ich fang denn mal an...
keine uni kann's sich leisten, mal eben 'ne mille preisgeld zu zahlen. die werden sich die sache wohl gut überlegt haben und wissen, daß sowas nicht ganz einfach ist - wenn nicht (mit zur verfügung stehender rechenzeit) unmöglich. und wenn du's schaffst, wäre das wohl auch auch das ende des RSA-verschlüsselungsalgoritmus - und den gibt's seit 25 jahren. viel spaß...
Das Ziel der Sache ist doch auch net das Preisgeld zu gewinnen (du wärest übrigens überrascht, wie oft Preisgelder von Unis ausgesetzt wurden ).
Schnapp dir mal irgend eine gute Lektüre zu Primzahlen. Wenn du da ein bisschen gelesen hast, wirst du Probleme haben hinterher zu kommen. Einfach weil das dann wirklich so extrem mathematisch wird, dass es keinen Spaß mehr macht. Da gibts teilweise Verfahren, auf die man nichtmal im Traum kommen würde.
Zurück zum Thema: Hier geht es eher darum den einfachsten und gleichzeitig schnellsten Algorithmus zu finden, den eine Person allein implementieren kann, und dann geht es auch darum diesen Algorithmus möglichst gut zu implementieren.
Sich da irgendwelche werweißwiekomplexe Algorithmen auszudenken... das ist Sache der Mathematiker
Aber manchmal kommt man nach längerem Überlegen auch zu wunderbar einfachen Dingen, siehe zb. die Fibonacci Zahlen.
Und zu guter letzt macht es Spaß! 8)
PS Bei den Zeiten können wir ja auch in Initialisierungszeit und Ausführungszeit unterscheiden, dann muss man nicht alles bis zum letzten Ende optimieren.
PPS Mit den Quantencomputern sind eh viele der Verschlüsselungsverfahren die wir kennen Wirkungslos, weil sie jeder Quantenrechner innerhalb weniger Sekunden per Brute Force geknackt hat
).Schnapp dir mal irgend eine gute Lektüre zu Primzahlen. Wenn du da ein bisschen gelesen hast, wirst du Probleme haben hinterher zu kommen. Einfach weil das dann wirklich so extrem mathematisch wird, dass es keinen Spaß mehr macht. Da gibts teilweise Verfahren, auf die man nichtmal im Traum kommen würde.
Zurück zum Thema: Hier geht es eher darum den einfachsten und gleichzeitig schnellsten Algorithmus zu finden, den eine Person allein implementieren kann, und dann geht es auch darum diesen Algorithmus möglichst gut zu implementieren.
Sich da irgendwelche werweißwiekomplexe Algorithmen auszudenken... das ist Sache der Mathematiker
Aber manchmal kommt man nach längerem Überlegen auch zu wunderbar einfachen Dingen, siehe zb. die Fibonacci Zahlen.
Und zu guter letzt macht es Spaß! 8)
PS Bei den Zeiten können wir ja auch in Initialisierungszeit und Ausführungszeit unterscheiden, dann muss man nicht alles bis zum letzten Ende optimieren.
PPS Mit den Quantencomputern sind eh viele der Verschlüsselungsverfahren die wir kennen Wirkungslos, weil sie jeder Quantenrechner innerhalb weniger Sekunden per Brute Force geknackt hat
Nein, ist es eben nicht!
Ich will das jetzt nicht in einen Diskussionsthread verwandeln - desswegen nur kurz die Begründung und dann ist gut.
Ein normaler Rechner rechnet mit einfachen Werten. Eine Variable hat einen bestimmten Wert.
Ein Quantenrechner rechnet mit Variablen, die alle möglichen Werte gleichzeitig annehmen.
Also wenn ich einem Quantenrechner sage char a,b;int c; c=b+a, dann nimmt c alle möglichen Ergebnisse dieser Gleichung zu einem einzigen Zeitpunkt ein.
So, und nun weg damit vom Tisch
Ich will das jetzt nicht in einen Diskussionsthread verwandeln - desswegen nur kurz die Begründung und dann ist gut.
Ein normaler Rechner rechnet mit einfachen Werten. Eine Variable hat einen bestimmten Wert.
Ein Quantenrechner rechnet mit Variablen, die alle möglichen Werte gleichzeitig annehmen.
Also wenn ich einem Quantenrechner sage char a,b;int c; c=b+a, dann nimmt c alle möglichen Ergebnisse dieser Gleichung zu einem einzigen Zeitpunkt ein.
So, und nun weg damit vom Tisch
So, die erste Version ist am Rennen. Ist noch relativ einfach gehalten, aber die Zeiten sind schonmal garnet so schlecht:
Initialisierungszeit 0.23s
Alle Zahlen zwischen 1000 und 2000 Faktorisieren: 0.01s
11000-12000: 0.01s
101000-102000: 0.09s
1001000-1002000: 0.81s
Mir reichts heute erstmal mit proggen, ich werd dann wohl morgen weitermachen.
Initialisierungszeit 0.23s
Alle Zahlen zwischen 1000 und 2000 Faktorisieren: 0.01s
11000-12000: 0.01s
101000-102000: 0.09s
1001000-1002000: 0.81s
Mir reichts heute erstmal mit proggen, ich werd dann wohl morgen weitermachen.
mj
Technische Administration, Dinosaurier, ,
Die Regeln sind klar und ich hab meine Prüfung hinter mir - werd mich ergo ab morgen mal in Java an eine Implementierung machen. Java mag zwar nicht das schnellste sein, aber es ist sehr eleganz und angenehm zu programmieren.
Vielleicht mach ich auch C/C++ mal sehen - aber da intel_hasser diese Liga bereits eingenommen hat tendiere ich wohl doch eher zu Java. In ML wird das ganze viel zu kompliziert, umständlich und bei so großen Zahlen auch viel zu langsam.
Vielleicht mach ich auch C/C++ mal sehen - aber da intel_hasser diese Liga bereits eingenommen hat tendiere ich wohl doch eher zu Java. In ML wird das ganze viel zu kompliziert, umständlich und bei so großen Zahlen auch viel zu langsam.
Update:
10'001'000 - 10'002'000: 8.03s
Ich sehs schon kommen, ich werd hier doch noch weitermachen. Ich hab ja sogar noch eine Pizza im Ofen, die erst in 20min fertig wird... da kann ich wohl kaum wiederstehen
So wie es aussieht verläuft der Aufwand für meinen Alg linear... aber da gibts sicher irgendwo eine Stelle, ab der die Zeit steil bergauf geht.
@D'Espice
Es geht auch ziemlich einfach, aber ich weis net wie viel optimierungspotenzial das hat. Aber so könnte man es theoretisch auch in ML problemlos implementieren (mit etwas C gewürzt).
Dafür hab ich auch eine Initialisierungsroutine dazu genommen...
10'001'000 - 10'002'000: 8.03s
Ich sehs schon kommen, ich werd hier doch noch weitermachen. Ich hab ja sogar noch eine Pizza im Ofen, die erst in 20min fertig wird... da kann ich wohl kaum wiederstehen
So wie es aussieht verläuft der Aufwand für meinen Alg linear... aber da gibts sicher irgendwo eine Stelle, ab der die Zeit steil bergauf geht.
@D'Espice
Es geht auch ziemlich einfach, aber ich weis net wie viel optimierungspotenzial das hat. Aber so könnte man es theoretisch auch in ML problemlos implementieren (mit etwas C gewürzt).
Dafür hab ich auch eine Initialisierungsroutine dazu genommen...
mj
Technische Administration, Dinosaurier, ,
Ein guter Anfang wäre doch alle Primzahlen zwischen Anfang und Ende zu ermitteln und in eine List/Tabelle/Array zu schreiben. Bei einem Array müsste man nach einmaligen Faktorisieren (also N -> N x N) einfach nur den Index um 1 erhöhen um auf die nächste Primzahl zu kommen.
Ich denke sogar, dass es nicht mal notwendig ist soviele Primzahlen zu errechnen, es müsste reichen von x(Anfang) bis sqr(y(Ende)-x)
Ich denke sogar, dass es nicht mal notwendig ist soviele Primzahlen zu errechnen, es müsste reichen von x(Anfang) bis sqr(y(Ende)-x)
Gib mir meinen Algorithmus wieder!
Aber es reicht nicht die Primzahlen bis sqrt(x) zu berechnen - wenn x selber eine Primzahl ist gehts nämlich schief.
Ich hab jetzt mal 2 Messungen gemacht, so ungefähr könnten wir das ja dann benchen.
1. Wie oben, also es werden alle Zahlen in einem Intervall konstanter Größe faktorisiert, die Basis steigt exponential an.
Also eben 100'000-101'000, 1'000'000-1'001'000 etc.
Und eben hab ich mal die linearität gemessen:
Initialisierungszeit (nur einmal vor allen Tests): 2.87s
90'000-110'000: 1.72s
999'000 - 1'001'000: 1.78s
9'999'900 - 10'000'100: 1.57s
99'999'990 - 100'000'010: 1.42s
Das das nun linear aussieht wird wohl an den Intervallen liegen, also dass kurz vor/nach einer so runden Zahl vermehrt einfach zu faktorisierende Zahlen auftauchen.
Aber es reicht nicht die Primzahlen bis sqrt(x) zu berechnen - wenn x selber eine Primzahl ist gehts nämlich schief.
Ich hab jetzt mal 2 Messungen gemacht, so ungefähr könnten wir das ja dann benchen.
1. Wie oben, also es werden alle Zahlen in einem Intervall konstanter Größe faktorisiert, die Basis steigt exponential an.
Also eben 100'000-101'000, 1'000'000-1'001'000 etc.
Und eben hab ich mal die linearität gemessen:
Initialisierungszeit (nur einmal vor allen Tests): 2.87s
90'000-110'000: 1.72s
999'000 - 1'001'000: 1.78s
9'999'900 - 10'000'100: 1.57s
99'999'990 - 100'000'010: 1.42s
Das das nun linear aussieht wird wohl an den Intervallen liegen, also dass kurz vor/nach einer so runden Zahl vermehrt einfach zu faktorisierende Zahlen auftauchen.
Zuletzt bearbeitet:
Hä .. wo ist das Problem ?
Code:
int start=528;
// (Primzahlen generieren)
int numbers[100] = {2,3,5,7,...,523};
int primeindex = 0;
Vector faktoren = new Vector();
while (start!=0 && primeindex < numbers.length) {
if (start%numbers[primeindex]) {
faktoren.addElement(Integer.toString(numbers[primeindex]));
start/=numbers[primeindex];
}
primeindex++;
}
}Welches Problem
Natürlich musst du vorher einige Primzahlen erzeugen, schreib mal einen Algorithmus der das bis 10'000'000 in wenigen ms macht
Und dann gehts natürlich auch net um Zahlen wie 523 die man im Kopf faktorisieren kann, sondern um deutlich größere und vor allem mehrere Zahlen.
Und da ist dann schon etwas optimierarbeit gefragt
Übrigens steigt schon die Zeit die der Alg zur Berechnung der Primzahlen braucht überlinear an.
Aber vielleicht gibts ja auch einen völlig anderen Ansatz mit dem man zum Erfolg kommt, die FPU kann ja bei Zahlen <2^32 auch genutzt werden, da muss man nicht erst irgendwelche extraroutinen implementieren.
Natürlich musst du vorher einige Primzahlen erzeugen, schreib mal einen Algorithmus der das bis 10'000'000 in wenigen ms macht
Und dann gehts natürlich auch net um Zahlen wie 523 die man im Kopf faktorisieren kann, sondern um deutlich größere und vor allem mehrere Zahlen.
Und da ist dann schon etwas optimierarbeit gefragt
Übrigens steigt schon die Zeit die der Alg zur Berechnung der Primzahlen braucht überlinear an.
Aber vielleicht gibts ja auch einen völlig anderen Ansatz mit dem man zum Erfolg kommt, die FPU kann ja bei Zahlen <2^32 auch genutzt werden, da muss man nicht erst irgendwelche extraroutinen implementieren.
ich schau mal nach den ergebnissen meines abgebrochenen projektes...
also:
größte geloggte primzahl: 019D978Bh (=27.105.163)
anzahl primzahlen in der datenbank: 1.703.210
macht bei 4 byte (32 bit) /primzahl: 6.812.840 bytes datenbankgröße
wie groß braucht man die primzahlen eigentlich ? ich meine, wenn's um extrem große zahlen n geht, wird der bereicht bis 32 bit sicher nicht reichen...
also:
größte geloggte primzahl: 019D978Bh (=27.105.163)
anzahl primzahlen in der datenbank: 1.703.210
macht bei 4 byte (32 bit) /primzahl: 6.812.840 bytes datenbankgröße
wie groß braucht man die primzahlen eigentlich ? ich meine, wenn's um extrem große zahlen n geht, wird der bereicht bis 32 bit sicher nicht reichen...
habe gerade mal ein paar auswertungs-scans durch meine db gemacht... ich wünsche euch allen noch viel spaß !!
damit euch der spaß nicht vergeht:
1. der kleinste abstand zweier primzahlen voneinander ist 2, der größte war 208. leider ist dazwischen immer alles vertreten, man kann also keine zahlenbereiche ausschließen.
2. der graph der ersten 1000 primzahlen (also blöde geschrieben y=x.te primzahl) sieht durch punkt 1 dermaßen huckelig aus, daß da sicher kein bissel linearität oder berechenbarkeit drinsteckt.
und wenn ich das mit primzahlen >10 stellen machen soll ... kann ich nur wiederholen: viel spaß...
wie gesagt, wenn's einer schafft, kannste pgp in die tonne treten. aber ich verdiene meine million besser woanders...
damit euch der spaß nicht vergeht:
1. der kleinste abstand zweier primzahlen voneinander ist 2, der größte war 208. leider ist dazwischen immer alles vertreten, man kann also keine zahlenbereiche ausschließen.
2. der graph der ersten 1000 primzahlen (also blöde geschrieben y=x.te primzahl) sieht durch punkt 1 dermaßen huckelig aus, daß da sicher kein bissel linearität oder berechenbarkeit drinsteckt.
und wenn ich das mit primzahlen >10 stellen machen soll ... kann ich nur wiederholen: viel spaß...
wie gesagt, wenn's einer schafft, kannste pgp in die tonne treten. aber ich verdiene meine million besser woanders...
Schau mal in den Primzahlen-Thread. Mein Alg hat zum Schluss für alle Primzahlen zwischen 1 und 4'000'000'000 120s gebraucht
Insgesammt gibt es in dem Bereich ~190'000'000 Primzahlen.
Und wie schon gesagt, wir wollen doch garnet auf einen Alg kommen der das in linearer Zeit schafft. Da zerbrechen sich Leute den Kopf drüber und gehen dabei Wege die für uns Normalsterbliche sowieso völlig unverständlich sind.
Dabei sind schon einige der bekannten Methoden praktisch unverständlich...
Insgesammt gibt es in dem Bereich ~190'000'000 Primzahlen.
Und wie schon gesagt, wir wollen doch garnet auf einen Alg kommen der das in linearer Zeit schafft. Da zerbrechen sich Leute den Kopf drüber und gehen dabei Wege die für uns Normalsterbliche sowieso völlig unverständlich sind.
Dabei sind schon einige der bekannten Methoden praktisch unverständlich...
Warum gehst du abends mit Kumpels in die Kneipe einen Saufen? Was ist der Sinn dahinter?
Ich mach das auf jeden Fall aus Spaß (Zahlen faktorisieren). Und abgesehen davon sorgts dafür, dass die letzten Grauen Zellen nicht auch noch absterben
Genausogut könnte ich fragen wieso du Schach spielst. Das ist sich schon erstaunlich ähnlich.
Ich mach das auf jeden Fall aus Spaß (Zahlen faktorisieren). Und abgesehen davon sorgts dafür, dass die letzten Grauen Zellen nicht auch noch absterben
Genausogut könnte ich fragen wieso du Schach spielst. Das ist sich schon erstaunlich ähnlich.
Sargnagel
Commodore Special
- Mitglied seit
- 31.12.2001
- Beiträge
- 477
- Renomée
- 1
Um die Grauen Zellen in Wallung zu halten.
Ich habe mir schon vor ein paar Tagen die Abstände der Primzahlen angeschaut. Erstaunlich sind die vielen Palindrome, die sich bilden; oder auch inverted repeats, um es mal molekularbiologisch auszudrücken. Hat eigentlich schon mal jemand einen Algorithmus zur Mustererkennung darauf losgelassen? Das wäre ähnlich zu Algorithmen zur Sequenzanalyse von Genen/Proteinen. Leider weiß ich von Dynamic Programming noch zu wenig, um das selber durchführen zu können ...
Zuletzt bearbeitet:
