22 listopada 2011

Ulamki egipskie

Ułamki egipskie to nazwa sum dodatnich ułamków właściwych zwykłych z 1 w licznikach. Żadna inna wartość niż 1 w liczniku się nie pojawia.
Przejście na ułamki egipskie należy do trudnych zagadnień. Algorytm zachłanny zawsze działa, lecz mianowniki uzyskiwane pod koniec przekształceń są ogromne. Są dwa kryteria doboru optymalnych sum:
- jak najmniej składowych;
- suma mianowników jest najmniejsza.
Kryteria te czasem wykluczają się nawzajem. Istnieje ułamek egipski będący sumą 3 ułamków zwykłych, ale suma mianowników jest najmniejsza dla sumy 4 ułamków zwykłych.

Zwłaszcza ułamki egipskie powstałe z ułamka zwykłego postaci (2^n-1)/2^m wymagają ostrożnego podejścia. Np. 15/32 = 1/3 + 1/8 + 1/96 oraz 15/32 = 1/4 + 1/8 + 1/16 + 1/32.
Pierwsza postać ma długość (liczność składników sumy) 3, druga 4. Suma mianowników w pierwszym przykładzie to 107, w drugim 60.

Do rozkładu należy ewolucyjnie zaprząc 3 algorytmy: próba rozkładu lub rozszerzenie przez liczbę dopasowaną do dzielników mianownika, oraz algorytm zachłanny wyłączający największy ułamek postaci 1/n mieszczący się w rozkładanym. Po każdym wyłączeniu składnika należy sprawdzić wyniki tych trzech algorytmów i wybrać najlepszy.
Dla ułamków mających dzielniki najczęściej dobry jest rozkład. Jeżeli wielokrotność licznika nieco przekracza dzielnik mianownika, rozszerzanie jest bardzo opłacalne. Gdy mianownik jest liczbą pierwszą, algorytm zachłanny bywa najlepszy.

Wśród nierozwiązanych problemów jest hipoteza Erdosa: każdy ułamek 4/n można przekształcić na ułamek egipski długości 3.
Dowód według mnie można sprowadzić do rozszerzenia takiego, by rozszerzyć ułamek i skrócić przez dzielnik powstałego mianownika. Odpowiednie rozszerzenie zawsze istnieje dla liczb mniejszych od pierwotnego mianownika. Jest ich nawet więcej niż trzeba.

Wysuwam hipotezę: długość ułamka egipskiego otrzymanego z a/n nie przekracza 1+lg_2(a).
Dla 3/n nie można zmniejszyć, zatem przy 4 nie obejmuje hipotezy Erdosa. Niemniej graniczne szacowanie jest rzadko spełniane, trzeba specjalnie dobierać mianowniki, jako np. n=a*b+1.

07 listopada 2011

cechy podzielnosci przez 7, 17

Wśród wielu znanych cech podzielności przez 7 podanych przez M. Szurka w Opowieściach matematycznych nie ma jednej, bardzo prostej. Jest ona podobna do cechy I, lecz działa nieco inaczej.

Cecha I polegała na odcięciu dwu ostatnich cyfr liczby, oraz dodanie do niej iloczynu 4 oraz odciętej liczby dwucyfrowej. Jeśli nowo otrzymana liczba jest podzielna przez 7, to początkowa także.

Ta cecha zaczyna się podobnie, odcinam dwie ostatnie cyfry, lecz liczbę dwucyfrową dodaję do podwojonej części.

Na przykładzie 138264, oryginalnie:
1382 + 4*64 = 1638
16 + 4*38 = 168
dokończenie 168 = 24*7.
Ten sam przykład, moją cechą podzielności
2*1382 + 64 = 2828
2*28 + 28 = 84 = 12*7

Cecha działa, ponieważ 7 dzieli 98, czyli 100-2. W każdym kroku zmniejszam o wielokrotność 98.

Bardzo podobnie zachowuje się 17, które dzieli 102.
Cecha podzielności przez 17 jest identyczna, z tą różnicą, że liczbę dwucyfrową odejmuje się zamiast dodawać.
Przykład dla tej samej wartości 138264 = 8133*17+3
2*1382 - 64 = 2700
2*27 - 0 = 54 = 3*17 + 3

18 października 2011

faktoryzacja

W kontakcie z wroclawskim portalem informatycznym uzyskalem informacje, jak liczy sie zlozonosc algorytmow rozkladajacych liczbe na czynniki pierwsze.
Liczy sie je wedlug licznosci bitow (znakow), za pomoca ktorych mozna te liczbe przedstawic.

Moje wczesniejsze wyniki dotyczace zmian systemow liczbowych pozwalaja latwo faktoryzowac liczby. Sprawdzam, czy liczba jest podzielna przez 2, 3. Konwertuje na system trojkowy a nastepnie zwiekszam podstawe systemu. Algorytm jest liniowy wzgledem dlugosci liczby, kwadratowy wzgledem przeksztalcen.
Najmniej znaczaca cyfra rowna 0 wskazuje dzielnik. Kryterium stopu jest osiagniecie pierwiastka z liczby, co rozpoznaje po krotnosci 'cyfr'. Liczba 'dwucyfrowa' bez dzielnikow uzyskana w tym algorytmie jest pierwsza.

Oznacza to, ze dysponuje liniowym algorytmem faktoryzacji liczb!

16 września 2011

Obsługa klas

Jak zostało wspomniane w poprzednim poście, istnieje schemat, by nie mówić 'szablon' klas.

Do jego obsługi potrzebna jest specjalizowana klasa, cos w rodzaju rozdzielnika. Ale przyglądając sie wprawce - generowaniu mudowego miasta, zauważyłem potrzebę jeszcze kilku zaprzyjaźnionych funkcji.
Są to funkcje: 'dołączania argumentu', wywoływania, korekty i naprawy.
Tak. Argumenty Obiektów sa Obiektami przekazywanymi w inny sposob. Daje się je na listę, a następnie 'wywołuje' Obiekt. Kiedy dany Obiekt zna i akceptuje argument, wywoływana jest 'standardowa', napisana funkcjonalnie (jak ktoś chce, to nawet obiektowo) funkcja.
Każda operacja na Obiekcie może go modyfikować. Może zmieniać stan tego Obiektu, może wskazać, że jest niepotrzebny. Może wyzwolić kaskadę kolejnych zmian na Obiektach. Dlatego wartością funkcji powinien być integer, wartość boolowska ma za malo możliwości.
Wartością wyjścia jest liczba ujemna w przypadku krytycznego błędu. Błąd dotyczy jednak tylko danego Obiektu! Po jego naprawie można działać dalej.
Wartość 0 oznacza pomyślne zakończenie, wartości dodatnie oznaczają informacje o stanie Obiektu do systemu. Po przechwyceniu wartości, z Obiektem mozna zrobić to, co zaproponował swoją wartością, skasować, odłożyć do kolejki do ponownego wywołania.

W projektowaniu walczą ze sobą: kolejka na void* oraz klasa abstrakcyjna, będaca korzeniem wszystkich Obiektów. A na razie powinienem pamiętać o sprawdzaniu zwracanej wartości!

05 września 2011

Schemat klas

Wreszcie doszedlem do schematu fizycznego klasy. Wymagalo to wielu refaktoryzacji, ale jest.
Kazda klasa Obiekt ma nastepujace pola:

identyfikator (int)
wartosc (unsigned int)
znak (unsigned int)
korzen (void *)
data (void * [] ) czyli tablica Obiektow
create(wartosc, znak)
destroy()
show()
'obiekt'(int)

oraz skladowe prywatne, ktore sa bardzo uzaleznione od klasy.
Na razie pola te sa publiczne, do testow. W oryginale jednak wszystkie moga byc prywatne! I tak odwolania do tych wszystkich klas nie wystepuja bezposrednio, lecz za pomoca zaprzyjaznionej klasy, ktora je tworzy, kasuje i wywoluje. Zaden nieznany Obiekt nie przejdzie przez to sito, a jesli nawet, to bedzie on zignorowany lub skasowany.

Dodatkowo mam dolaczone bardzo mile wlasnosci: automatyczne sprytne wskazniki, funktory, oraz wlasna kontrole typow, gdyz Obiekty moga czasem zmieniac swoj typ w czasie dzialania.
Z minusow, trzeba uwazac na liczby calkowite ujemne - calkiem nowy typ.

13 czerwca 2011

Projektowanie ekstremalne

Opiszę ten sposób projektowania na przykładzie klonu Master of Orion.

Jest to projektowanie funkcyjne schodzące od najbardziej ogólnych obiektów do obiektów coraz głębiej położonych. Ten typ projektowania można określić grafem lasu, w którym korzenie to najbardziej ogólne klasy. Liście stanowią podstawowe wartości zmiennych obiektów.
Przykładowo, w pniu będą klasy Galaktyki i Rasy, zaś dalej następuje cały ciąg powiązanych ze sobą klas.
Galaktyka składa się z systemów gwiazdowych Star. Każda ma własną nazwę. Ze Star odchodzi krawędź na liść „Nazwa gwiazdy”.
Do każdego układu gwiezdnego można przypisać statek kosmiczny, potwora, traktując je przy inicjacji analogicznie jak kolejną planetę. Owszem, mają inne własności, lecz uaktywniają się one tylko na określone żądanie. To podejście narzuca ograniczenie na liczność statków wyprodukowaną przez Rasę, związaną z ich ekspansją, jak w Ascendancy.
No dobrze, ale ja nie chcę jednego statku na układ dla jednej Rasy! W takim przypadku klasę statków umieszczamy jako obiekt w klasie Rasa, wskazując tylko Planetę Układu, przy którym statek powstaje, aby z niej czerpać surowce. I mamy jednostki jak w Civilization.

To było przypisanie. Każdy obiekt może zawierać wiele obiektów różnych typów. Sam najczęściej zawiera się w innym. Przy projektowaniu zastanawiamy się, jakie zależności spełnia Obiekt, jak jest położony w strukturze. Po utworzeniu prototypu umieszczamy go we właściwej części drzewa. Na raz zajmujemy się dokładnie jednym obiektem.

Kiedy już wiemy, gdzie jest obiekt, co jest jego przodkami, zatrzymajmy się na chwilę, ignorując jego potomków, jego prawidłowe działanie. Sprawdzamy, czy takie rozmieszczenie nie psuje powstałej struktury. Najtrudniejsze jest zachowywanie widoczności z innymi gałęziami drzewa, aby obiekt widział inne istotne dla siebie obiekty, przekazywał im informacje. Dobrze, gdy mają wspólnego przodka. A kiedy nie mają, potrzebują wskaźnik na odpowiedni węzeł drzewa w swojej budowie.

Dopiero kiedy struktura jest zachowywana, można przystąpić do wprowadzania działań, co obiekt robi, jak to robi. Są to rzeczy, które klasycznie robi się na samym początku. Zaś przy kłopotach część pracy klasycznej idzie do kosza. Przy podejściu ekstremalnym wystarczy odszukać w kodzie właściwy fragment klas bazowych i podpiąć się. Wywołanie nastąpi przy działaniach na tamtych klasach, o ile wszystkie warunki inicjacyjne zostaną spełnione.

08 kwietnia 2011

zmiany systemów liczbowych

Zastanawiałem się nad zapisem liczby w różnych liczbowych systemach pozycyjnych.
Aktualnie jestem w stanie przejść prawie bez przeszkód pomiędzy dwoma systemami w ogólnej postaci:
a_n p^n + ...+ a_1p +a_0

Wykorzystuję schemat Hornera, zaczynając od cyfry najbardziej znaczącej.

W użyciu jest następujący algorytm rekurencyjny:
wyliczam różnicę między podstawami systemów r = p2-p1, może być liczbą  dodatnią lub ujemną
na wejściu jest liczba (a_n ... a_0), wynik jest w postaci (b_m ... b_0), wartości pośrednie c_i można zapisać w dowolnym systemie, są to liczby całkowite
d = n, b_n = a_n; b_{n+1} = 0;
w pętli d = d-1;
    (1)                c_i = b_{i} + r * b_{i+1}
Ten krok 'psuje' cyfry, tzn. na miejscu cyfr pojawiają się liczby całkowite. Potrzebna jest 'naprawa', czyli przeniesienie nadmiarów lub wzięcie pożyczek: wykonuje się to w pętli po j>d-1:
b_j = c_j modulo podstawa,
b_{j+1} = b_{j+1} + c_j/ podstawa

Przy dużych podstawach liczby sa krótkie, pętle składają się z kilku prostych sum lub różnic.
Można pomyśleć o rozkładach liczb w taki sposób. Przekształcenia dla małych przyrostów są niesamowicie szybkie, można sprowadzić do 3*r sumowań lub odejmowań.

Konkretny przykład:
213 w systemie ósemkowym przekształcimy na system dziewiątkowy. Różnica r = 8-9 = -1
Pobieramy najbardziej znaczącą cyfrę: 
2
Pobieramy kolejną cyfrę 1 oraz stosujemy przekształcenie (1) 
2  1
2  1+2*(-1)
2  -1
wartość wymaga naprawy przez pożyczkę podstawy 9+(-1), uzyskujemy
1  8
dołączymy kolejną cyfrę 3
1   8             3
1   8+1*(-1)  3+8*(-1)
1   7             -5
Potrzebna jest pożyczka 9+(-5). Aktualna postać liczby to
1  6  4
Zatem 213 w ósemkowym to 164 w dziewiątkowym.
Bez dzielenia, same dodawania i odejmowania. Wszystkie wartości pośrednie są mniejsze niż pierwiastek z liczby.

04 stycznia 2011

Zaćmienie Słońca 4.01.2011

Rano wchodzac do Centrum astronomowie urzadzili sobie sesje fotograficzna ze Slonkiem i Ksiezycem. podobno zakrycie doszlo do 80%. Sprawdzajac pogode nad Europa z sat24.com pojawily sie bardziej dynamiczne efekty zwiazane z tym zjawiskiem. Polska byla na jego poczatkowej krawedzi.
Na zdjeciach z satelitow widac polcien rzucany na Ziemie z bardzo specyficznym torem ruchu. Najpierw polcien rozszerzal sie wedrujac na NW!, po czym zaczyna podazac na E, w kierunku Moskwy. Wskazuje to sposob, jak zacmienia 'pojawiaja sie i znikaja'. Z zabkami.
Oczywiscie, najbardziej widowiskowy jest srodek. Ale tor zacmien nie jest 'czystym' pasem w jednym kierunku, jak to podaja niektore pogladowe rysunki.