✔ Lucas-Lehmer Test

[Philipp9494]

Hallo.

Auf http://primes.utm.edu/mersenne/index.html steht dieser Pseudocode für den Lucas-Lehmer Test:

Lucas_Lehmer_Test(p):
  s := 4;
  for i from 3 to p do s := s2-2 mod 2p-1;
  if s == 0 then
    2p-1 is prime
  else
    2p-1 is composite;

Daraufhin habe ich ihn in diesen C++-Code umgewandelt.

#include <iostream>
#include <math.h>
using namespace std;

void f_llt(int p) {
	int s=4;
	int M;
	for(int j=3;j<=p;j++) {
		M = (pow(2, p) - 1);
		s = ((s*s) - 2) % M;
	}
	if(s==0) {
		cout<<"(2^"<<p<<")-1 is prime\n";
	}
}

int main() {
	for(int i=2; i<700;i++) {
		f_llt(i);
	}
	return 0;
}

dieser gibt es aber nur bis 2^13-1 aus 2^17-1 sollte es u.a. auch ausgeben, aber hier ist Schluss!? Weis eventuell jemand wieso?

MfG
Philipp

 

[deepthroat]

Hi.

dieser gibt es aber nur bis 2^13-1 aus 2^17-1 sollte es u.a. auch ausgeben, aber hier ist Schluss!? Weis eventuell jemand wieso?

Ja: Integer-Overflow.

Du berechnest dort das Quadrat von ziemlich großen Zahlen. Für den Exponent 17 könnte die Eingabezahl s = 2^17-1 werden und das Resultat von s² liegt nicht mehr im Bereich eines int.

Verwende lieber double (oder unsigned long long wenn dein Compiler das unterstützt):

void f_llt(int p)                                                                                                               
{                                                                                                                               
  double s = 4.0;                                                                                                               
  const double M = pow(2, p) - 1;                                                                                               
                                                                                                                                
  for(int j=3;j<=p;j++)
    {
      modf(fmod(s*s - 2, M), &s);
    }

Gruß

 

[Philipp9494]

uh.. an dass hab ich ja gar nicht gedacht..

danke..