fbpx

Ridicarea la putere in timp logaritmic in C++ (Problema lgput – infoarena.ro)

0

Ridicarea la putere in C++

Cum am calcula in mod normal NP ? Cea mai usoara metoda este sa facem:

Sau folosind libraria #include <math>:

Insa aceste metode sunt foarte ineficiente. Deoarece daca N si P sunt numere naturale, putem aplica un algoritm mai inteligent si reducem complexitatea in timp de la O(P) (unde P este exponentul) la O(log2(P)). Diferenta intre aceste doua complexitati poate fi vazuta in graficul de mai jos:

Graficul complexitatii in timp
Graficul complexitatii in timp

Ridicarea la putere in timp logaritmic

Tot algoritmul se bazeaza pe urmatoarea observatie:

Observatie ridicarea la putere in timp logaritmic
Observatie ridicarea la putere in timp logaritmic

Aceasta metoda foloseste reprezentarea pe biti a numerelor pentru a determina ce calcule trebuie efectuate.

In urmatorul exemplu o sa va  aratam cum putem calcula x13 folosind aceasta metoda. Exponentul, 13, este scris sub forma 1 1 0 1 in codul binar. De asemenea, inca un aspect important este faptul ca bitii sunt folositi de la stanga la dreapta. De asemenea, 13 folosind doar 4 biti in reprezentarea lui, se vor efectua doar 4 iteratii.

De asemenea 13 poate fi scris sub forma 13 = 23 + 22 + o + 20.

In primul rand ne luam o variabila „rezultat” pe care o vom initializa r= 1 (1 = x0).

Calculam:

  • r = r * r . Deoarece primul bit este 1 (impar), mai adaugam un „x” la rezultat. Si avem r =  r * x. Deci avem r = 1 * x, adica x1
  • r = r * r. Inlocuind, x1 * x1 = x2 Deci r= x2. Deoarece al doilea bit este 1 (impar), mai adaugam un „x” la rezultat si avem. r = x2 * x, adica x3
  • r = r * r. Inlocuind, x3 * x3 = x6. Deci r = x6. Deorece al treilea bit este o, nu mai adaugam nimic.
  • r = r * r. Inlocuind, x6 * x6 = x12. Deci r = x12. Deoarece al patrulea bit este 1 (impar), mai adaugam un „x” la rezultat si obtinem r = x12 * x, adica x13.

De unde rezulta complexitatea in timp log2(P)?

In mod normal pentru a calcula NP am calcula N = N * P de P ori. Ceea ce ar rezulta intr-o complexitate O(P).

Dar daca folosim metoda descrisa mai sus o sa utilizam log2(P) operatii. Mai pe scurt numarul de pasi depinde de numarul de biti ce il ocupa P in memorie.
Am vazut mai sus ca pentru 13 am folosit log2(13) = 4 operatii.

Problema lgput – infoarena.ro

In continuare, pentru implementarea algoritmului vom rezolva problema lgput de pe infoarena.ro.

Cerinta:

Dandu-se doua numere naturale N si P, se cere sa se calculeze restul impartirii lui NP la 1999999973.

De ce trebuie sa calculam impreuna cu restul impartirii la 1999999973? Deoarece daca am calcula in mod normal 232 ridicat la puterea 232 ar trebuii sa modificam putin mai mult algoritmul datorita afisarii. Si nu acesta este scopul problemei.

Varianta nerecursiva:

Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More