Super speed modulo - jak to działa?

Question

Witajcie, czy znalazłby się śmiałek, który zdołałby wypunktować mi jak ta funkcja działa, co w danych momentach/etapach się dzieje? Przyznam, że - przede wszystkim - jestem skonfundowany zapisem: i<<=1.

int super_speed_modulo(int a, int b)
{
    int result=1;
    long long int x=a%10;
    for(int i=1; i<=b; i<<=1)
    {
        x %= 10;
        if ((b&i) != 0) { result *= x; result %= 10; }
        x*=x;
    }
    return result;
}

 

Answer 1

 

Wytłumaczę tylko największe magie, bo z resztą chyba sobie poradzisz.

i<<=1;

Przesunięcie bitowe. Przesuwasz wszystkie bity w lewo o 1 pozycję. Gdybyś napisał "i>>n", to było by to przesunięcie w prawo o n bitów. "i<<=n" jest równoważne z operacją i = i * 2 ^ n, a "i>>=n" będzie oznaczało i = i / 2 ^ n. Tylko nie myśl, żeby to zawsze traktować, jako takie obliczenie, bo przede wszystkim trzeba pamiętać, że jest to przesunięcie np.

char i = 0b00110110;
i <<= 3;
cout<<i<<"\n"; \\0b10110000
i >>= 5;
cout<<i<<"\n";\\0b00000101

Bity, które się nie miszczą są obcinane.

 

if ((b&i) != 0) { result *= x; result %= 10; }

Magia jest tu głównie z operatorem "&". Jest to AND, ale bitowe, czyli bierze pod uwagę karzdy bit oddzielnie.

Przykład:

char a = 0b01010110;
char b = 0b10001011;
char c = a&b; \\c = 0b00000010

Zauważ, że 1 jest tylko tam, gdzie w obu liczbach było 1, co zatym idzie możesz mieć np. taki przypadek:

char a = 0b01010110;
char b = 0b10000001;
char c = a&b; \\c = 0b00000000

Zmienna c została wyzerowana mimo, że obie wartości były różne od 0, więc nie można tego utożsamiać z &&.

W parze z tym operatotem często spotyka się też "|". Jest to OR bitowe. Nożesz tego użyć np. do ustawienia flag, które mówią, czy coś jest czy czegoś niema. Ustawiasz bity operatorem "|", a sprawdzasz "&". Takie coś jest też czasem nazywane maskowaniem. Dużo tego można znaleźć w WinAPI. 

Comments

Będę musiał się chyba trochę douczyć, bo na razie, czytając ten post, robię tylko wielkie oczy ;D

Serdecznie dziękuję za pięknie zredagowaną odpowiedź :)

---

hit02, mogłeś uprzedzić że jesteś, to bym się nie męczył interpretacją. ;D Lecę spać. Dobrej nocy! :)

Answer 2

Jesteś pewien, że ten kod działa poprawnie? :)

Celem testu (C++, jeśli chcesz w czystym C, musisz zmienić operacje I/O) chciałem wydrukować sobie po kolei, co ta funkcja robi, ale najpierw sprawdziłem, czy podaje poprawne wyniki... Przetestuj.

#include <iostream>
using namespace std;

int super_speed_modulo(int a, int b)
{
    int result=1;
    long long int x=a%10;
    for(int i=1; i<=b; i<<=1)
    {
        x %= 10;
        if ((b&i) != 0) { result *= x; result %= 10; }
        x*=x;
    }
    return result;
}

int main()
{
    int a = 13, b = 2;
    cout<<a%b<<endl<<super_speed_modulo(a,b);
    return 0;
}

Chyba że ona nie służy jako operator modulo, a tylko ta nazwa jest taka myląca. ;D

Comments

Przepraszam, nie wytłumaczyłem oznaczeń zmiennych:

a - jest podstawą potęgi,

b - jest wykładnikiem, 

Funkcja wypisuje liczbę jedności wyniku takiego potęgowania, czyli modulo z 10.

Jest to jakoś sprytnie zrobione, że wykonana jest tam bardzo mała ilość mnożenia - w przeciwieństwie do normalnego potęgowania.

Funkcja ta jest mi potrzebna do tego zadania ze spoja: http://pl.spoj.com/problems/PA05_POT/.

Edit: 13 do 2 potęgi to 169, czyli modulo to 9. Pozdrawiam :)

---

Czekaj, bo chcę dobrze zrozumieć, a pora nie pomaga. ;P

Wynik działania funkcji to (a^b)%10?

---

Tak nawiasem, to zapis i <<= 1; oznacza przesunięcie bitowe i o 1 w lewo.

Co np. dla i = 3:

i = 3 = 0011

0011<<1 = 0110

Answer 3

Na SPOJ'a wystarczy taki kod - złożoność O(log b)

int power_modulo_fast(int a, int b, int m)
{
int i;
int result = 1;
long int x = a%m;
 
for (i=1; i<=b; i<<=1)
{
x %= m;
if ((b&i) != 0)
{
result *= x;
result %= m;
}
x *= x;
}
 
return result;
}

Ta funkcja pochodzi z algorytmu szybkiego potęgowania.

Comments

Taki sam kod znajduje się w pytaniu :)

---

Sorry nie zauważyłem. Wersja rekurencyjna jest za to łatwiejsza do oklepania (bez operacji bitowych).

---

Dziękuję za susgestię :)