Ridicare la putere în timp logaritmic

Apărut la 17 octombrie 2016 în C / C++   |   autor: Dan Pracsiu 2 comentarii

Doresc să pun în evidenţă o modalitate simplă de calcul a valorii expresiei xⁿ, unde x este un număr real, iar n este număr natural. O primă variantă, cea care se învaţă odată cu instrucţiunile repetitive, este bazată pe relaţia:

xⁿ = x * x * ... * x, adică înmulţire repetată de n ori a lui x

Funcţia care realizează acest lucru este:

  double Putere(double x, int n)
  {
  double p = x ;
  for (int i = 1 ; i < n ; i++)
  p *= x ;
  return p ;
  }

Există însă o soluţie mai rapidă, bazată pe relaţiile următoare:

• dacă n este impar, atunci xⁿ = x^n-1 * x
• dacă n este par, atunci xⁿ = x^n/2 * x^n/2

În acest fel, numărul total de operaţii de înmulţire va scădea semnificativ. De exemplu pentru calculul lui x¹³ se vor efectua numai 5 înmulţiri, iar x¹⁰⁰ doar 8 înmulţiri. Funcţia este următoarea:

double PutereLogaritmic(double x, int n)
{
	double p = 1 ;
	while (n > 0)
	{
		if (n & 1) // n este impar
		{
			p *= x;
			n-- ;
		}
		x = x * x ;
		n >>= 1 ; // sau n = n / 2
	}
	return p ;
}

Număr de accesări: 26043

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică

• 

  Borcani Robert 17-7-2014 13:21:59

  Buna!
  
  Va multumesc foarte mult pentru aceasta explicatie pentru ca aveam mare nevoie de ea intr-o problema si aici a fost singurul loc unde am inteles cum functioneaza ridicarea la putere in timp logaritmic.

• 

  Spataru Marc 21-2-2015 19:34:11

  Multumesc foarte mult pentru algoritmul acesta!
  Initial nu am inteles cel cu operatii pe biti... Acesta m-a scos din ceata.