W poprzednim poście z pierwszego października opisana została konstrukcja grafu, z której można odczytywać wartosci logarytmów dyskretnych. Czas na ćwiczenia praktyczne.
Porachujemy kilka logarytmów dyskretnych dla systemu Z_{17}. Został wybrany, gdyż dla tej liczby pierwszej pojawia się niejednoznaczność znajdowanych rozwiązań.
Dla przypomnienia podaję graf, którego lista jest wypisywana pionowo za numerem kolejnym wierzchołka. Wierzchołki listy są drzewami wysokości 1 o dwu liściach rozdzielonych '|'.
lista trywialna
0
lista długości 8:
1. 2 - 6 | 11
2. 4
3. 8 - 5 | 12
4. 16
5. 15 - 7 | 10
6. 13
7. 9 - 3 | 14
8. 1
Numer jest potrzebny, gdyż odczyt jest podobny jak w metodzie zliczania indeksów.
Rozwiązując równanie x^k = a (17) wyszukujemy pozycję a w grafie, tę pozycję listy dzielimy przez k. Jeśli nie jest to liczba całkowita dodajemy odpowiednią wielokrotność długości listy. Jeśli nie znajdujemy rozwiązania całkowitego, równanie nie ma rozwiązań. Wartość logarytmu odczytujemy z tego samego poziomu, co a.
Policzymy dla próby x^3 = 16 (17)
Szukamy 16 na listach. Znajdujemy na pozycji czwartej listy. Teraz znajdujemy położenie rozwiązania jako iloraz 4/3. Jest to liczba niewymierna, dodajemy długość listy (4+8)/3 = 12/3 = 4. Odczytujemy wartość: 16, oraz 16^3 = 16 (17).
Jest to proste, gdyż 16 = -1 (17) oraz (-1)^3 = (-1) = 16 (17).
Teraz coś trudniejszego, też z listy głównej:
x^5 = 9 (17)
Wartość 9 stoi na pozycji siódmej, zatem obliczamy pozycję wyniku (7+8)/5 = 3. Znajdujemy wartość 8, którą sprawdzamy: 8^5 = 9 (17). Zgadza się.
Kiedy wartość jest znaleziona w liściu, rozwiązanie też znajduje się na tym poziomie:
x^3 = 6 (17)
Wartość 6 jest na pozycji pierwszej listy, następuje tymczasowe 'podniesienie' do 2. Obliczamy pozycję wyniku (1+8)/3 = 3. Teraz 'schodzimy' poziom niżej znajdując dwie kandydatki: 5 oraz 12. Sprawdzamy je:
5^3 = 6 (17) oraz 12^3 = 11 (17).
Znaleźliśmy rozwiązanie 5, mając do sprawdzenia wybór jednej z dwu wartości.
Zwróćmy uwagę, że rachowane były wyższe potęgi niż druga. Dla tego sposobu wartość potęgi nie jest przeszkodą. W wikipedii większośc przykładów ograniczała się do potęgi drugiej, która przy tym podejściu jest często znajdowana 'z marszu'.
17 jest liczbą pierwszą. Sposób ten działa także dla liczb złożonych, lecz graf może być znacznie bardziej skomplikowany.
Przykładowo dla liczby 493 niektóre wartości mają do 8 pierwiastków, które trudno uporządkować liniowo. Dołączane do listy o długości 112 łańcuchy miały wysokość 1 lub 3. Dla 28 wartości przyłaczane łańcuchy długości 4 miały wspólny środkowy wierzchołek oraz maksimum lokowane na liście.
Wybieramy wtedy za jedną z list dowolny ze znalezionych łańcuchów długości 112, łańcuchy fragmentami są rozdzielne, lecz łączą się przy wartościach mających większą krotność pierwiastków. Przypomina mi to nieco budowę białek, kiedy poskręcane włókna wzajemnie się przeplatają. Pozostałe łańcuchy miały długości o 1 mniejsze niż dzielniki 493.
W przypadku doczepiania łańcuchów niektóre wartości musiały pojawiać się dwukrotnie, gdyż były sześcianami innych wartości, których łańcuchy nie obejmowały. Wartości te raz rozpoczynały łańcuch, za drugim razem sąsiadowały z korzeniem.
Brak komentarzy:
Prześlij komentarz