ZahlReich - Mathematik Hausaufgabenhilfe: Mersenne'sche Primzahlen

Mersenne'sche Primzahlen

ZahlReich - Mathematik Hausaufgabenhilfe » Universitäts-Niveau » Mathematik für Informatiker » Mersenne'sche Primzahlen « Zurück Vor »

Das Archiv für dieses Kapitel findest Du hier.

Autor

Beitrag

Mainziman (Mainziman)

Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 596
Registriert: 05-2002

Veröffentlicht am Montag, den 22. Dezember, 2003 - 02:35:

Mersenne 40 ist entdeckt: 2^20996011-1 ist prim :-)

Was mich in dem Zusammenhang interessieren würde,
wie geht man bei derartig großen Zahlen vor, um zu zeigen, daß sie prim sind?

Weiters: Mathematica 4.2 benötigte auf meinem
iPentiumIV 2.4 GHz weniger als 100 sec. zum Berechnen aller Stellen dieser Primzahl;

mein eigenes Programm, welches mit allen Schikanen optimiert (Assembler, u. a.) ist, benötigt dafür aber beinahe 100 min., mein Algorithmus: Umrechnung der Dualzahl (lauter 1en) durch permanentes Dividieren durch 1 0000 0000, so lange bis die Zahl nur noch Rest liefert, sprich kleiner als 100000000 ist; damit erhalte ich 8stellige Blöcke im Dezimalsystem, welche ich einfach ausgeben kann;
Ist der Algorithmus schlecht?
Wo liegt das Problem, daß mein Program derart lange braucht?
(auf einem Athlon XP 2400 benötigt es noch länger)

Wer weiß das Problem/Rat oder kennt einen pfeilschnellen Algorithmus?

Oder hat Mathematica gar Tabellen und rechnet gar nicht?

Gruß,
Walter

Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*

Panther (Panther)

Erfahrenes Mitglied
Benutzername: Panther

Nummer des Beitrags: 127
Registriert: 04-2003

Veröffentlicht am Montag, den 29. Dezember, 2003 - 09:52:

Du kannst dies selbst berechnen, indem du mit Modulo rechnest.

Wenn du wissen willst, wie das geht, dann schick mir doch ne Mail - das hier aufzuschreiben dauert mir jetzt zu lange.... und Mails kann ich offline verfassen.

Murray (Murray)

Erfahrenes Mitglied
Benutzername: Murray

Nummer des Beitrags: 223
Registriert: 10-2001

Veröffentlicht am Montag, den 29. Dezember, 2003 - 10:13:

Hallo Mainziman,

schau ma hier: http://www.mersenne.org/math.htm
(Das beschreibt zumindest den Test einer solchen Zahl)

Zur Stellenberechnung: scheint recht simpel zu sein, schließlich ist diese Zahl ja schon eine 2'er Potenz (binaer 1111...111 (20996010 mal 1)).
Der Aufwand sollte sich deshalb in Grenzen halten.

Cu Danny

Mainziman (Mainziman)

Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 605
Registriert: 05-2002

Veröffentlicht am Montag, den 29. Dezember, 2003 - 14:27:

Hi Danny,

Würde die Programmiersprache einen Gigantointeger kennen dann ja, aber so scheint es doch verdammt viel Aufwand zu sein, weil ja mit maximal 64bit

gerechnet werden kann;

Gruß,
Walter

Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*

Friedrichlaher (Friedrichlaher)

Senior Mitglied
Benutzername: Friedrichlaher

Nummer des Beitrags: 1893
Registriert: 02-2002

Veröffentlicht am Montag, den 29. Dezember, 2003 - 17:04:

die Zahl hat also 6 320 430 Dezimalstellen;
in
einem 32Bit Wert speicherst Du davon 9,
brauchts also long Zahl[2809080];
und
ich würde nicht primär mit "Dividieren"
arbeiten,
sondern mit "Hornerschema":

20996011 = 29*724000+11, (* weil 2²⁹<10⁹<2³⁰ *)
also

"Zahl = 2^11 - 1" (* die 1ten 11 Einsen *)

"for(i=724000; i--;;) Zahl = Zahl*2²⁹+(2²⁹-1);"
-------------
"in Anführungszeichen" gesetzt habe ich
die Anweisungen, weil die Rechnung naürlich
mit der Zahlenbasis 10⁹ efolgen muß .
Ich empfehle mit Integern zu rechnen;
Ich nehme an, die verwendete Programmiersprache
bietet eine Divisionsroutine die aufeinmal
Quotienten und Rest zurückgibt,
ideal wäre natürlich dafür Assembler zu verwenden

Wenn das Erlernen der Mathematik einigermaßen ihre Erfindung wiederspiegeln soll, so muß es einen Platz für Erraten, für plausibles Schließen haben.
[Aus dem Vorwort zu "Mathematik und plausibles Schliessen, Bd. 1 Induktion und Analogie in der Mathematik" von Georg Pólya]

Mainziman (Mainziman)

Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 606
Registriert: 05-2002

Veröffentlicht am Montag, den 29. Dezember, 2003 - 20:55:

Hallo Fritz,

so sieht mein C Programm aus, welches ich mit Assembler feintune, und das hat eine längere laufzeit, weil multipliziert wird und zusätzlich eben dividiert :-(

Gruß,
Walter

#include <stdio.h>

const unsigned modval = 1000000000;

static unsigned num[ 2809080 ];

int main( int argc, char* argv[] )
{
int i;

for ( i = 0; i < 2809080; i++ )
num[ i ] = 0;

num[ 0 ] = 2047;

for ( i = 0; i < 724000; i++ )
{
int j = -1;

unsigned next;

next = 536870911;

while ( num[ ++j ] | next )
{
unsigned __int64 n = num[ j ];

n <<= 29;
n += next;

next = (unsigned) ( n / modval );
num[ j ] = (unsigned) ( num % modval );
}

if ( ( i % 724000 ) == 0 )
printf( "\r %2d percent done ...", i / 7240 );
}

printf( " 2^20996011-1 done.\n\n" );

for ( i = 0; i < 2809080; i++ )
printf( "%09u", num[ 2809080 - i ] );

return 0;
}

Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*

Friedrichlaher (Friedrichlaher)

Senior Mitglied
Benutzername: Friedrichlaher

Nummer des Beitrags: 1895
Registriert: 02-2002

Veröffentlicht am Montag, den 29. Dezember, 2003 - 22:00:

ok,
statt
num[ j ] = (unsigned) ( num % modval );
muss es wohl
num[ j ] = (unsigned) ( n % modval );
lauten
und da liegt das Beschleunigungspotential,
da
der Ass.befehl DIV EDX:EAX, #modval
ja Quotienten und Rest bereits liefert;
das ganze whileSchleife
ist in assembler wahrscheinlich
fast auschschließlich mit Registern zu bewältigen

Mainziman (Mainziman)

Senior Mitglied
Benutzername: Mainziman

Nummer des Beitrags: 608
Registriert: 05-2002

Veröffentlicht am Montag, den 29. Dezember, 2003 - 22:23:

Hallo Fritz,

ich kenne das Beschleunigungspotential, nur mein Proggi machts halt ohne der Multiplikation es dividiert einfach nur so, wie von Dir geschildert;
weil ich ja bereits die Riesenzahl als internes Format habe, kann man als Konstante hineinprogrammieren; und damit brauchts knapp 100 mins. :-(

Gruß,
Walter

Mainzi Man,
ein Mainzelmännchen-Export,
das gerne weiterhilft
oder auch verwirren kann *ggg*

Administration Abmelden Previous Page Next Page