Przeszukując źródła nie zauważyłem, by gdziekolwiek były podane operatory arytmetyczne za pomocą operatorów logicznych. Zauważyłem tylko, np. w Kalejdoskopie Techniki 7/1978, że w układach cyfrowych odejmowanie, mnożenie i dzielenie są funkcjami dodawania. Zaś wykłady z elektroniki obejmowały konstrukcje sumatorów oraz komparatorów, cyfra po cyfrze.
O ile komparator musi działać liniowo, o tyle dodawanie można zapisać funkcjami logicznymi AND &, OR |, NOT ~. Wymagana jest tylko rekursja oraz operatory przesunięcia SAL (w lewo, czyli mnożenie przez 2) oraz SAR (w prawo, czyli dzielenie przez 2).
Prawdę mówiąc, nie potrafię zapamiętać, który z SAL, SAR to mnożenie, a który dzielenie. Przed każdym użyciem muszę to sprawdzać.
Algorytmy są rekursywne, w najgorszym przypadku przewijają cały obrabiany bajt. Przy przesuwaniu wstawiane są zera.
I tak inkrementacja INC A wyraża się za pomocą ( ? : ) z C następująco:
INC A = ( A&1 ? SAL INC SAR A : A|1 );
Funkcja dekrementacji DEC A stosując maskę -2 = 0xF...FE
DEC A = ( A&1 ? A&(-2) : 1|(SAL DEC SAR A) );
Funkcja porównania = zwraca A (równe) albo 0 (różne)
(A=B) = ( (A|B)&~(A&B) ? 0 : A ) = ( A XOR B ? 0 : A);
Funkcja porównania mniejszości < jest bardziej skomplikowana. Najpierw usuwamy pola z jednocześnie ustawionymi bitami argumentów
C = A&~(A&B); D = B&~(A&B);
Teraz w pętli zmniejszamy, dopóki jedno z nich się nie wyzeruje
while (C&D) { SAR C; SAR D; }
Po tych zabiegach można zwrócić wartość porównania: większe B lub zero
(A < B) = ( C ? 0 : B);
Wreszcie funkcja dodawania, która się zakończy zanim rekursja przejdzie cały bajt:
0+B = B;
(A+B) = (SAL A&B) + ((A|B)&~(A&B)) = (SAL A&B) + (A XOR B);
najgorszym przypadkiem jest (-1)+1, kiedy rekursja przechodzi kolejno po każdym bicie.
Algorytmy te nie mają praktycznego znaczenia, gdyż jednostka arytmetyczno-logiczna procesorów jest dedykowana także do obliczeń arytmetycznych. Wykonuje je równie szybko i sprawnie jak logiczne.
Teoretycznie moduł arytmetyczny procesora nie jest potrzebny. Wystarczy logiczny.
16 czerwca 2014
Schemat mnożenia, czyli funkcja jednoargumentowa iloczynu
Przy pisemnym mnożeniu binarnym mamy ciągłe inną dodawanie liczby i jej przesuwanie. Jeżeli mnożymy binarnie przez jeden, tworzy się pewien schemat. Zapamiętany schemat można odtworzyć biorąc jako argument dowolną wartość. Uzyskamy w ten sposób iloczyn argumentu oraz liczby danej schematem.
Kiedy występuje kilka jedynek pod rząd, np. '0111', zamiast trzech dodawań wygodniej jest dodać liczbę na pozycji poprzedzajacej jedynkę, oraz odjąć na pozycji ostatniej jedynki.
Opracowuje sposób uzyskania schematu. Zliczam długość binarnych ciągów zer i jedynek, oraz wprowadzam dodatkowe elementy + oraz - oznaczające dodanie, odjęcie argumentu.
Algorytm jest następujacy: dany jest ciąg symboli 0,1, poprzedzony zerami. Domyślnie jest to zapis binarny liczby od cyfr najmniej znaczących.
Mam flagę F, początkowo wyzerowaną oraz licznik C
1) powtarzam 2)- 4), dopóki liczba dodatnia i flaga wyzerowana
2) jeśli ostatni bit jest wyzerowany i flaga ustawiona zapamiętuję '+'C, zeruję C i kasuję flagę;
3) jeśli ostatnie dwa bity to '11' oraz flaga wyzerowana, zapamiętuję wartość licznika '-'C, zeruję licznik i ustawiam flagę; jeśli flaga była już ustawiona zwiększam tylko licznik
4) jeśli ostatnie dwa bity to '01' oraz flaga wyzerowana, zapisuję licznik '+'C, zeruję licznik; Gdy flaga jest ustawiona, zwiększam tylko licznik
Zapamiętany zostaje ciąg, np. dla liczby binarnej 100111101 jest nim +1+3-1+0. Zer nie musimy zapisywać, lecz należy je uwzględniać.
Sposób użycia schematu.
Startujemy od liczby lub +. W obu przypadkach jest to wartość argumentu. Napotykając +, mnożymy przesuwaniem liczbę o 2 i dodajemy argument. Kiedy napotykamy -, mnożymy przez 2 przesuwaniem i odejmujemy argument. Kiedy występuje liczba, przesuwamy mnożąc wartość przez 2 do potęgi tej liczby.
Schemat sprawdzamy, wstawiając za argument 1. Kiedy uzyskamy wartość liczby, schemat jest prawidłowy.
Sprawdźmy zatem schemat +1+3-1+:
+1, 1 mnożymy przez 2^1 uzyskując 2;
+3, przesunięcie i dodanie 1 da 2*2+1 = 5, przesunięcie 3 powoduje pomnożenie przez 8 do 40;
-1, przesunięcie i odjęcie 1 powoduje uzyskanie 79, które mnożymy jeszcze raz przez 2 do 158
+[0], przesunięcie i dodanie 1 powoduje uzyskanie 317, ponieważ ostatnie przesunięcie jest zerowe, mamy wartość ostateczną 317 rowną binarnie liczbie 1 0011 1101.
Wartości liczbowe są zmniejszonymi o 1 krotnościami kolejnych zer, jedynek. Każdy zapis '+/- a' odpowiada następujacej instrukcji niskiego poziomu dla argumentu Y oraz wartości X: (X<<1 +/- Y)<<a .
Uzyskane liczby zawsze są dodatnie.
Kiedy występuje kilka jedynek pod rząd, np. '0111', zamiast trzech dodawań wygodniej jest dodać liczbę na pozycji poprzedzajacej jedynkę, oraz odjąć na pozycji ostatniej jedynki.
Opracowuje sposób uzyskania schematu. Zliczam długość binarnych ciągów zer i jedynek, oraz wprowadzam dodatkowe elementy + oraz - oznaczające dodanie, odjęcie argumentu.
Algorytm jest następujacy: dany jest ciąg symboli 0,1, poprzedzony zerami. Domyślnie jest to zapis binarny liczby od cyfr najmniej znaczących.
Mam flagę F, początkowo wyzerowaną oraz licznik C
1) powtarzam 2)- 4), dopóki liczba dodatnia i flaga wyzerowana
2) jeśli ostatni bit jest wyzerowany i flaga ustawiona zapamiętuję '+'C, zeruję C i kasuję flagę;
3) jeśli ostatnie dwa bity to '11' oraz flaga wyzerowana, zapamiętuję wartość licznika '-'C, zeruję licznik i ustawiam flagę; jeśli flaga była już ustawiona zwiększam tylko licznik
4) jeśli ostatnie dwa bity to '01' oraz flaga wyzerowana, zapisuję licznik '+'C, zeruję licznik; Gdy flaga jest ustawiona, zwiększam tylko licznik
Zapamiętany zostaje ciąg, np. dla liczby binarnej 100111101 jest nim +1+3-1+0. Zer nie musimy zapisywać, lecz należy je uwzględniać.
Sposób użycia schematu.
Startujemy od liczby lub +. W obu przypadkach jest to wartość argumentu. Napotykając +, mnożymy przesuwaniem liczbę o 2 i dodajemy argument. Kiedy napotykamy -, mnożymy przez 2 przesuwaniem i odejmujemy argument. Kiedy występuje liczba, przesuwamy mnożąc wartość przez 2 do potęgi tej liczby.
Schemat sprawdzamy, wstawiając za argument 1. Kiedy uzyskamy wartość liczby, schemat jest prawidłowy.
Sprawdźmy zatem schemat +1+3-1+:
+1, 1 mnożymy przez 2^1 uzyskując 2;
+3, przesunięcie i dodanie 1 da 2*2+1 = 5, przesunięcie 3 powoduje pomnożenie przez 8 do 40;
-1, przesunięcie i odjęcie 1 powoduje uzyskanie 79, które mnożymy jeszcze raz przez 2 do 158
+[0], przesunięcie i dodanie 1 powoduje uzyskanie 317, ponieważ ostatnie przesunięcie jest zerowe, mamy wartość ostateczną 317 rowną binarnie liczbie 1 0011 1101.
Wartości liczbowe są zmniejszonymi o 1 krotnościami kolejnych zer, jedynek. Każdy zapis '+/- a' odpowiada następujacej instrukcji niskiego poziomu dla argumentu Y oraz wartości X: (X<<1 +/- Y)<<a .
Uzyskane liczby zawsze są dodatnie.
02 czerwca 2014
Największy wspólny dzielnik podejściem wielowartościowym
W poprzednim poście podałem, że dla nieparzystej wartości a największy wspólny dzielnik nwd (ang. greatest common divisor GCD) spełnia warunek:
nwd(a,b) = nwd(a,2b).
Pozwala to dodać kilka dodatkowych warunków, by szybko liczyć nwd metodami wielowartościowymi.
Załóżmy roboczo, że a<b.
Metody do liczenia nwd są następujące: różnica b-a, reszta z dzielenia b/a, dopasowanie potęgi 2 tak, by
2^i*a <= b < 2^(i+1)*a
oraz całkowite
2^(j-1)*b <= a < 2^j*b .
Warunek całkowitości nie jest spełniony dla b nieparzystych, wtedy ten warunek sprowadza się do a<b.
Obliczamy moduł różnic uzyskanych wartości oraz odpowiedniej a, b oraz dokładamy dodatnią resztę z dzielenia. Uzyskamy wartość dodatnią c jako minimum uzyskanych wartości. Powtarzamy dla pary a, c.
Wartości zmniejszają się w kierunku wartości największego wspólnego dzielnika. Reszta z dzielenia może spaść do 0, wtedy zostaje zignorowana.
Złożoność postępowania jest złożonością najgorszej operacji: tu reszty z dzielenia. Dopasowanie potęg polega na porównaniu, przesuwaniu binarnym i odejmowaniu. Sprawdzana jest też parzystość, np. instrukcją 'b&1'.Wartości maleją szybciej niż logarytmicznie.
Przykład liczbowy, jak u Knutha Sztuka Programowania 4.5.2:
nwd( 20451, 6035 )
przesuwania: 2*6035 = 12070 < 20451 < 2^2*6035 = 24140;
20451/2 blokowany ułamek, pozostaje 6035 < 20451;
reszta z dzielenia: (2*(10000-6035)+451)%6035 = 2346;
lista: [8381, 3689, 14416, 2346]
Do dalszej iteracji przechodzi para ( 6035, 2346 ).
przesuwania: 2*2346 = 4692 < 6035 < 2^2*2346 = 9384;
6035/2 blokada, degeneracja do 2346 < 6035;
reszta z dzielenia: (6035 - 2*2346) = 1343;
lista: [1343, 3349, 3689, 1343]
Do dalszej iteracji rzechodzi para ( 2346, 1343 ).
przesuwania: 1343 < 2346 < 2*1343 = 2686;
2346/2 = 1173 < 1343 < 2346;
reszta z dzielenia: (2346-1343) = 1003;
lista: [1003, 340, 170, 1003, 1003]
Do dalszej iteracji przechodzi para ( 1343, 170 ).
przesuwania: 2^2*170 = 680 < 1343 < 2^3*170 = 1360;
1343/2 blokada, degeneracja do 170 < 1343;
reszta z dzielenia: 153;
lista: [663, 17, 1173, 153]
Do dalszej iteracji przechodzi para ( 170, 17 ).
przesuwania: 2^3*17 = 136 < 170 < 2^4*17 = 272;
170/2 = 85 >17 blokada na 17 < 85;
reszta z dzielenia: 0 blokada;
lista: [34, 102, 68]
Do ostatniej iteracji przechodzi para ( 34, 17 ).
Teraz obliczenia blokują się bardzo często zerem, zostawiając [17, 51] jako wartości listy. Po wymianie mamy parę (17, 17).
Zatem 17 = nwd(20451, 6035).
U Knutha było koło 8 iteracji, tutaj 6.
nwd(a,b) = nwd(a,2b).
Pozwala to dodać kilka dodatkowych warunków, by szybko liczyć nwd metodami wielowartościowymi.
Załóżmy roboczo, że a<b.
Metody do liczenia nwd są następujące: różnica b-a, reszta z dzielenia b/a, dopasowanie potęgi 2 tak, by
2^i*a <= b < 2^(i+1)*a
oraz całkowite
2^(j-1)*b <= a < 2^j*b .
Warunek całkowitości nie jest spełniony dla b nieparzystych, wtedy ten warunek sprowadza się do a<b.
Obliczamy moduł różnic uzyskanych wartości oraz odpowiedniej a, b oraz dokładamy dodatnią resztę z dzielenia. Uzyskamy wartość dodatnią c jako minimum uzyskanych wartości. Powtarzamy dla pary a, c.
Wartości zmniejszają się w kierunku wartości największego wspólnego dzielnika. Reszta z dzielenia może spaść do 0, wtedy zostaje zignorowana.
Złożoność postępowania jest złożonością najgorszej operacji: tu reszty z dzielenia. Dopasowanie potęg polega na porównaniu, przesuwaniu binarnym i odejmowaniu. Sprawdzana jest też parzystość, np. instrukcją 'b&1'.Wartości maleją szybciej niż logarytmicznie.
Przykład liczbowy, jak u Knutha Sztuka Programowania 4.5.2:
nwd( 20451, 6035 )
przesuwania: 2*6035 = 12070 < 20451 < 2^2*6035 = 24140;
20451/2 blokowany ułamek, pozostaje 6035 < 20451;
reszta z dzielenia: (2*(10000-6035)+451)%6035 = 2346;
lista: [8381, 3689, 14416, 2346]
Do dalszej iteracji przechodzi para ( 6035, 2346 ).
przesuwania: 2*2346 = 4692 < 6035 < 2^2*2346 = 9384;
6035/2 blokada, degeneracja do 2346 < 6035;
reszta z dzielenia: (6035 - 2*2346) = 1343;
lista: [1343, 3349, 3689, 1343]
Do dalszej iteracji rzechodzi para ( 2346, 1343 ).
przesuwania: 1343 < 2346 < 2*1343 = 2686;
2346/2 = 1173 < 1343 < 2346;
reszta z dzielenia: (2346-1343) = 1003;
lista: [1003, 340, 170, 1003, 1003]
Do dalszej iteracji przechodzi para ( 1343, 170 ).
przesuwania: 2^2*170 = 680 < 1343 < 2^3*170 = 1360;
1343/2 blokada, degeneracja do 170 < 1343;
reszta z dzielenia: 153;
lista: [663, 17, 1173, 153]
Do dalszej iteracji przechodzi para ( 170, 17 ).
przesuwania: 2^3*17 = 136 < 170 < 2^4*17 = 272;
170/2 = 85 >17 blokada na 17 < 85;
reszta z dzielenia: 0 blokada;
lista: [34, 102, 68]
Do ostatniej iteracji przechodzi para ( 34, 17 ).
Teraz obliczenia blokują się bardzo często zerem, zostawiając [17, 51] jako wartości listy. Po wymianie mamy parę (17, 17).
Zatem 17 = nwd(20451, 6035).
U Knutha było koło 8 iteracji, tutaj 6.
Subskrybuj:
Posty (Atom)