Na prawym marginesie - nowy gadżet. Z grubsza jest to zabawka (niedoskonała mocno) związana z L-systemami. Napiszę o niej i o nich coś więcej wkrótce. Zaby uruchomić: Najpierw kliknąć na link :"Gdy wyrasta kwiat ze ziemi ..." Potem na "Niech wyrasta ...". Można modyfikować reguły i dodawać nowe. Na własną odpowiedzialność oczywiście...
Działa w Firefoxie. W IE, przynajmniej moim, nie.
Miłej (ewentualnie) zabawy...
Aha! Frazeologia zaczerpnięta z wierszyka, który kiedyś popularyzował mój kolega z akademika:
"Gdy wyrasta kwiat ze ziemi, wszyscy są zadowoleni, lecz gdy rośnie trawa: to już inna sprawa..."
2008-07-25
2008-07-15
Haskell i Pell
Jak mówiłem tak zrobiłem, tj. sprawdziłem algorytm Wildbergera w praniu. Poniżej kod funkcji rozwiązującej równanie Pella w oparciu o ów algorytm w Haskellu. Poza rekurencją i "pattern matching" nie demonstruje on pazura Haskella, ale mam nadzieję, że jest równie przyjemny w czytaniu jak był w pisaniu...
Funkcja solvePell, bierze d z rówania Pella jako argument i zwraca parę liczb będąca pewnym rozwiązaniem równiania. Trzeba pamiętać, by d nie było kwadratem - tego funkcja nie sprawdza. Na kwadratach wchodzi zwykle w nieskończoną rekurencję ... Niestety, są i smutniejsze wieści. Algorym nie zawsze znajduje rozwiązanie fundamentalne. Np. dla d = 13, rozwiązaniem fundamentalnym jest x=18 y=5, podczas gdy zaimplementowany algorytm daje rozwiązanie: x=649 y=180, które jest następnym z kolei (bo 649=18^2+13*5^2 i 180 = 2*5*18). Tym samym zrozumiałe staje się, dlaczego w pracy Wildbergera nie było stosownego dowodu ;). Warto pomyśleć, czy nie da się tej metody jakoś zmodyfikować (nie zmieniając jednak jej ducha) by algorytm zwracał zawsze rozwiazanie fundamentalne.
solvePell :: Integer -> (Integer, Integer)
solvePell d = (b11, b21) where
(b11, b12, b21, b22) = searchFixedPointMtr (1, 1, 0, 1) where
searchFixedPointMtr p | (o11, o12, o21, o22) == (1, 0, 0 , -d) = r
| o11 > 0 && o22 < 0 = searchFixedPointMtr r
|otherwise = searchFixedPointMtr tr where
r = mult p (1, 1, 0, 1)
tr = mult p (1, 0, 1, 1)
(o11, o12, o21, o22) = mult( mult (transpose r) (1,0,0,-d) ) r
transpose (a11 ,a12, a21, a22) = (a11, a21, a12, a22)
mult (a11, a12, a21, a22) (b11, b12, b21, b22)=
(a11*b11+a12*b21, a11*b12+a12*b22,
a21*b11+a22*b21, a21*b12+a22*b22)
Funkcja solvePell, bierze d z rówania Pella jako argument i zwraca parę liczb będąca pewnym rozwiązaniem równiania. Trzeba pamiętać, by d nie było kwadratem - tego funkcja nie sprawdza. Na kwadratach wchodzi zwykle w nieskończoną rekurencję ... Niestety, są i smutniejsze wieści. Algorym nie zawsze znajduje rozwiązanie fundamentalne. Np. dla d = 13, rozwiązaniem fundamentalnym jest x=18 y=5, podczas gdy zaimplementowany algorytm daje rozwiązanie: x=649 y=180, które jest następnym z kolei (bo 649=18^2+13*5^2 i 180 = 2*5*18). Tym samym zrozumiałe staje się, dlaczego w pracy Wildbergera nie było stosownego dowodu ;). Warto pomyśleć, czy nie da się tej metody jakoś zmodyfikować (nie zmieniając jednak jej ducha) by algorytm zwracał zawsze rozwiazanie fundamentalne.
Do badań porównawczych użyłem sprawdzonej już w bojach, on-linowej maszyny do poszukiwania fundamentalnych rozwiązań równania Pella którą niniejszym polecam: Diophantus Quadraticus. Dla miłośników numerologii, przykładowe wynik działania funkcji (pod Hugsem):
Main> solvePell 12
(7,2)
Main> solvePell 123
(122,11)
Main> solvePell 1234
(586327869067265,16691023073856)
Main> solvePell 12345
(1196823028442576899590849641,10771703481902106796084652)
Main> solvePell 123456
(32153667637494049,91511235212695)
Main> solvePell 1234567
(20371567825887579087969922203933358793493846332810110697
4127231916998110712447355624,1833441773536251588833840127
75408990796176026949965279326746283914164614149841725)
Main> solvePell 12345678
(84798178834254206501069091776063801828858638442491294173
283622693331157941169053721682146500840778040795681426799
746373774600679194577190578795925022609963251697702932038
103575417349220734335472506700750376403558084067176117304
353961009320426319261060613871588088528284393528998330022
695959115757272835324559892633223467646161202348129574120
811322088113694783,24133985779040703487042001168546778233
886602226457226201732495439539842758227586390869258263482
721919445559004333460853375915877499010684711766338764074
438034949056494509471323897949013056855661657290867499070
288510685596491236418010367399292614822499208206228574471
914923864025707862772212062023636759525773725225355147035
172813431107542245055578655655064)
2008-07-14
W słońcu i w deszczu
Raz za oknem żar. Rekordowe temperatury. Organizm traci wodę. Potem odmiana. Ulewa, burza. Potem 15 stopni za oknem. Klimat umiarkowany, nie ma co...
W takich okolicznościach przyrody zwolniłem z lekturami. Diogenes Laertios i jego plotkarskie opowiesci o greckich perwersjach umysłowych powędrował z porotem na półkę z zakładką włożoną gdzieś w jednej czwartej grubości książki. Prz łóżku wala się - bo wezbrał we mnie apetyt na jakiś wielki epicki kawałek - drugi już tom "Nędzników" Wiktora Hugo. Wielka literatura w starym dobrym stylu.
Poczta, z przygodami dostarczyła mi dwie książeczki, które korzystając z przyjemnego dla polskiego konsumenta kursu dolara kupiłem wysyłkowo w Amazonie. Bawię się językiem Haskell (jedna z nich jego m.in. dotyczy) odkrywając kolejne więzi między programowaniem, matematyką i resztą świata.
W moim prywatnym piekiełku, po lekturze kilku prac i wertując kolejną amazonową książkę, jakby się trochę przejaśnia. Ależ byłem głupi formułując w naprędce i na bazie słabej intuicji moje małe hipotezy (tu)! Sprawa jest, jak to w życiu bywa, znacznie bardziej tajemnicza i głęboka. Jak pozbieram myśli do kupy, i zsyntetyzuję to co dotychczas na ten temat przeczytałem, to pewnie coś na ten temat napiszę i na blogu. W każdym razie związkami między regularnościami i pewnymi formami "automatyzmu" w różnych typach przedstawień liczb matematycy zajmują się od dawna i sporo na ten temat wiadomo a jeszcze więcej, jak można się domyślić, nie wiadomo.
Przy okazji drobnych studiów nad tym tematem, wróciłem do powiązanych z nim spraw, którymi trochę zajmowałem się w zeszłym roku: koalgebry itd. Stąd już niedaleko do innych konstrukcji opartych na teorii kategorii w tym i monad więc z powrotem do Haskella i jego wysoce zmatematyzowanych abstrakcji. Takie to wiry, szumy zlepy i ciągi tego lata ...
Z innej, ale podobnej beczki: Ale się czasem trafia uroczy kawałek matematyki!
Kilka tygodni temu na arxiv pojawiła się praca australijskiego matematyka N.J.Wildbergera pt. "Pell's equation without irrational numbers". Praca jest krótka, elementarna (poza szkolną matematykę wychodzi chyba tylko pojęcie macierzy: ich mnożenia i wyznacznika, ale w superprostych przypadkach) i prosta, tj. dowody są bardzo klarowne. W sam raz na niecałą godzinę czytania.
Przypominam równanie Pella:
x^2-D*y^2 = 1
gdzie x i y to szukane a D > 0 jest liczbą naturalną niebędącą kwadratem. Chcemy równanie to rozwiązywać w liczbach naturalnych (>0).
Algorytm klasyczny (nie wiem kto go podał jako pierwszy: Lagrange ?) polega na rozwijaniu pierwiastka kwadratowego z D do ułamka łańcuchowego .Dowodzi się, że takie rozwinięcie jest okresowe i bierze się odpowiedni n-ty redukt gdzie n jest funkcją długości okresu. Jaką funkcją: szczerze mówiąc nie pamiętam teraz, ale to łatwo znaleźć na sieci.
Autor podaje algorytm rozwiązywania równania Pella odmienny od tego algorytmu. Postaram się tu pokrótce go przedstawić i mam nadzieję, że niczego nie pomieszam:
Oznaczenie: Przez X^T gdzie X jest macierzą, rozumiem macierz transponowaną do X (tj taką, której wiersze odpowiadają kolumnom X).
Wychodzimy od macierzy:
|1 0|
A = | |
|0 -D|
gdzie D to owo D z równania Pella. Rozważamy też macierz:
|1 1|
R = | |
|0 1|
Konstruujemy ciąg macierzy B_0, ... w taki sposób, że B_0 = R^T lub R, tak, by macierz B_0^T*A*B_0 miała własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Dowodzi się, że można wybrać jednoznacznie między T i R^T.
Potem, indukcyjnie: mając zdefiniowane B_n, definiujemy B_(n+1) = B_n*R lub B_n*R^T, tak by B_(n+1)^T*A*B_(n+1) miała wspomnaną wyżej własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Ponownie dowodzi się, że w każdym kroku można wybrać jednoznacznie między T i R^T.
Dowodzi się, że dla pewnego n, macierz B_n z tego ciągu ma własność B_n^T*A*B_n = A. Pierwsza kolumna macierzy B_n wyznacza wówczas rowziązanie równania Pella.
Niestety autor nie dowodzi, że wynikiem działania algorytmu jest najmniejsze rozwiązanie. Ja zamierzam się sprawdzić w ustaleniu tego.
Algorytm zaimplementuję, oczywiscie w Haskellu i obiecuję przedstawić tu program.
W ogóle do Haskella będę wracał, bo to naprawdę fascynujący język, zmuszający do zmiany sposobu myślenia. Poza tym jest bardzo sexy i gdybym nie był żonaty podrywał bym na niego dziewczyny.
W takich okolicznościach przyrody zwolniłem z lekturami. Diogenes Laertios i jego plotkarskie opowiesci o greckich perwersjach umysłowych powędrował z porotem na półkę z zakładką włożoną gdzieś w jednej czwartej grubości książki. Prz łóżku wala się - bo wezbrał we mnie apetyt na jakiś wielki epicki kawałek - drugi już tom "Nędzników" Wiktora Hugo. Wielka literatura w starym dobrym stylu.
Poczta, z przygodami dostarczyła mi dwie książeczki, które korzystając z przyjemnego dla polskiego konsumenta kursu dolara kupiłem wysyłkowo w Amazonie. Bawię się językiem Haskell (jedna z nich jego m.in. dotyczy) odkrywając kolejne więzi między programowaniem, matematyką i resztą świata.
W moim prywatnym piekiełku, po lekturze kilku prac i wertując kolejną amazonową książkę, jakby się trochę przejaśnia. Ależ byłem głupi formułując w naprędce i na bazie słabej intuicji moje małe hipotezy (tu)! Sprawa jest, jak to w życiu bywa, znacznie bardziej tajemnicza i głęboka. Jak pozbieram myśli do kupy, i zsyntetyzuję to co dotychczas na ten temat przeczytałem, to pewnie coś na ten temat napiszę i na blogu. W każdym razie związkami między regularnościami i pewnymi formami "automatyzmu" w różnych typach przedstawień liczb matematycy zajmują się od dawna i sporo na ten temat wiadomo a jeszcze więcej, jak można się domyślić, nie wiadomo.
Przy okazji drobnych studiów nad tym tematem, wróciłem do powiązanych z nim spraw, którymi trochę zajmowałem się w zeszłym roku: koalgebry itd. Stąd już niedaleko do innych konstrukcji opartych na teorii kategorii w tym i monad więc z powrotem do Haskella i jego wysoce zmatematyzowanych abstrakcji. Takie to wiry, szumy zlepy i ciągi tego lata ...
Z innej, ale podobnej beczki: Ale się czasem trafia uroczy kawałek matematyki!
Kilka tygodni temu na arxiv pojawiła się praca australijskiego matematyka N.J.Wildbergera pt. "Pell's equation without irrational numbers". Praca jest krótka, elementarna (poza szkolną matematykę wychodzi chyba tylko pojęcie macierzy: ich mnożenia i wyznacznika, ale w superprostych przypadkach) i prosta, tj. dowody są bardzo klarowne. W sam raz na niecałą godzinę czytania.
Przypominam równanie Pella:
x^2-D*y^2 = 1
gdzie x i y to szukane a D > 0 jest liczbą naturalną niebędącą kwadratem. Chcemy równanie to rozwiązywać w liczbach naturalnych (>0).
Algorytm klasyczny (nie wiem kto go podał jako pierwszy: Lagrange ?) polega na rozwijaniu pierwiastka kwadratowego z D do ułamka łańcuchowego .Dowodzi się, że takie rozwinięcie jest okresowe i bierze się odpowiedni n-ty redukt gdzie n jest funkcją długości okresu. Jaką funkcją: szczerze mówiąc nie pamiętam teraz, ale to łatwo znaleźć na sieci.
Autor podaje algorytm rozwiązywania równania Pella odmienny od tego algorytmu. Postaram się tu pokrótce go przedstawić i mam nadzieję, że niczego nie pomieszam:
Oznaczenie: Przez X^T gdzie X jest macierzą, rozumiem macierz transponowaną do X (tj taką, której wiersze odpowiadają kolumnom X).
Wychodzimy od macierzy:
|1 0|
A = | |
|0 -D|
gdzie D to owo D z równania Pella. Rozważamy też macierz:
|1 1|
R = | |
|0 1|
Konstruujemy ciąg macierzy B_0, ... w taki sposób, że B_0 = R^T lub R, tak, by macierz B_0^T*A*B_0 miała własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Dowodzi się, że można wybrać jednoznacznie między T i R^T.
Potem, indukcyjnie: mając zdefiniowane B_n, definiujemy B_(n+1) = B_n*R lub B_n*R^T, tak by B_(n+1)^T*A*B_(n+1) miała wspomnaną wyżej własność: element w lewym górnym rogu był większy od zera a element w prawym dolnym rogu był mniejszy od zera. Ponownie dowodzi się, że w każdym kroku można wybrać jednoznacznie między T i R^T.
Dowodzi się, że dla pewnego n, macierz B_n z tego ciągu ma własność B_n^T*A*B_n = A. Pierwsza kolumna macierzy B_n wyznacza wówczas rowziązanie równania Pella.
Niestety autor nie dowodzi, że wynikiem działania algorytmu jest najmniejsze rozwiązanie. Ja zamierzam się sprawdzić w ustaleniu tego.
Algorytm zaimplementuję, oczywiscie w Haskellu i obiecuję przedstawić tu program.
W ogóle do Haskella będę wracał, bo to naprawdę fascynujący język, zmuszający do zmiany sposobu myślenia. Poza tym jest bardzo sexy i gdybym nie był żonaty podrywał bym na niego dziewczyny.
Subskrybuj:
Posty (Atom)
Posty
