Prim-Programm (Fabrice Bellard) strukturieren

[osculumobscenum]

Hallo zusammen!

Zuallererst : Ich bin nicht in C zuhause sondern verfüge da nur über sehr begrenzte Einblicke. Pascal und ein wenig Assembler sind eher mein Ding, daher brauche ich hier ein wenig Hilfe.
Ich habe auf der Homepage von Fabrice Bellard (der könnte dem einen oder anderen hier ein Begriff sein) ein kleines C-Programm gefunden, das eine irrsinnig hohe Primzahl festlegt und als Primzahl verifiziert und dann ausgibt. Leider hat er das im Rahmen eines "wer schreibt das kleinste Programm"-Wettbewerb gemacht, so dass ich NULL davon verstehe, aber ich hoffe, dass hier irgendjemand das Ding ein wenig zerlegen kann, so dass es lesbar wird.

Hier mal der Quellcode :

Code: Alles auswählen

int m=1811939329,N=1,t[1<<26]={2},a,*p,i,e=73421233,s,c,U=1;g(d,h){for(i=s;i<1<<
25;i*=2)d=d*1LL*d%m;for(p=t;p<t+N;p+=s)for(i=s,c=1;i;i--)a=p[s]*(h?c:1LL)%m,p[s]
=(m*1U+*p-a)*(h?1LL:c)%m,*p=(a*1U+*p)%m,p++,c=c*1LL*d%m;}main(){while(e/=2){N*=2
;U=U*1LL*(m+1)/2%m;for(s=N;s/=2;)g(136,0);for(p=t;p<t+N;p++)*p=*p*1LL**p%m*U%m;
for(s=1;s<N;s*=2)g(839354248,1);for(a=0,p=t;p<t+N;)a+=*p<<(e&1),*p++=a%10,a/=10;
}while(!*--p);for(t[0]--;p>=t;)putchar(48+*p--);}

Ich kann das Programm unter Debian Linux mit gcc problemlos compilieren, es wird dann auch rund 256 MB (!) groß, und es läuft auch, indem es nach einer gewissen Rechenzeit eine riesengroße Zahl ausgibt. mit einer Umleitung wie "./prim > output.txt" kann die ausgegebene Zahl in eine Datei umgeleitet werden, was sich dann rund 21 MB genehmigt.

ABER : Ich verstehe NULL von dem Programm. Kann das vllt mal jemand ansehen?

Als Quelle nenne ich hier noch https://www.bellard.org/mersenne.html , da ist das Programm her.

Danke im Voraus!

[Xin]

Zuallererst : Ich bin nicht in C zuhause sondern verfüge da nur über sehr begrenzte Einblicke. Pascal und ein wenig Assembler sind eher mein Ding, daher brauche ich hier ein wenig Hilfe.

Soso.

Und wofür brauchst Du diese Hilfe?

Ich habe auf der Homepage von Fabrice Bellard (der könnte dem einen oder anderen hier ein Begriff sein) ein kleines C-Programm gefunden, das eine irrsinnig hohe Primzahl festlegt und als Primzahl verifiziert und dann ausgibt. Leider hat er das im Rahmen eines "wer schreibt das kleinste Programm"-Wettbewerb gemacht, so dass ich NULL davon verstehe, aber ich hoffe, dass hier irgendjemand das Ding ein wenig zerlegen kann, so dass es lesbar wird.

ABER : Ich verstehe NULL von dem Programm. Kann das vllt mal jemand ansehen?

Auf der Website steht: "A previous version of this program to compute 26972593-1 won the International Obfuscated C Code Contest of Year 2000."

Es geht nicht um das kleinste Programm, sondern um das unleserlichste Programm.
Daraus lesbaren Code zu machen, ergibt keinen Sinn. Verstehe die Art, wie das Programm entstanden ist und schreib es sauber.

Eine Sache hat mich allerdings interessiert... das bisschen Code soll zu 256MB kompilieren? Und das tut es tatsächlich.

Code: Alles auswählen

int m=1811939329,N=1,t[1<<26]={2}...

Erzeugt ein statisches Array "t" mit 64 Millionen ints, die jeweils 4 Byte groß sind, macht 256MB. Das würde man sonst wohl so auch nicht machen.

Aber dann habe ich aufgehört zu lesen. Das ist kein Code, den man verstehen will.

[osculumobscenum]

Aber dann habe ich aufgehört zu lesen. Das ist kein Code, den man verstehen will.

Ich würde ihn schon gerne verstehen, aber ich kann der Syntax nicht folgen.

Was mich am meisten interessiert ist, wie genau er diese sehr sehr große Zahl speichert (ohne Nutzung irgendwelcher externen BigNumber-Bibliotheken), und wie er dann damit Berechnungen durchführt. (Ich vermute mal, das muss er, da er ja sichergehen will, dass es auch wirklich eine Primzahl ist) .

Aber das ist schon alles sehr kryptisch, da geb ich dir schon recht.

[Xin]

Ich würde ihn schon gerne verstehen, aber ich kann der Syntax nicht folgen.

Das Programm ist so geschrieben, dass Du ihm nicht folgen können sollst.

Und so gerne ich Leuten versuche zu helfen, Dinge zu verstehen... das ist gemacht, um nicht verstanden zu werden. Und da solltest Du vielleicht das Programm anfordern, bevor sämtliche Dokumentation entfernt wurde und Variablennamen auf einen Buchstaben reduziert wurden.

Was mich am meisten interessiert ist, wie genau er diese sehr sehr große Zahl speichert (ohne Nutzung irgendwelcher externen BigNumber-Bibliotheken), und wie er dann damit Berechnungen durchführt. (Ich vermute mal, das muss er, da er ja sichergehen will, dass es auch wirklich eine Primzahl ist) .

Er nimmt offensichtlich einen 256MB großen Speicherblock.