Funkcja intpower - na jakiej zasadzie działa

Witam,
poniższy program liczy potęgi liczb. Działać działa.

#include <stdio.h>

// x - liczba potegowana
// n - wykladnik


double intpower(double x, int n)
{
	double tmp; // - zmienna do obliczen
	double answer; // - wynik
		if(n==0) { answer=1; }
		else if(n==1) { answer=x; }
			else if(n%2==0) { 
			        tmp = intpower(x , n/2);
				answer=tmp*tmp;
			} else {
				tmp = intpower(x , n/2*x);
				answer=tmp*tmp;
			}
return answer;			
}


main()
{
	double x;
	int n;
	printf("Podaj liczbe potegowana: ");
	scanf("%lf" , &x);
	printf("Podaj wykladnik: ");
	scanf("%d" , &n);
	printf("%lf \n", intpower(x,n));
} 

Tylko mógłby mi ktoś wytłumaczyć na jakiej zasadzie działa ten kod:

tmp = intpower(x , n/2);
answer=tmp*tmp;

O co chodzi z tym sprawdzaniem potęgi czy jest parzysta? Bo jeśli jest to czemu trzeba wprowadzić jako wykładnik to n/2. I jaki wynik jest równy tmp, że trzeba go pomnożyć przez siebie (druga część)? I to samo przy sprawdzaniu czy wykładnik nie jest parzysty. Dlaczego jest coś takiego - n/2*x?

ten kod nie może działać, sprawdź co ci powie na 10 ^ 3

_13th_Dragon napisał(a):

ten kod nie może działać, sprawdź co ci powie na 10 ^ 3

O kurna, faktycznie. Zawiesił się. Czym może być spowodowany ten błąd? :-/

EDIT: Ok, już mam. Zamieniłem z n/2*x na n-1 i działa.

No dobra, tylko dalej nie rozumiem jak to działa.

EDIT 2: Fakt, fakt. Zrobiłem w ten sposób:

				tmp = intpower(x , n-1);
				answer=tmp*x;

I teraz wynik jest prawidłowy.

Czy nie lepiej zrobić to po bożemu?

double intpow(double x,unsigned n)
  {
   double answer;
   for(answer=1;n;x*=x,n>>=1) if(n&1) answer*=x; // n>>=1 można zamienić na n/=2, n&1 można zamienić na n%2
   return answer;
  }

A jak koniecznie chcesz rekurencyjną wersje to:

double intpower(double x, int n)
  {
   if(n==0) return 1;
   if(n&1) return x*intpower(x*x,n>>1);// n>>=1 można zamienić na n/=2, n&1 można zamienić na n%2
   return intpower(x*x,n>>1);// n>>=1 można zamienić na n/=2
  }

Muszę właśnie rekurencyjnie. Teraz powinno być wszystko ok? Bo wyniki wychodzą prawidłowe.

 #include <stdio.h>

// x - liczba potegowana
// n - wykladnik

double intpower(double x, int n)
{
	double tmp; // - zmienna do obliczen
	double answer; // - wynik
		if(n==0) { answer=1; } // jeśli wykładnik jest rowny 0 przypisz to wynik(answer) rowny 1
		else if(n==1) { answer=x; } // jesli natomiast wykladnik jest rowny 1 to wynik(answer) rowny liczbie potegowania(x)
			else if(n%2==0) { // jezeli wykladnik jest parzysty czyli reszta z dzielenia przez 2 jest rowna 0...
				answer = intpower(x*x, n/=2); // przypisz do zmiennej answer wynik z funckji intpower
			} else { // jezeli wykladnik nie jest parzysty...
				answer = x*intpower(x*x, n/=2); // przypisz do zmiennej answer wynik z funckji intpower
			}
return answer;			
}

main()
{
	double x;
	int n;
	printf("Podaj liczbe potegowana: ");
	scanf("%lf" , &x);
	printf("Podaj wykladnik: ");
	scanf("%d" , &n);
	printf("%lf \n", intpower(x,n));
}

Tylko wracając do pierwotnego pytania co robi ta funkcja - intpower(x*x, n/=2)? Jaki wynik zwraca? I dlaczego, gdy wykładnik jest nieparzysty to trzeba całość przemnożyć przez liczbę potęgowaną?

x^15 = x^(1+2+4+8) = x^1 * x^2 * x^4 * x^8
x^10 = x^(2+8) = x^2 * x^8

_13th_Dragon napisał(a):

x^15 = x^(1+2+4+8) = x^1 * x^2 * x^4 * x^8
x^10 = x^(2+8) = x^2 * x^8

Szczerzę to dalej średnio rozumiem. Czemu intpower rozkłada na części z wykładnikiem parzystym? I czemu x^{10 = x}2 * x^{8 a nie np: x}2 * x^{2 * x}2 * x^{2 * x}2?

15 w kodzie binarnym 1111
10 w kodzie binarnym 1010
sprawdzasz parzystość, dzielisz przez 2

Dlaczego jest n/=2?

Dano: 15 nieparzysta 1
15/2 = 7 nieparzysta 1
 7/2 = 3 nieparzysta 1
 3/2 = 1 nieparzysta 1
 1/2 = 0
kod binarny czytany od tyłu 1111

Dano: 10    parzysta 0
10/2 = 5 nieparzysta 1
 5/2 = 2    parzysta 0
 3/2 = 1 nieparzysta 1
 1/2 = 0
kod binarny czytany od tyłu 1010