Szybkie potęgowanie – sprawdzenie poprawności kodu

Napisałem program na szybkie potęgowanie iteracyjnie. Mógłby ktoś sprawdzić czy kod jest poprawny? Jak go poprawić, żeby liczył liczbę mnożeń?

#include<iostream>

using namespace std;

long long potegowanie(long long p, long long w) // p-podstawa, w-wykladnik
{
    long long x = 1;

    while(w>0)
    {
        if (w%2 == 1) 
            x *= p;

        p*= p;
        w/=2; 
    }
    return x;
}

int main()
{
    long long p;
    long long w;
    cin>>p>>w;

    cout<<potegowanie(p, w);

    return 0;
}

Ten kod sie rozni od tego z Wikipedii: https://en.m.wikipedia.org/wiki/Exponentiation_by_squaring. Mozesz Sam go sprawdzic.

np dla 2^4 powinno wyświetlać liczbę mnożeń: 2, a wyswietla 3. W czym tkwi problem?

#include<iostream>


using namespace std;

long long potegowanie(long long p, unsigned int w) // p-podstawa, w-wykladnik
{
    long long x = 1;
    int i=0;


    while(w>0)
    {

        if (w%2 == 1)
            x *= p;

        p*= p;

        w/=2; 
        i++;
    }
    cout<<"Liczba mnozen: "<<i<<endl;
    return x;


}

int main()
{

    long long p;
    unsigned int w;
    cin>>p>>w;

    cout<<potegowanie(p, w)<<endl;



    return 0;
}

Po każdym mnożeniu powinieneś zwiększyć licznik mnożeń:

#include<iostream>
 
using namespace std;
 
long long potegowanie(long long p, long long w)
{
    long long x = 1;
    int licznik_mnozen = 0;
 
    while(w > 0)
    {
        if (w%2 == 1) 
       {
            x *= p;
           licznik_mnozen++;
       }
 
        p *= p;
        licznik_mnozen++;
        w /= 2; 
    }
	
    return x;
}

2^4 daje 4 mnożenia
2^2 daje 3 mnożenia
2^16 daje 6 mnożeń,
raczej ten algorytm jest lepszy dla dużych wykładników.

Edit: cos dziwnie wychodzi?
Edit2: warunek wyjścia trochę skopany, mnożysz przez jedynkę w ostatniej iteracji, ale twój algorytm tak działa, że musisz mnożyć przez 1.

do testowania kodu użyć gtest i serii testowych(TEST_P o ile dobrze pamiętam);

Dla 2^16 nie powinno pokazywac 4 mnozenia?

W piątej iteracji w = 1, 1%2 = 1 więc if zadziała i masz jedno mnożenie (x *= p), p *= p też zadziała chociaż już nie ma żadnego znaczenia, więc do tych 4 musisz dodać 2.

http://www.algorytm.edu.pl/algorytmy-maturalne/potegowanie-szybkie.html

W tym przypadku jest napisane ze 2^10 daje liczbę mnozeń 4 a nie 6..

No skoro tak napisali...
Rozpisz sobie na kartce ten przypadek i porównaj wynik z wartościami oczekiwanymi.

Funkcja rekurencyjna daje o jedno mnożenie mniej.

A może mnożenie przez jeden już nie jest traktowane jako mnożenie? Fakt kompilatory potrafią coś tam optymalizować z drugiej strony jest to zmienna a nie stała wartość 1.