Programm klappt nicht bei großen Zahlen (D&Q)

deavilaxn

Aufgabenstellung:
http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss11/info2/Ueb/blatt6_ss11.pdf
Nicht fertiges Programm:
http://www-ai.math.uni-wuppertal.de/SciComp/teaching/ss11/info2/Ueb/Blatt6/potenzen_mod.c

Aufgabe 1 b)

Ich habe die 1b) soweit fertig gemacht. Unten im Programmcode sieht man, wo ich meinen D&Q Algorithmus eingefügt habe. Das Problem bei meinem Algorithmus ist, dass er nicht bei großem p funktioniert und ich weiss nicht wieso. Der andere langsamere Algorithmus (vorgegeben) geht ohne Probleme bei großem p.

/******************************************************/
/* AuDSS11 - Matthias Rottmann                        */
/* Potenzen, Divide & Conquer                         */
/* Rahmenprogramm                                     */
/******************************************************/

#include <stdio.h>
#include <time.h>

typedef long int datatype;

/* Um die Zeitmessung sichtbar zu machen  */
void waste_some_time( void )
{
  int i;
  for(i=0;i<5000000;i++);
}

/* Ihr Devide&Conquer Algorithmus */
datatype potenz_dc( int a, int n, int p )
{
  waste_some_time(); // <--- nicht löschen!!!

  // IMPLEMENTIEREN!!!
	if (n==1) return a; /* Falls n==1*/
	int y=1;
	int z;
	if (n%2) /*Bei ungerade Zahlen*/
	{
		n-=1 ; /*ungerade zu gerade*/
		y=a;
	}

	z=potenz_dc(a, n/2 ,p ); /*berechne per Rekursion mit halbiertem Wert*/
	return ((z%p)*(z%p)*y)%p; /*Ausgabe*/

}

/* Der langsame Ansatz : a^n = ( a * ( a^n-1 mod p ) ) mod p  */
datatype potenz_schleife( int a, int n, int p )
{
  datatype y=1;
  int i;
  for(i=0;i<n;i++) {
    waste_some_time();
    y = (y%p)*a;
  }
  return y%p;
}

int main(void)
{

  int a, n, p;
  datatype y;

  /* x,n einlesen */
  printf("Geben Sie a ein: ");
  scanf("%d",&a);
  printf("Geben Sie n ein: ");
  scanf("%d",&n);
  printf("Geben Sie p ein: ");
  scanf("%d",&p);

  /* Variablen zur Zeitmessung */
        clock_t dc_start, dc_ende;
	clock_t ps_start, ps_ende; 

	/* Zeitmessung und Ausführung des Devide&Conquer-Algorithmus  */
	dc_start=clock();
	y = potenz_dc(a,n,p);
	printf("Mit Divide&Conquer: (%d hoch %d) mod %d = %d\n", a, n, p, y);
        dc_ende=clock();
        printf("Laufzeit %.2f Sekunden\n\n",((float)(dc_ende-dc_start)) / CLOCKS_PER_SEC);

	//getchar();

	/* Zeitmessung und Ausführung des rekursiven Algorithmus zum trivialen Ansatz  */
	ps_start=clock();
	y = potenz_schleife(a,n,p);
	printf("Mit trivialem Ansatz: (%d hoch %d) mod %d = %d\n", a, n, p, y);
        ps_ende=clock();
        printf("Laufzeit %.2f Sekunden\n\n",((float)(ps_ende-ps_start)) / CLOCKS_PER_SEC);

	//getchar();
        return 0;
}

SeppJ

Was heißt hier groß und was genau ist der Fehler?

deavilaxn

Groß würde bei mir heissen 444.444 z.B. und der Fehler ist der, dass eine 0 ausgegeben wird.

Edit:
Eingabe:
a=2
n = 1024
p = 4567

Meine Algorithmus-Lösung: 2978, laufzeit 0.10

der andere: 2978, Laufzeit 9.91 Sekunden

Eingabe a=2
n=256
p = 444444
meiner : laufzeit 0.08 lösung: 0

der andere laufzeit 2,44 lösung 161632

SeppJ

Wenn ich die internen Datentypen auf long long ändere, passt es. Folgerung: Da läuft etwas über. Höchstwahrscheinlich dieser Ausdruck hier (z%p)*(z%p)*y), wo leicht etwas von der Größenordnung p^2*y rauskommen kann. Habe ich aber nicht explizit geprüft, sonder ist nur Erfahrung.

deavilaxn

Danke Dir.

Habe jetzt anstatt int z: long z; genommen und es klappt.

Von mir gibt es keine weitere Fragen. Der Code ist nicht wirklich schön, aber erfüllt seinen Zweck

deavilaxn schrieb:

Von mir gibt es keine weitere Fragen.

Hat ein wenig was von den Nachmittags-Gerichtssendungen...
"Keine weiteren Fragen, haben Sie noch was, Staatsanwalt Römer?" - "Nein, Frau Vorsitzende." - "Dann erkläre ich das Buffet hiermit für eröffnet *HAMMER*"

Programm klappt nicht bei großen Zahlen (D&amp;Q)

Programm klappt nicht bei großen Zahlen (D&Q)