Etap 2 barokowego s.a.
Wlodzimierz Holsztynski
przez Darka naszej grupy, z wyposażenia grupy
przez materiały i wyszukiwarkę--dzięki Darku,
i z kodu brqJul, który korzysta z TWRów
oraz unika memory allocation (by nie być
spowalnianym), a jednak marnuje pamięć
tylko w n iewielkim stopniu.
Wczoraj-przedwczoraj Mirek niepokoił się,
czy program będzie dostatecznie wydajny
przy wielkich hazach. Wcześniej Artur
poruszał kwestię zmniejszenia przestrzeni
konfiguracji. Na przykład zmniejszenie
możliwych ruchów na każdym kroku
o 1%, przy zachowaniu tych samych możliwych
rozwiązań (baroków) prawdopodobnie daje
olbrzymi zysk, .(99/100)^eternity -- to nie jest
aż tak jasne, ale jednak zmniejszenie
przestrzeni konfiguracji jest ważne.
Pierwszym krokiem, bardzo prymitywnym,
było wprowadzenie TWRów.
TWRy planuję zasadniczo udoskonalić.
Jest to jednak odrębny temat. Natomiast
ostatnio wspominałem dwie idee: dno[ ]
oraz chude TWRy. Drugi etap będzie poolegal
na zakodowaniu idei idącej dalej od tych
dwóch, zaqwierającej je obie.
Obecnie algorytm za bazę danych ma
kolejne potęgi danych mu liczb pierwszych.
Algorytm drugiego etapu będzie
obracał się tylko wśród wybranych potęg
danych liczb pierwszych z nośnika, a nie
wśród pełnych odcinków potęg.
***
Byłem rano u dentysty po nieprzespanej
nocy, więc chce mi się teraz kimać.
Zadawajcie pytania, chętnie będę pisał
dokładniej, ale nijako mi jak stróż do obrazu,
musiałbym sporo wypić, a wtedy jakość
przekazu mogłaby opaść (a może dramatycznie
by się podniosła?!).
Pozdrawiam,
Włodek
PS. Mirku, otrzymałeś? Kompiluje się?
Działa? Pytania? (Hm, sam zadałem tyle,
że... o-la-la-la).
Mirek
On Mon, Jul 23, 2007 at 05:09:50AM -0700, Wlodzimierz Holsztynski wrote:
> Co mi radzicie, żebym wreszcie wyszedł
> poza 2^31 ?
Moim skromnym zdaniem jest na to jeszcze za
wcześnie (o tym dalej).
Choć na pierwszy rzut możesz zastosować:
long long int
zamiast int'a - daje to 64 bity. Na 32 bitowej
maszynie jest to wprawdzie emulowane, ale zawsze
jakiś następny krok.
On Mon, Jul 23, 2007 at 12:04:31PM -0700, Wlodzimierz Holsztynski wrote:
[...]
> Obecnie algorytm za bazę danych ma
> kolejne potęgi danych mu liczb pierwszych.
> Algorytm drugiego etapu będzie
> obracał się tylko wśród wybranych potęg
> danych liczb pierwszych z nośnika, a nie
> wśród pełnych odcinków potęg.
Za dużo wyciąłem ;), ale chcę napisać, że
podstawy teoretyczne algorytmu będą główną
siłą napędową tego projektu.
Bez tego ani rusz.
> PS. Mirku, otrzymałeś? Kompiluje się?
> Działa? Pytania? (Hm, sam zadałem tyle,
> że... o-la-la-la).
Pierwsze wrażenia na temat kodu wysłałem Włodkowi
w e-mailu.
Teraz podam uwagi (moim zdaniem) ogólniejszej
natury, lecz dotyczące wyłącznie techniczej
strony kodu projektu.
0) Mamy już pierwszy kod
1) Trzeba go zrozumieć (patrz też na PS):
- okomentować
- sformatować w sposób jednolity:
zaproponowałem użycie programu
"astyle -ZbpPUOs2"
2) Można go spróbować przenalizować profilerem
(np. gprof) pod względem elementów najbardziej
czasochłonnych.
3) Przygotować go pod biblioteki operujące na
większych liczbach:
- powinno być to jak nabardziej uniwersalne:
zmiana include <> powinna dać możliwość
testowania różnych środowisk
- ponieważ jest to program typu number
cruncher, jestem oponentem pakowania
generyczności w klasy C++ (może jestem zbyt
archaiczny)
- proponowane rozwiązanie to omakrowanie
operacji na liczbach i zdefiniowanie własnych
typów dla naszych wartości - w tej chwili
zastąpić wszystkie jawne int-y (dotyczące
wartości) czymś w rodzaju myInt.
4) Trzeba by pomyśleć o czymś w rodzaju
repozytorium CVS.
PS
Sorry tu miało coś być, ale nie analizowałem
kodu, więc na inne pytania i propozycje za wcześnie
;)
W dodatku jestem zmęczony i jakaś myśl mi
uciekła :(
Więc na razie kończę.
PS2
No nie - coś sobie przypomniałem.
Wygląda mi na to, że Twój program działa
wyłącznie na wartościach logp i nie wykonuje
eksplicite obliczeń wartości liczb.
Czy to prawda?
Jeśli tak, to jak mój program z wątku o algorytmice
- poszukiwanie liczb barokowych dla zadanego
największego podzielnika pierwszego
p|n & logp(n)==1.
Wtedy w ogóle nie są potrzebne DUŻE LICZBY w
programie (ja mam je wprawdzie w pamięci, ale
wyłącznie do wydruków - przechowywane są w
postaci stringów).
Potrzebne są wtedy jedynie bazy rekomedacji ==
faktoryzacji sd(p^x) - a do programu wprowadzać
jedynie ich numery/indeksy zamiast wartości (w
poszczególnych bazach ta numeracja może być
różna). Sądzę, że nie logp nie przekroczy
zakresu int-a ;)
Bazy można przygotować samemu. Ja już pisałem
wcześniej o moich postępach w faktoryzacji
wartości funkcji sd() w programie pari-gp -
ciągle robię postępy.
Ale niestety (bo moje postępy tego nie
dotyczą) sądzę, że wartości
sd(p^1) gdzie p > 10^100
są raczej na ogół poza naszym zasięgiem.
Wydaje mi się jednak, że głównych źródłem takich
baz powinny być tablice z Cunnimgan Project,
Cyclotomic Factorization Page, etc (mam
nadzieję, że nie poprzekręcałem).
Wlodzimierz Holsztynski
> W innym wątku:
>
> On Mon, Jul 23, 2007 at 05:09:50AM -0700, Wlodzimierz Holsztynski wrote:
> > Co mi radzicie, żebym wreszcie wyszedł
> > poza 2^31 ?
>
> Moim skromnym zdaniem jest na to jeszcze za
> wcześnie (o tym dalej).
>
> Choć na pierwszy rzut możesz zastosować:
>
> long long int
Spróbuję. W każdym razie mam częściowe rozwiązanie,
które wystarczy na pewien czas. Nowy program zacznie
działać w nieco późniejszym momencie. Liczenie
rekomendacji czyli rozkład sd(p^k), gdy sd(p^k)
jest 2^31 lub więcej, dokonam przed programem, albo
"ręcznie", albo innym programem. Dzięki temu
nowe ograniczenie będzie znacznie łagodniejsze,
bo tylko liczby pierwsze będą ograniczone:
p < 2^31
> On Mon, Jul 23, 2007 at 12:04:31PM -0700,
> Wlodzimierz Holsztynski wrote:
>
> [...]
>
> > Obecnie algorytm za bazę danych ma
> > kolejne potęgi danych mu liczb pierwszych.
> > Algorytm drugiego etapu będzie
> > obracał się tylko wśród wybranych potęg
> > danych liczb pierwszych z nośnika, a nie
> > wśród pełnych odcinków potęg.
>
> Za dużo wyciąłem ;), ale chcę napisać, że
> podstawy teoretyczne algorytmu będą główną
> siłą napędową tego projektu.
W ambitnych projektach zawsze tak musi
być (chyba że dopisze dzikie szczęście :-).
> > PS. Mirku, otrzymałeś? Kompiluje się?
> > Działa? Pytania? (Hm, sam zadałem tyle,
> > że... o-la-la-la).
>
> Pierwsze wrażenia na temat kodu wysłałem Włodkowi
> w e-mailu.
Powinienem byl użyć załącznika! Nawet dwóch.
Co wreszcie uczyniłem. Chyba masz już wersję
niepociachaną, nieporąbaną przez email?
Tak Cię bardzo przepraszam Mirku za klopot.
Pozostałym wyślę już w załączniku, ale niech się
zgłoszą!!! :-) Nie chcę robić najazdów na skrzynki,
gdy nie mają takich rzeczy w głowie.
> Teraz podam uwagi (moim zdaniem) ogólniejszej
> natury, lecz dotyczące wyłącznie techniczej
> strony kodu projektu.
>
> 0) Mamy już pierwszy kod
>
> 1) Trzeba go zrozumieć (patrz też na PS):
Pisałem coś jak tutorial. Ze zmęczenia
zapomniałem, że nie dokończyłem i że
nie wysłałem. Trochę mnie myliła cisza
na liście, przez co spowalnałem, ociągałem się.
Ale wezmę się w karby.
> - okomentować
Chyba w kodzie powinny być tylko drobne
komentarze. A prawdziwe okomentowanie
wymaga oddzielnego dokumentu.
Zawsze najważniejsze są dwie sprawy,
gdy chodzi o uprzystępnienie kodu:
(0) opis I/O
(1) opis bazy danych programy (zmiennych,
arrays, itd.)
Dopiero na 3' miejscu jest sam algorytm.
> - sformatować w sposób jednolity:
> zaproponowałem użycie programu
> "astyle -ZbpPUOs2"
Mirku, może za dużo pracy w brqJul
nie warto wkładać (chyba że łatwo, automatycznie).
Myślę już o programie:
JulEnd
Zrozumienie JulEnd będzie nieco łatwiejsze
poprzez zrozumienie brqJul najpierw, ale i tak
dobrze i tak dobrze.
> 2) Można go spróbować przenalizować profilerem
> (np. gprof) pod względem elementów najbardziej
> czasochłonnych.
To zawsze jest ciekawe, choć dla JulEnd, gdy nadejdzie
pora, będzie istotniejsze.
> 3) Przygotować go pod biblioteki operujące na
> większych liczbach:
>
> - powinno być to jak nabardziej uniwersalne:
> zmiana include <> powinna dać możliwość
> testowania różnych środowisk
>
> - ponieważ jest to program typu number
> cruncher, jestem oponentem pakowania
> generyczności w klasy C++ (może jestem zbyt
> archaiczny)
Faktycznie klasy lepiej może zrobić na koniec,
gdy wszystko będzie jasne. Nie wiem. To kwestia także
tego co kto umnie i lubi. Sam niewiele używałem klas.
Ważniejsze są w wielkich programach, z ogromną liczbą
obiektów. Tutaj staram się unikać wszelkich spowolnień.
Dlatego wprowadziłbym je dopiero pod koniec, by uniknąć
spowolnienia. W ogóle dobrze mieć nawyk klas, stosować
je odruchowo.
> - proponowane rozwiązanie to omakrowanie
> operacji na liczbach i zdefiniowanie własnych
> typów dla naszych wartości - w tej chwili
> zastąpić wszystkie jawne int-y (dotyczące
> wartości) czymś w rodzaju myInt.
Ciekawa, sensowna propozycja. Wspomnę, że
wszystkie funkcje dekalrowałem jako "init",
ządna nie jest "void", bo kiedyś się tylko
namęczyłem z "void". Zawsze coś tam zapomniałem,
i tylko w kółko walczyłem z kompilatorem, może
gorzej.
> 4) Trzeba by pomyśleć o czymś w rodzaju
> repozytorium CVS.
A co to za zwierz?
> PS2
>
> No nie - coś sobie przypomniałem.
Hej! :-) (Głowa u staruszka jednak działa! :-)
> Wygląda mi na to, że Twój program działa
> wyłącznie na wartościach logp i nie wykonuje
> eksplicite obliczeń wartości liczb.
> Czy to prawda?
OCZYWISCIE (prawda!)
Cały czas, o0d początku o to mi chodziło.
Dlatego dziwiłem się, że w ogóle w innej
nocie wspominałeś wartości.
> Jeśli tak, to jak mój program z wątku o algorytmice
> - poszukiwanie liczb barokowych dla zadanego
> największego podzielnika pierwszego
>
> p|n & logp(n)==1.
>
> Wtedy w ogóle nie są potrzebne DUŻE LICZBY w
> programie (ja mam je wprawdzie w pamięci, ale
> wyłącznie do wydruków - przechowywane są w
> postaci stringów).
>
> Potrzebne są wtedy jedynie bazy rekomedacji ==
> faktoryzacji sd(p^x) - a do programu wprowadzać
> jedynie ich numery/indeksy zamiast wartości (w
> poszczególnych bazach ta numeracja może być
> różna). Sądzę, że nie logp nie przekroczy
> zakresu int-a ;)
TAK! Myśleliśmy równolegle. Od początku chciałem
to tak czysto programować, ale chciałem też mieć
w mniarę szybko pierwszą wersję. Popełniłem
lekki kompromis. Chyba warto bylo ze względów
choćby subiektywnych, by czuć, że mamy wróbla
w ręku. Poza tym, oszacowałem czas trwania
pierwszego etapu na 8 tygodni. Przez środkowe
tygodnie źle się czułem. Ale na termin mniej więcej
zdążyłem. Teraz znowu daję nam czas gdzieś do
10-15 września na Etap 2. (O losie, chiałbym też
robić inne rzeczy :-)
> Bazy można przygotować samemu. Ja już pisałem
> wcześniej o moich postępach w faktoryzacji
> wartości funkcji sd() w programie pari-gp -
> ciągle robię postępy.
Pisz Mirku, iniformuj nas. Teraz już lepiej się
rozumiemy. Przedtem gubiłem się. Ale nie
pofolguj sobie czasem, pisz wciąż starannie,
jak najstaranniej, jak dla skończonego matoła,
jakim jestem. idea omijania wielkich liczb przyświecała
mi od samego początku barokowego s.a., b yła dla mnie
jednym z ważnych elementów atrakcyjności tego
projektu. (O zrelaksowaniu ograniczenia na p < 2^31
wspomniałem też mimochodem pod psem, kilka
czy kilkanaście godzin temu; tylko tam zaanonsowałem
stan rzeczy; wciąż nie zamierzam tam być aktywnym,
póki sytuacja pod psem wygląda po staremu czyli pod
psem; wiem jak ją zmienić praktycznie, ale jakoś mi
się już nie chce, za dużo było rozczarowań wszelakich).
> Ale niestety (bo moje postępy tego nie
> dotyczą) sądzę, że wartości
>
> sd(p^1) gdzie p > 10^100
>
> są raczej na ogół poza naszym zasięgiem.
Przezs dłuższy czas p < 2^31 powinno wystarczyć.
Ważne, że w ramach tego ograniczenia już p^k
może b yć dowolne (w efekcie nie, bo wielkie
potęgi okoażą się zbędne, nieproduktywne,
przy ograniczonych p).
> Wydaje mi się jednak, że głównych źródłem takich
> baz powinny być tablice z Cunnimgan Project,
> Cyclotomic Factorization Page, etc (mam
> nadzieję, że nie poprzekręcałem).
Jeżeli masz link, to proszę podaj. Sam też
ewentualnie poGoogle'uję. Pewnej kobiecie
google'owanie uratowało życie. W kryzysie,
google'owała swoje objawy w trakcie, i
zrozumiała, że ma atak serca. Była profesorem
chyba lingwistyki. Trochę przypadek chce,
że dziś pracuje w Google :-) To nie jest bajka
z mediów, lecz wiem od córki, bo razem pracują
(nie nad tym samym projektem). Ot dygresja.
Dziękuję Mirku, serdeczności,
Włodek
PS. Darku, odezwałeś się. Czy przesłać Ci kod?
Użyję załączników! Nie bezpośrednio w emailu.
Arturze? Pawle?