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

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*

Wenn Performance und Fehlerfall-Garantien dich nicht interessieren, kannst du's auf

int hoch_aux(int *cache, unsigned basis, unsigned exponent) {
  if(exponent == 0) return EXIT_SUCCESS;

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

  *cache *= basis;

  return EXIT_SUCCESS;
}

int hoch(int *result, int basis, unsigned exponent) {
  int err;

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

  return err;
}

zusammenstreichen, aber ich halte es nicht für sinnvoll, derart dreckige Praktiken zu verbreiten.

seldon schrieb:

aber ich halte es nicht für sinnvoll, derart dreckige Praktiken zu verbreiten.

hab's mal ausprobiert, der zweite code tuts nicht bei mir. der erste aber schon.

Eh, tschuldigung.

int hoch(int *result, int basis, unsigned exponent) {
  int err;

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

  return err;
}

ach du heiliges potenzmittel. erst ein abs, damit der grösser-vergleich geht, dann alles auf 'double' aufblasen und mit dem: *result *= 1 - 2 * (basis < 0 && exponent % 2 == 0) wird am schluss das vorzeichen wiederhergestellt, ne? das ist doch etwas zu umständlich, finde ich. *fg*