[gelöst] Wie überschreiten des Wertebereichs richtig abfangen?

[Nestor]

Hallo,
hab ein kleines Problem.

Will ein Programm schreiben welches mir Potenzen ausrechnet. Das Programm soll 2 ganze Zahlen entgegen nehmen. Zuerst die Basis dann den Exponenten. Exponent soll zwischen 0 und ... liegen und die Basis darf auch negative Werte enthalten.

Das Problem ist, wenn ich z.B. 2^31 krieg ich -2147483648 raus. Warum der das macht versteh ich ja und das macht ja auch Sinn. Aber ich weiß nicht wie ich das abfangen soll.
Wenn ich das so schreibe, dass das Ergebnis zwischen INT_MIN und INT_MAX liegen muss funktioniert das trotzdem nicht weil dann 10^15=-1530494976 ist. Und das stimmt ja nicht.

Hier mal den Code wie er bisher aussieht.

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

int potenz(int basis, int exponent) {
	if (exponent == 0)
		return 1;
	else if (exponent == 1)
		return basis;
	else
		return basis * potenz(basis, exponent - 1);
}

int main(void) {
	int basis, exponent, check1, check2, ergebnis;
	while (1) {
		printf("\nPotenz: ...hoch... \n");
		printf("Bitte geben Sie die Basis und den Exponenten ein.\n\n");

		printf("Basis ...........:");
		check1 = scanf("%i", &basis);
		getchar();

		printf("Exponent.........:");
		check2 = scanf("%i", &exponent);
		getchar();

		if (check1 != 0 && check2 != 0)
			ergebnis = potenz(basis, exponent);
		if (ergebnis > INT_MIN && ergebnis < INT_MAX)
			printf("\n%i hoch %i ist gleich: %i\n", basis, exponent, ergebnis);
		else
			printf("\nWertebereich gesprengt\n");

	}
	return EXIT_SUCCESS;
}

[noobLolo]

evtl. kannst du erst die basis auf 2 umrechnen so ungefähr

double changeBaseToTwo(double in){
	return 1./(log(2.)/log(abs(in)));
}

mit dem rückgabe wert multiplizierst du den exponent und dann kannst ja einfach schauen ob der exponent < 31 ist

dann hast nur noch das problem das dir der log() nicht über läuft also eher das problem verschoben als aufgehoben

lg lolo

[noobboon]

noobLolo schrieb:

dann hast nur noch das problem das dir der log() nicht über läuft...

was ist denn das für ein quatsch

[inspire]

hallo nestor,

bei wrap arounds wird der wertebereich eines datentyps über-/unterschritten. du versuchst eine extrem hohe potenz auszurechnen, obwohl du nur ein (long) int benutzt. dessen wertebereich geht bis 2147483647, 2^31 wäre aber 2147483648. da kommt dann ein wrap around zustande, sodass du beim minimalen integer-wert landest. du hast nun zwei einfachere möglichkeiten:
1. anstatt int nimmst du float/double, da diese datentypen einen wesentlich größeren wertebereich bieten.
2. wenn du int behalten willst, könntest du es mit zwei variablen versuchen. du musst dann eine schleife entwickeln, die die beiden variablen versetzt hochlaufen lässt. wenn die erste variable einen negativen wert bekommt, hälst du die schleife an. da du die variablen versetzt laufen lässt, besitzt die andere variable dann die höchstmögliche integer-potenz.

sonst jemand noch andere ideen?

gruß
martin

[noobLolo]

noobLolo schrieb:

evtl. kannst du erst die basis auf 2 umrechnen so ungefähr

double changeBaseToTwo(double in){
	return 1./(log(2.)/log(abs(in)));
}

mit dem rückgabe wert multiplizierst du den exponent und dann kannst ja einfach schauen ob der exponent < 31 ist

@inspire
gefällt dir meine lösung nicht

btw. "double in" sollte > 1 sein das könnte noch mit rein

lg lolo

[noobLolo]

@inspire
hab mir das nochmal durch den kopf gehen lassen und mir gefällts von sekunde zu sekunde besser, poste mal meine umsetzung deines vorschlags

#include <stdio.h>
#include <stdlib.h>

int powSave(int base,int exp,int *ret){
	int cache = base;
	int ccache = cache;//falls 0
	if(base>0){
		while(--exp)
			if((cache *= base)>0)
				ccache = cache;
			else
				return 0;
	}else if(base<0){
		while(--exp)
			if((cache *= -base)<0)
				ccache = cache;
			else
				return 0;
	}
	*ret = ccache;
	return 1;
}

int main(void) {
	int base = 2;
	int exp = 31;
	int ret;
	if(powSave(base,exp,&ret))
		printf("%d",ret);
	else
		printf("number overflow");

	return 0;
}

lg lolo

[noobLolo]

natürlich wäre es schöner eine zeile unter z.13 mit

base = -base;

einzufügen und dann in z.15

if((cache *= base)<0)

da es keinen sinn macht einen zu kleinen wert raus zu geben reicht auch das return 0; natürlich könnte man da noch *ret setzen aber naja und es ist ja auch schon etwas später da sei mir der ein oder andere bug vergönnt

die tierchen wollen doch auch leben^^, was wär eine welt ohne bugs

lg lolo

[;fricky]

inspire schrieb:

sonst jemand noch andere ideen?

der OP kann in seine funktion einen überlauf-test einbauen, etwa so:

int potenz(int basis, int exponent) 
{
   if (exponent == 0)
      return 1;
   else
   {
      int n = potenz(basis, exponent - 1);
      int p = basis * n;
      if (n != 0 && p/n != basis)  // multiplikation muss umkehrbar sein, sonst overflow
         return 0;
      return p;
   }
}

int main(void) 
{
   printf ("%d\n", potenz (2, 30));
   printf ("%d\n", potenz (2, 31));
   printf ("%d\n", potenz (-1000, 3));
   printf ("%d\n", potenz (-10000, 3));
}

[Nestor]

Wow, ich bin echt geschockt, wie viele Antworten in weniger als 24 Stunden hier stehen.

Mir persönlich gefällt die Idee von inspire auch am besten.

@noobLolo
Jetzt hast du mir ja schon ganze Arbeit abgenommen. Trotzdem danke.

Das einzige was noch rein muss ist, wenn der Exponent 0 ist muss 1 rauskommen.

Ansonsten würde ich sagen Problem gelöst.

[inspire]

nebenbei: wieso benutzt du nicht einfach float/double-variablen?

[Nestor]

Wenn ich float oder double nehme dann ändert sich doch vom Prinzip nichts, außer das mein Wertebereich größer wird.

Und dann hat sich mein Problem ja auch nicht geändert nur das es bei größeren Zahlen kommt.

[;fricky]

Nestor schrieb:

@noobLolo
Jetzt hast du mir ja schon ganze Arbeit abgenommen. Trotzdem danke.

funzt aber nicht richtig. gib mal für 'base' werte nahe an INT_MAX ein und kleine exponenten, z.b:

int base = INT_MAX-10;
int exp = 2;

^^ ergibt 121, kann ja irgendwie nicht sein. *fg*

[Nestor]

@;fricky
Ja ich bin auch gerade über ne Rechnung gestolpert die keinen Sinn macht.

Ich hab 10^10 getestet kommt auch Unsinn raus.

Ich glaube das Problem ist das es je nach Zahlenbeispiel genau so passt das der negative Teil genau übersprungen wird. Und dann greift das nicht mit dem Vorzeichentest.

Ich glaube die Idee von ;fricky mit der Überprüfung ob die Rechnung umkehrbar ist ist, könnte das lösen.
Ich teste es mal und poste dann den Code.

[Nestor]

So ich hab jetzt mal sogut durchprobiert wie es ging. Hab auf jeden Fall keine Kombination gefunden, die was falsches ausgibt. In der main Funktion ist natürlich noch jede Menge unnützes die nur der Optik dienen, denkst euch einfach weg.

#include <stdio.h>
#include <stdlib.h>

int powSave(int basis, int exponent, int *ret) {
	int cache = basis, puffer;
	if (!exponent)
		*ret = 1;
	else if (!basis)
		*ret = 0;
	else if (exponent > 0) {
		while (--exponent) {
			puffer = cache;
			cache *= basis;
			if (cache / puffer != basis)
				return 0;
		}
		*ret = cache;
	} else
		return 0;
	return 1;

}

int main(void) {
	int check1, check2, ret;
	int basis, exponent;
	while (check1 != 0 || check2 != 0) {
		printf("Bitte geben Sie die Basis und den Exponenten ein.\n");
		printf("Mit der Eingabe von 2 Buchstaben beenden.\n\n");

		printf("Basis ...........:");
		check1 = scanf("%i", &basis);
		getchar();

		printf("Exponent.........:");
		check2 = scanf("%i", &exponent);
		getchar();

		if (check1 != 0 && check2 != 0 && powSave(basis, exponent, &ret))
			printf("Ergebnis.........:%i\n\n", ret);
		else
			printf("ERROR\n");
		printf("-----------------------------\n\n");
	}
	return EXIT_SUCCESS;
}

[;fricky]

Nestor schrieb:

So ich hab jetzt mal sogut durchprobiert wie es ging. Hab auf jeden Fall keine Kombination gefunden, die was falsches ausgibt.

na, wenn's jetzt klappt, musste nur noch 'nen tolleren potenzier-algo nehmen, der weniger ackern muss. z.b. sowas hier: http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Computation_by_powers_of_2

[Nestor]

@;fricky
Interessant zu wissen das es sowas gibt!
Der Code soll jedoch auch von anderen Mitstudenten gelesen werden können, und deswegen benutze ich lieber die klassische, wenn auch nicht effiziente x*x*x*...*x*x*x Variante.

Hier kann man den Artikel auch in deutsch finden:http://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation

[seldon]

Äh...

if(zwischenergebnis > INT_MAX / (double) basis) {
  return EXIT_FAILURE;
}

?

[;fricky]

seldon schrieb:

Äh...

if(zwischenergebnis > INT_MAX / (double) basis) {
  return EXIT_FAILURE;
}

?

^^funzt doch auch nicht. schau mal hier: http://www.scipub.org/fulltext/jcs/jcs13304-309.pdf
dritte seite, links unten: Overflow = (((a.. *fg*

[seldon]

Das ganze jetzt so zu normalisieren, dass basis positiv ist, ist nun wirklich trivial, und für alle relevanten Fälle ist das zwischenergebnis >= basis, also reicht das so schon aus.

[;fricky]

seldon schrieb:

Das ganze jetzt so zu normalisieren, dass basis positiv ist, ist nun wirklich trivial, und für alle relevanten Fälle ist das zwischenergebnis >= basis, also reicht das so schon aus.

^^zeig doch mal ein komplettes beispiel, z.b. eine 'mult'-funktion, die überläufe erkennt.

[seldon]

#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

int hoch_aux(int *cache, unsigned basis, unsigned exponent) {
  if(exponent % 2 == 1) {
    if(hoch_aux(cache, basis, exponent - 1) || *cache > INT_MAX / (double) basis) {
      return EXIT_FAILURE;
    }

    *cache *= basis;
  } else if(exponent != 0) {
    static double intmax_sqrt = sqrt(INT_MAX);

    if(hoch_aux(cache, basis, exponent / 2) || *cache > intmax_sqrt) {
      return EXIT_FAILURE;
    }

    *cache *= *cache;
  }

  return EXIT_SUCCESS;
}

int hoch(int *result, int basis, unsigned exponent) {
  int cache = 1, err = EXIT_FAILURE;

  err = hoch_aux(&cache, abs(basis), exponent);
  cache *= 1 - 2 * (basis < 0 && exponent % 2 == 0);

  if(err == EXIT_SUCCESS) {
    *result = cache;
  }

  return err;
}

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

  if(argc == 3 && !hoch(&x, atoi(argv[1]), atoi(argv[2]))) {
    printf("%d\n", x);
  } else {
    return -1;
  }

  return 0;
}