Prim-Programm (Fabrice Bellard) strukturieren
Verfasst: Do Aug 24, 2023 7:25 pm
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 :
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!
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--);}
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!