Bardzo miły sposób mnożenia, dzielenia występuje wtedy, kiedy oba wyrażenia zapiszemy przy podstawie mniejszego z nich. Jest to wtedy odpowiednik mnożenia przez '10'.
Kłopotliwy jest powrót do systemu początkowego. Ale wykorzystując równe liczby zapisane inaczej:
a_n p^n + ... + a_1 p + a_0 przy podstawie 2n
2^n a_n p^n + ... + 2 a_1 p + a_0 przy podstawie n
uzyskujemy kolejną, stosunkowo szybką metodę konwersji.
Przykładowo, liczba trójcyfrowa w systemie o podstawie 288 mająca następującą postać:
1.54.53
po konwersji do systemu o podstawie połowę mniejszej, 144 przyjmuje postać:
4.108.53
Przekształcenia: [1*4, 54*2(<144), 53] = [4, 108, 53]. Nie trzeba używać przeniesień, które występują, gdy iloczyn na miejscu cyfry będzie większy niż podstawa systemu.
Podobnie przy zwiększaniu podstawy systemu należy dzielić przez potęgi 2 w takiej potędze, jak daleko są one od cyfry najmniej znaczącej. Oczywiście cyfry po każdej zmianie systemu warto naprawiać.
Sposób ten oraz konwersje na sąsiedni system pozycyjny p -> p+1 opisane kilka postów wcześniej pozwalają błyskawicznie pomnożyć, i wrócić do systemu początkowego. Może to być wygodniejsze niż mnożenie pisemne.
Do pełnej implementacji pozostaje jeszcze sprowadzenie liczby do systemu, w którym będziemy mnożyć, dzielić. Możemy to zrobić w czasie O( log^2 ).
Jeśli chcemy zapisać liczbę a w systemie o podstawie b, najpierw wpuszczamy a między dwie sąsiednie potęgi
b^n < a < b^(n+1).
Następnie połowimy b zacieśniając przedział występowania b jak w wyszukiwaniu binarnym. Kiedy z b dojdziemy do 0, znajdziemy najbardziej znaczącą cyfrę a w systemie o podstawie b.
Zagęszczeń danej cyfry mamy tyle, jak długa jest liczba b. Powtarza się tyle razy, ile cyfr ma docelowa postać liczby a.
30 marca 2012
18 lutego 2012
mnożenie wysokiej precyzji
Mam porównać swój algorytm faktoryzacji liczb ze standardowym. Liczby, które zadaję są za małe.
Zatem należy poznać bibliotekę rachunków na dużych liczbach - gmp.
Nie byłbym sobą, gdybym wpierw nie przejrzał dokumentacji i zastanowił się nad algorytmami.
Oczywiście dla dodawania i odejmowania algorytmy nie są wspomniane. Są liniowe, jak to opisuje Knuth w Sztuce programowania rozdział 4.3.1.
Większość algorytmów używanych przez gmp jest też podana przez Knutha. Najprostszy ma złożoność O(NM), gdzie N i M są licznościami cyfr czynników. Lepsze mają złożoność związaną z licznością cyfr N wzorem O(N 2^(sqrt(2 lg N)) log N) .
Lecz Knuth nie zauważył jeszcze jednego podejścia, związanego z podawaną wielokrotnie przez niego równoważną postacią liczby.
Liczba binarna a_n a_{n-1}... a_0 może być przedstawiona następująco:
A = (...(a_n*2+a_{n-1})*2+...)*2 + a_0
Oznaczmy A_i nawias zawierający jako najmniej znaczącą cyfrę a_i.
Obliczając dwie takie liczby A oraz B uzyskujemy iloczyn
A*B = (A_1*2 + a_0) * (B_1*2 + b_0 ) = ((A_1*B_1)*2 + A_1*b_0 + a_0*B_1)*2 + a_0*b_0
Ponieważ mnożenie przez 2 jest równoważne przesunięciu, mamy 3 mnożenia przez cyfry 0, 1; do wyniku dodajemy 3 sumy cząstkowe oraz mamy wywołanie rekurencyjne dla liczb mających mniej cyfr.
Złożoność tego algorytmu to 3 mnożenia, 3 dodawania oraz 3 przesunięcia na każdą iterację, za każdym razem wyznaczamy 2 cyfry. Do wyznaczonych cyfr najmniej znaczących już nie musimy wracać. Iteracji jest tyle, by któraś z liczb A_i, B_i stała się jednocyfrowa.
Ponieważ w przypadku binarnym mnożenia mozemy zastąpić dodawaniami liczb o długości co najwyżej max(N,M), cała złożoność nie przekracza złożoności sum coraz krótszych liczb. Jest zatem co najwyzej kwadratowa dla wiekszej z nich. Dokladniej porownujac, uzyskuje zlozonosc taka sama jak u Knutha O(NM), lecz na coraz mniejszych cyfrach.
Zatem należy poznać bibliotekę rachunków na dużych liczbach - gmp.
Nie byłbym sobą, gdybym wpierw nie przejrzał dokumentacji i zastanowił się nad algorytmami.
Oczywiście dla dodawania i odejmowania algorytmy nie są wspomniane. Są liniowe, jak to opisuje Knuth w Sztuce programowania rozdział 4.3.1.
Większość algorytmów używanych przez gmp jest też podana przez Knutha. Najprostszy ma złożoność O(NM), gdzie N i M są licznościami cyfr czynników. Lepsze mają złożoność związaną z licznością cyfr N wzorem O(N 2^(sqrt(2 lg N)) log N) .
Lecz Knuth nie zauważył jeszcze jednego podejścia, związanego z podawaną wielokrotnie przez niego równoważną postacią liczby.
Liczba binarna a_n a_{n-1}... a_0 może być przedstawiona następująco:
A = (...(a_n*2+a_{n-1})*2+...)*2 + a_0
Oznaczmy A_i nawias zawierający jako najmniej znaczącą cyfrę a_i.
Obliczając dwie takie liczby A oraz B uzyskujemy iloczyn
A*B = (A_1*2 + a_0) * (B_1*2 + b_0 ) = ((A_1*B_1)*2 + A_1*b_0 + a_0*B_1)*2 + a_0*b_0
Ponieważ mnożenie przez 2 jest równoważne przesunięciu, mamy 3 mnożenia przez cyfry 0, 1; do wyniku dodajemy 3 sumy cząstkowe oraz mamy wywołanie rekurencyjne dla liczb mających mniej cyfr.
Złożoność tego algorytmu to 3 mnożenia, 3 dodawania oraz 3 przesunięcia na każdą iterację, za każdym razem wyznaczamy 2 cyfry. Do wyznaczonych cyfr najmniej znaczących już nie musimy wracać. Iteracji jest tyle, by któraś z liczb A_i, B_i stała się jednocyfrowa.
Ponieważ w przypadku binarnym mnożenia mozemy zastąpić dodawaniami liczb o długości co najwyżej max(N,M), cała złożoność nie przekracza złożoności sum coraz krótszych liczb. Jest zatem co najwyzej kwadratowa dla wiekszej z nich. Dokladniej porownujac, uzyskuje zlozonosc taka sama jak u Knutha O(NM), lecz na coraz mniejszych cyfrach.
28 stycznia 2012
Sposób konwersji
W ostatnim poście pokazałem, jak można stosować cechę podzielności, ale nie wskazałem szybkiego sposobu przechodzenia z systemu na system. Za to użyłem takiego przy konwertowaniu z systemu dziesiątkowego na ósemkowy.
Zatem dodatek: szybki sposób konwersji systemów pozycyjnych.
Zanim go jednak przedstawię, oto różnica między liczbą a cyfrą.
CYFRA danego systemu liczbowego to liczba mieszcząca się między 0 włącznie oraz podstawą systemu liczbowego p, czyli w przedziale [0, p). Stanowi zarazem podstawowy składnik konstrukcji liczb. Dla małych podstaw cyfry mają własne symbole graficzne.
LICZBA [w systemie pozycyjnym] to [uporządkowany] ciąg cyfr a_n .. a_1 a_0.
W algorytmie poniższym cyfry są traktowane jako liczby, oraz w czasie początkowych przekształceń ignorujemy nałożone nań ograniczenia na wielkość.
Mając liczbę a_n...a_0 w systemie p, chcemy ją zapisać w systemie o podstawie p+r (p+r>1), stosujemy oparty na schemacie Hornera zapisu liczb
(...(a_n*p+a_{n-1})...)*p+a_0
następujący algorytm:
inicjacja: sprawdzamy przyrost r, załóżmy ze jest r>0 Bierzemy a_n, pozostałe cyfry czekają w kolejce [a_{n-1} , ... , a_0]
1) pobieramy cyfrę a_j z kolejki;
2) każdą cyfrę a_i (zaczynając od i=j, zwiększając do i=n ) modyfikujemy do liczby a_i := a_i - r*a_{i+1}, kiedy nie ma wartości i+1, traktujemy ją jako 0;
3) powstałe liczby sprowadzamy do cyfr dodając t razy (p+r) - pożyczamy od cyfr bardziej znaczących, aby liczba stojąca na miejscu cyfry była w odpowiednim przedziale;
4) poprzedzającą cyfrę a_{i+1} zmniejszamy o znalezione w 3) t;
powtarzamy 3) 4) tak długo, aż liczba będzie się składała tylko z prawidłowych w danym systemie cyfr;
5) kiedy kolejka cyfr jest pusta, uzyskujemy postać liczby w systemie (p+r), w przeciwnym przypadku wracamy do 1)
Na zakończenie modyfikujemy aktualną krotność cyfr, gdyż wartość ta może się zmienić.
Kiedy r jest dodatnie, w 2) dodajemy zamiast odejmować, zaś liczbę sprowadzamy do cyfry przez przekazywanie nadmiarów (p+r) cyfrom bardziej znaczącym.
Sposób nie jest tak szybki jak konwersje między systemami o podstawach będących potęgami jednej liczby a, w których liczbę zapisujemy przy podstawie a, a następnie cyfra powstaje z paczki odpowiedniej długości, np. konwersja z systemu o podstawie 27 na system o podstawie 9 przez system o podstawie 3:
22 2 4_{27} = 211 002 011_3 = 2 11 00 20 11_3 = 24064_9,
ale i tak znacznie szybszy niż stosowanie definicji systemów.
Przykład: przekonwertujemy szesnastkowe 0xBACA na system dziesiętny.
cyfry początkowe: [ 0xB=11, 0xA=10, 0xC=12, 0xA=10]
Początek to lista 11, mamy przyrost 10-16=-6, czyli do poszczególnych cyfr będziemy dodawać iloczyny 6
zaczynamy pierwszą iterację:
11 10+6*11
11 76
na pozycji jedności mamy liczbę! 76, którą należy zmniejszyć, aby na powrót stała się cyfrą systemu, tym razem dziesiątkowego
(11+t) (76-t*10) t=7
18 6
teraz cyfra dziesiątek jest za duża. Przenosimy nadmiar tworząc następną cyfrę, cyfrę setek.
1 8 6
Dla sprawdzenia, 11*16+10 = 186 = 1*10^2 + 8*10 + 6,
Kolejna iteracja, dołączamy cyfrę 0xC=12
1 8 6 12
1[+0] 8+6*1 6+6*8 12+6*6
1 14 54 48
przenosimy nadmiary (od razu wynik) (11*16+10)*16+12 = 2988
2 9 8 8
Ostatnia cyfra, czyli ostatnia iteracja
2 9 8 8 10
2[+0] 9+6*2 8+6*9 8+6*8 10+6*8
2 21 62 56 58
Przenosimy nadmiary
4 7 8 1 8
Zatem szesnastkowe 0xBACA to dziesiętne 47818.
W drugą stronę podobnie, lecz mamy 5 iteracji, przyrost 6. Pierwsza jest postaci
4[-0] 7-6*4
4 -17
naprawa polega na dodawaniu docelowej podstawy 16, czyli
4-2 -17+2*16
2 15
Kolejna iteracja
2 15 8
2 15-6*2 8-6*15
2 3 -82
1 13 14
Kolejna iteracja
1 13 14 1
1 13-6*1 14-6*13 1-6*14
1 7 -64 -83
1 2 10 13
Ostatnia iteracja
1 2 10 13 8
1 2-6*1 10-6*2 13-6*10 8-6*13
1 -4 -2 -47 -70
0 11 10 12 10
Ostatecznie przekształcamy te szesnastkowe cyfry na liczbę 0xBACA.
Zatem dodatek: szybki sposób konwersji systemów pozycyjnych.
Zanim go jednak przedstawię, oto różnica między liczbą a cyfrą.
CYFRA danego systemu liczbowego to liczba mieszcząca się między 0 włącznie oraz podstawą systemu liczbowego p, czyli w przedziale [0, p). Stanowi zarazem podstawowy składnik konstrukcji liczb. Dla małych podstaw cyfry mają własne symbole graficzne.
LICZBA [w systemie pozycyjnym] to [uporządkowany] ciąg cyfr a_n .. a_1 a_0.
W algorytmie poniższym cyfry są traktowane jako liczby, oraz w czasie początkowych przekształceń ignorujemy nałożone nań ograniczenia na wielkość.
Mając liczbę a_n...a_0 w systemie p, chcemy ją zapisać w systemie o podstawie p+r (p+r>1), stosujemy oparty na schemacie Hornera zapisu liczb
(...(a_n*p+a_{n-1})...)*p+a_0
następujący algorytm:
inicjacja: sprawdzamy przyrost r, załóżmy ze jest r>0 Bierzemy a_n, pozostałe cyfry czekają w kolejce [a_{n-1} , ... , a_0]
1) pobieramy cyfrę a_j z kolejki;
2) każdą cyfrę a_i (zaczynając od i=j, zwiększając do i=n ) modyfikujemy do liczby a_i := a_i - r*a_{i+1}, kiedy nie ma wartości i+1, traktujemy ją jako 0;
3) powstałe liczby sprowadzamy do cyfr dodając t razy (p+r) - pożyczamy od cyfr bardziej znaczących, aby liczba stojąca na miejscu cyfry była w odpowiednim przedziale;
4) poprzedzającą cyfrę a_{i+1} zmniejszamy o znalezione w 3) t;
powtarzamy 3) 4) tak długo, aż liczba będzie się składała tylko z prawidłowych w danym systemie cyfr;
5) kiedy kolejka cyfr jest pusta, uzyskujemy postać liczby w systemie (p+r), w przeciwnym przypadku wracamy do 1)
Na zakończenie modyfikujemy aktualną krotność cyfr, gdyż wartość ta może się zmienić.
Kiedy r jest dodatnie, w 2) dodajemy zamiast odejmować, zaś liczbę sprowadzamy do cyfry przez przekazywanie nadmiarów (p+r) cyfrom bardziej znaczącym.
Sposób nie jest tak szybki jak konwersje między systemami o podstawach będących potęgami jednej liczby a, w których liczbę zapisujemy przy podstawie a, a następnie cyfra powstaje z paczki odpowiedniej długości, np. konwersja z systemu o podstawie 27 na system o podstawie 9 przez system o podstawie 3:
22 2 4_{27} = 211 002 011_3 = 2 11 00 20 11_3 = 24064_9,
ale i tak znacznie szybszy niż stosowanie definicji systemów.
Przykład: przekonwertujemy szesnastkowe 0xBACA na system dziesiętny.
cyfry początkowe: [ 0xB=11, 0xA=10, 0xC=12, 0xA=10]
Początek to lista 11, mamy przyrost 10-16=-6, czyli do poszczególnych cyfr będziemy dodawać iloczyny 6
zaczynamy pierwszą iterację:
11 10+6*11
11 76
na pozycji jedności mamy liczbę! 76, którą należy zmniejszyć, aby na powrót stała się cyfrą systemu, tym razem dziesiątkowego
(11+t) (76-t*10) t=7
18 6
teraz cyfra dziesiątek jest za duża. Przenosimy nadmiar tworząc następną cyfrę, cyfrę setek.
1 8 6
Dla sprawdzenia, 11*16+10 = 186 = 1*10^2 + 8*10 + 6,
Kolejna iteracja, dołączamy cyfrę 0xC=12
1 8 6 12
1[+0] 8+6*1 6+6*8 12+6*6
1 14 54 48
przenosimy nadmiary (od razu wynik) (11*16+10)*16+12 = 2988
2 9 8 8
Ostatnia cyfra, czyli ostatnia iteracja
2 9 8 8 10
2[+0] 9+6*2 8+6*9 8+6*8 10+6*8
2 21 62 56 58
Przenosimy nadmiary
4 7 8 1 8
Zatem szesnastkowe 0xBACA to dziesiętne 47818.
W drugą stronę podobnie, lecz mamy 5 iteracji, przyrost 6. Pierwsza jest postaci
4[-0] 7-6*4
4 -17
naprawa polega na dodawaniu docelowej podstawy 16, czyli
4-2 -17+2*16
2 15
Kolejna iteracja
2 15 8
2 15-6*2 8-6*15
2 3 -82
1 13 14
Kolejna iteracja
1 13 14 1
1 13-6*1 14-6*13 1-6*14
1 7 -64 -83
1 2 10 13
Ostatnia iteracja
1 2 10 13 8
1 2-6*1 10-6*2 13-6*10 8-6*13
1 -4 -2 -47 -70
0 11 10 12 10
Ostatecznie przekształcamy te szesnastkowe cyfry na liczbę 0xBACA.
23 stycznia 2012
Podzielnosc w systemach niedziesiatkowych
Ułamki egipskie oraz algorytm faktoryzacji zwrócily moja uwagę na systemy niedziesiątkowe. Na razie system binarny oraz systemy o podstawie będące potęgą 2.
Występują bardzo proste cechy podzielności dla liczb będących postaci 2^n +- 1.
Dzieląc liczbę w systemie o podstawie 2^n na paczki binarne długości n-1 znaków, liczba jest podzielna przez 2^n-1 gdy suma wartości poszczególnych paczek binarnych też jest podzielna. (por. cecha podzielności przez 9).
Dla liczb postaci 2^n+1 reszta jest równa reszcie sumy naprzemiennej tych paczek (por. cecha podzielności przez 11.
Do odpowiednich liczb należą 3, 5, 7, 9, 15, 17, 31, 33 i wiele innych.
Wystarczy przekształcić liczbę do postaci np. oktagonalnej by już mieć postać równoważną binarnej i zastosować cechę.
Przykład: sprawdzimy resztę z dzielenia 3523432 przez 17 równe 10001 binarnie.
Przekształcamy 3523432 do systemu ósemkowego, dodając do każdej cyfry z wyjątkiem pierwszej przed '|' podwojoną wcześniejszą i 'naprawiając cyfry' przez przenoszenie nadmiarów 8:
3 5 | 2 3 4 3 2
4 3 2 | 3 4 3 2
5 4 0 3 | 4 3 2
6 7 0 3 4 | 3 2
1 0 4 6 4 2 3 | 2
1 2 6 0 1 2 7 2 |
1 5 3 4 1 5 5 0
Zatem w ósemkowym liczba wyglada 15341550 = binarnie 001 101 011 100 001 101 101 000 = 0011 0101 1100 0011 011 01000 = heksadecymalnie 3 5 12 3 6 8.
Według cechy podzielności, naprzemienna suma -3+5-12+3-6+8 = -5 = 12 (17) ma taką samą resztę. Istotne są tu znaki, ale rzeczywiście, wartość ta w dziesiatkowym przedstawi się jako 207260*17+12.
Algorytm dotyczący sposobu przechodzenia między systemami jest opublikowany w następnym poście.
Występują bardzo proste cechy podzielności dla liczb będących postaci 2^n +- 1.
Dzieląc liczbę w systemie o podstawie 2^n na paczki binarne długości n-1 znaków, liczba jest podzielna przez 2^n-1 gdy suma wartości poszczególnych paczek binarnych też jest podzielna. (por. cecha podzielności przez 9).
Dla liczb postaci 2^n+1 reszta jest równa reszcie sumy naprzemiennej tych paczek (por. cecha podzielności przez 11.
Do odpowiednich liczb należą 3, 5, 7, 9, 15, 17, 31, 33 i wiele innych.
Wystarczy przekształcić liczbę do postaci np. oktagonalnej by już mieć postać równoważną binarnej i zastosować cechę.
Przykład: sprawdzimy resztę z dzielenia 3523432 przez 17 równe 10001 binarnie.
Przekształcamy 3523432 do systemu ósemkowego, dodając do każdej cyfry z wyjątkiem pierwszej przed '|' podwojoną wcześniejszą i 'naprawiając cyfry' przez przenoszenie nadmiarów 8:
3 5 | 2 3 4 3 2
4 3 2 | 3 4 3 2
5 4 0 3 | 4 3 2
6 7 0 3 4 | 3 2
1 0 4 6 4 2 3 | 2
1 2 6 0 1 2 7 2 |
1 5 3 4 1 5 5 0
Zatem w ósemkowym liczba wyglada 15341550 = binarnie 001 101 011 100 001 101 101 000 = 0011 0101 1100 0011 011 01000 = heksadecymalnie 3 5 12 3 6 8.
Według cechy podzielności, naprzemienna suma -3+5-12+3-6+8 = -5 = 12 (17) ma taką samą resztę. Istotne są tu znaki, ale rzeczywiście, wartość ta w dziesiatkowym przedstawi się jako 207260*17+12.
Algorytm dotyczący sposobu przechodzenia między systemami jest opublikowany w następnym poście.
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.
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
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!
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!
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.
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.
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.
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.
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.
13 października 2010
Logika na listach
Poczytałem sobie książkę o programowaniu na listach, dokładniej o języku LISP. Podejście niestandardowe, dosyć bliskie moim zachciankom. Zacząłem testować to podejście w praktyce i zaczęło się!
Przebudowanie funkcji, które zmieniają się dynamicznie w czasie działania programu - zapewnione niemalże gratis. Mogą nawet powstawać i być usuwanymi. Zwrot wielu wartości naraz, przepraszam, co znaczy wartość. Wszystko, co jest umieszczone na listach istnieje, niepotrzebna im jakaś tam wartość. Ona może co najwyżej służyć jako dodatkowe pole.
Zajrzałem do zwykłej logiki z tym podejściem. Dowód formalny, zwłaszcza twierdzenie o dedukcji upraszcza się tak bardzo, że po wprowadzeniu listy założeń i ich przebudowie za pomocą reguły odrywania nie ma co robić. Wystarczy tylko sprawdzić, czy wyrażenie dowodzone znajduje się na liście.
I dodatkowa niespodzianka, kiedy wyrażenie musi korzystać z jakiegoś dodatkowego założenia o przestrzeni, lista wskaże tylko wszystkie prawdziwe przypadki!
Przy dowodzie prawa Dunsa Scota mam założone tylko istnienie oraz brak jednego zdania. Nie dowiodę innego, chyba... że przestrzeń jest zupełna, oraz prawda i fałsz są jedynymi możliwościami! Słowem rewelacja. Od razu wykryte ukryte założenia, o których normalnie się nie wspomina. Konstruktywizm w pełnej krasie. Na razie to pierwsze spojrzenie, ale im wiecej wzorów dowodzę w ten sposób, tym bardziej mi się to podoba.
Przebudowanie funkcji, które zmieniają się dynamicznie w czasie działania programu - zapewnione niemalże gratis. Mogą nawet powstawać i być usuwanymi. Zwrot wielu wartości naraz, przepraszam, co znaczy wartość. Wszystko, co jest umieszczone na listach istnieje, niepotrzebna im jakaś tam wartość. Ona może co najwyżej służyć jako dodatkowe pole.
Zajrzałem do zwykłej logiki z tym podejściem. Dowód formalny, zwłaszcza twierdzenie o dedukcji upraszcza się tak bardzo, że po wprowadzeniu listy założeń i ich przebudowie za pomocą reguły odrywania nie ma co robić. Wystarczy tylko sprawdzić, czy wyrażenie dowodzone znajduje się na liście.
I dodatkowa niespodzianka, kiedy wyrażenie musi korzystać z jakiegoś dodatkowego założenia o przestrzeni, lista wskaże tylko wszystkie prawdziwe przypadki!
Przy dowodzie prawa Dunsa Scota mam założone tylko istnienie oraz brak jednego zdania. Nie dowiodę innego, chyba... że przestrzeń jest zupełna, oraz prawda i fałsz są jedynymi możliwościami! Słowem rewelacja. Od razu wykryte ukryte założenia, o których normalnie się nie wspomina. Konstruktywizm w pełnej krasie. Na razie to pierwsze spojrzenie, ale im wiecej wzorów dowodzę w ten sposób, tym bardziej mi się to podoba.
18 sierpnia 2010
Przyszle cele programistyczne
Czytałem ostatnio kilka pozycji o programowaniu strukturalnym. Podejście obiektowe daje potężnego kopniaka programistycznego. Ale to jeszcze nie to. Powoli koryguję swój własny styl programowania - pod DOSem lub Linuxem. Windows, a tak, wyglądam czasem przez nie, popatrzeć np. na ogródek.
W styczniowym SDJ 1/2010 jest artykuł o wywoływaniu funkcji z opóźnieniem. Idealne do gier! Największy szok to ten, że działania są obiektami, domyślnie rzeczownikami. Wchodzi programowanie sterowane zdarzeniami. Przebieg tury gry jest następujący
Wykonuję kilka pętli na strukturze kolejkopodobnej. Przebieg:
1: obiekty znajdujące się na scenie szykują 2
2: obiekty z 1 deklarują swe działania (ogólnie) tworząc 3, ewentualnie 4, są sortowane
3: posortowane obiekty z 2 uszczegóławiają swoje ruchy, modyfikując swoje atrybuty, przechodzą w stan 0 lub 1
0: obiekt ginie lub ucieka, słowem znika.
pozostałe różne od powyższych: końcowa modyfikacja atrybutów, przejście w stan 1
Pod koniec wszystkie obiekty (stan 1) udają się do następnej tury.
Testowałem ten przebieg, kiedy nie było prądu. Najmocniejszą cechą jest ta, że jestem w stanie uzyskać łatwym kosztem nieoznaczoność w sposób deterministyczny!
W styczniowym SDJ 1/2010 jest artykuł o wywoływaniu funkcji z opóźnieniem. Idealne do gier! Największy szok to ten, że działania są obiektami, domyślnie rzeczownikami. Wchodzi programowanie sterowane zdarzeniami. Przebieg tury gry jest następujący
Wykonuję kilka pętli na strukturze kolejkopodobnej. Przebieg:
1: obiekty znajdujące się na scenie szykują 2
2: obiekty z 1 deklarują swe działania (ogólnie) tworząc 3, ewentualnie 4, są sortowane
3: posortowane obiekty z 2 uszczegóławiają swoje ruchy, modyfikując swoje atrybuty, przechodzą w stan 0 lub 1
0: obiekt ginie lub ucieka, słowem znika.
pozostałe różne od powyższych: końcowa modyfikacja atrybutów, przejście w stan 1
Pod koniec wszystkie obiekty (stan 1) udają się do następnej tury.
Testowałem ten przebieg, kiedy nie było prądu. Najmocniejszą cechą jest ta, że jestem w stanie uzyskać łatwym kosztem nieoznaczoność w sposób deterministyczny!
Subskrybuj:
Posty (Atom)