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

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 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

@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

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

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.

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;
}

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

Äh...

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

?

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*

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.

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.

#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;
}

^^mag ja sein dass dein code geht, aber der ist ja wohl viel komplizierter als die anderen vorschläge hier. *fg*