On 23.09.2016 00:16, Borneq wrote:

BTW, zerknij na wątek
"test randomizacyjny w C"
z lipca na grupie grupy pl.comp.c

Zaczęło się od pytania o zadanie domowe, ale ostetecznie
padło trochę ciekawych informacji linków;>

pzdr
bartekltg

do góry

On 25.09.2016 14:20, Borneq wrote:
> W dniu 23.09.2016 o 10:32, bartekltg pisze:
>> Po raz trzeci: po co ci ten zestaw liczb losowych?
>> Jeśli to nie kryptografia, to nie ma to sensu.
>> Jeśli to kryptografia - pewien jesteś, ze sam chcesz
>
> Jeszcze jeden problem: istnieją wydajne algorytmy sprawdzania czy duża
> liczba jest liczbą pierwszą. Potrzebują liczb losowych albo dobrych
> pseudolosowych. Liczba do sprawdzenia ma tak z kilkaset lub kilka
> tysięcy bitów natomiast generator zwraca po 24 bity i inicjowany jest
> ziarnem do 100 bitów. Czy to nie za mało? Czy ziarno musi być co
> najmniej wielkości badanej liczby?

Do kryptografii, musi!
Musisz mieć co najmniej tyle bitów entropii, ile bitów liczby.
Ale tam nie jest istotne w teście, tylko w wybieraniu liczb
pierwszych.

Test MR dobrze sobie radzi, jak wiekszosć algorytmów losowych,
na ciągu pseudolosowym.

Przeformuuj swoje pytanie tak: dlaczego całkowanie MC działa,
skoro wsadziłem tam tylko 32 albo 0 (bo zasedowałem stałą,
aby z pewnych powódów mieć powtarzalne wyniki, bo no testuje
drobne różnice w implementacji i chcę powtarzalnych warunków*)
bitów entropii?
Przecież użyłem 10 GB losowych danych! A zainicjowałem wierszykiem
o wróbelku.

Inicjalizowanie prawidzwymi bitami losowymi nie zmienia własnośći
'losowych' ciągu pseudolosowego.



pzdr
bartekltg

*) oczywiście nie mogę tego potem zostawić, bo jak będę chaił odpalić
program drugi raz, by poprawić wyniki, będą one skorelowane i nie
dostanę poprawy oszacowania wyniku ;-)

do góry

W dniu 25.09.2016 o 14:47, bartekltg pisze:
> Test MR dobrze sobie radzi, jak wiekszosć algorytmów losowych,
> na ciągu pseudolosowym.

są:
https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_p
rimality_test
https://en.wikipedia.org/wiki/AKS_primality_test
i cała kategoria:
https://en.wikipedia.org/wiki/Category:Primality_tes
ts

Trudno ocenić który test najszybszy

do góry

On 25.09.2016 15:07, Borneq wrote:
> W dniu 25.09.2016 o 14:47, bartekltg pisze:
>> Test MR dobrze sobie radzi, jak wiekszosć algorytmów losowych,
>> na ciągu pseudolosowym.
>
> są:
> https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_p
rimality_test
> https://en.wikipedia.org/wiki/AKS_primality_test
> i cała kategoria:
> https://en.wikipedia.org/wiki/Category:Primality_tes
ts
>
> Trudno ocenić który test najszybszy


?

Znów pomyliłeś wątki/posty?

pzdr
bartekltg

do góry

On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> >
> > > Jest jeden test, którego żaden deterministyczny generator nie
> > > przejdzie.
> > >
> >
> >
> > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów
> > nie jest to technicznie wykonalne;-)
> >
> > pzdr
> > bartekltg
>
> Chodziło o to, że teoretycznie można. Teoretycznie każdy
> deterministyczny ciąg da się mocno skompresować. W praktyce
> jest to niewykonalne, ponieważ trzaby sprawdzać kolejno
> wszystkie metody kompresji. Niemniej każdy deterministyczny
> ciąg ma małą złożoność kołmogorowa.

jest znacznie gorzej,
tu się okazuje, że nawet teoretycznie nie można ;-)

https://en.wikipedia.org/wiki/Kolmogorov_complexity#
Uncomputability_of_Kolmogorov_complexity

" there is no program which takes a string s as input and produces
the integer K(s) as output."

Polecam dowod, bardzo ładny.

pzdr
bartekltg

do góry

On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > >
> > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > przejdzie.
> > > >
> > >
> > >
> > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów
> > > nie jest to technicznie wykonalne;-)
> > >
> > > pzdr
> > > bartekltg
> >
> > Chodziło o to, że teoretycznie można. Teoretycznie każdy
> > deterministyczny ciąg da się mocno skompresować. W praktyce
> > jest to niewykonalne, ponieważ trzaby sprawdzać kolejno
> > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > ciąg ma małą złożoność kołmogorowa.
>
> jest znacznie gorzej,
> tu się okazuje, że nawet teoretycznie nie można ;-)
>
> https://en.wikipedia.org/wiki/Kolmogorov_complexity#
Uncomputability_of_Kolmogorov_complexity
>
> " there is no program which takes a string s as input and produces
> the integer K(s) as output."
>
> Polecam dowod, bardzo ładny.

Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze
zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
który zarówno jedno i drugie zadanie rozwiąże.

Pozdrawiam

do góry

On Sunday, September 25, 2016 at 8:25:34 PM UTC+2, M.M. wrote:
> On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> > On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > > >
> > > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > > przejdzie.
> > > > >
> > > >
> > > >
> > > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów
> > > > nie jest to technicznie wykonalne;-)
> > > >
> > > > pzdr
> > > > bartekltg
> > >
> > > Chodziło o to, że teoretycznie można. Teoretycznie każdy
> > > deterministyczny ciąg da się mocno skompresować. W praktyce
> > > jest to niewykonalne, ponieważ trzaby sprawdzać kolejno
> > > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > > ciąg ma małą złożoność kołmogorowa.
> >
> > jest znacznie gorzej,
> > tu się okazuje, że nawet teoretycznie nie można ;-)
> >
> > https://en.wikipedia.org/wiki/Kolmogorov_complexity#
Uncomputability_of_Kolmogorov_complexity
> >
> > " there is no program which takes a string s as input and produces
> > the integer K(s) as output."
> >
> > Polecam dowod, bardzo ładny.
>
> Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze
> zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> który zarówno jedno i drugie zadanie rozwiąże.


Hmmm. Pewien jesteś?
Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>

Jakbym jednak ja się mylił, podrzuć mi ten algorytm rozwiązujący problem
stopu na komputerze.

Bo ja bym sobie odpalił go na prostym programie:


for (bigint n=1;;n+=2){
bigint aku=0;
for (d=n-1;d>0;d--)
if (n%d==0) aku+=d;
if (aku==n) return n;
}

Bardzo bym chciał wiedzieć, czy ten programik się zatrzyma,
a skoro jest to wykonalne... ;-)

Zerknąłem jeszzce do dowodu na problem stopu. tam też nic
o modelu obliczeniowym nie ma. Żadnych turigów (którym zresztą
komputer jest) i podobnych pierdół.

pzdr
bartekltg

do góry

On Sunday, September 25, 2016 at 8:48:17 PM UTC+2, bartekltg wrote:
> On Sunday, September 25, 2016 at 8:25:34 PM UTC+2, M.M. wrote:
> > On Sunday, September 25, 2016 at 7:15:06 PM UTC+2, bartekltg wrote:
> > > On Saturday, September 24, 2016 at 3:06:29 AM UTC+2, M.M. wrote:
> > > > On Friday, September 23, 2016 at 7:47:37 PM UTC+2, bartekltg wrote:
> > > > > On Friday, September 23, 2016 at 12:19:59 PM UTC+2, M.M. wrote:
> > > > >
> > > > > > Jest jeden test, którego żaden deterministyczny generator nie
> > > > > > przejdzie.
> > > > > >
> > > > >
> > > > >
> > > > > Jaki? Tylko nie mów "wykrycie okresu", bo dla wielu generatorów
> > > > > nie jest to technicznie wykonalne;-)
> > > > >
> > > > > pzdr
> > > > > bartekltg
> > > >
> > > > Chodziło o to, że teoretycznie można. Teoretycznie każdy
> > > > deterministyczny ciąg da się mocno skompresować. W praktyce
> > > > jest to niewykonalne, ponieważ trzaby sprawdzać kolejno
> > > > wszystkie metody kompresji. Niemniej każdy deterministyczny
> > > > ciąg ma małą złożoność kołmogorowa.
> > >
> > > jest znacznie gorzej,
> > > tu się okazuje, że nawet teoretycznie nie można ;-)
> > >
> > > https://en.wikipedia.org/wiki/Kolmogorov_complexity#
Uncomputability_of_Kolmogorov_complexity
> > >
> > > " there is no program which takes a string s as input and produces
> > > the integer K(s) as output."
> > >
> > > Polecam dowod, bardzo ładny.
> >
> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze
> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> > który zarówno jedno i drugie zadanie rozwiąże.
>
>
> Hmmm. Pewien jesteś?
> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
>
> Jakbym jednak ja się mylił, podrzuć mi ten algorytm rozwiązujący problem
> stopu na komputerze.
>
> Bo ja bym sobie odpalił go na prostym programie:
>
>
> for (bigint n=1;;n+=2){
> bigint aku=0;
> for (d=n-1;d>0;d--)
> if (n%d==0) aku+=d;
> if (aku==n) return n;
> }
>
> Bardzo bym chciał wiedzieć, czy ten programik się zatrzyma,
> a skoro jest to wykonalne... ;-)
>
> Zerknąłem jeszzce do dowodu na problem stopu. tam też nic
> o modelu obliczeniowym nie ma. Żadnych turigów (którym zresztą
> komputer jest) i podobnych pierdół.
>
> pzdr
> bartekltg

Była rozmowa może z 10 lat temu w której podałem algorytm, myślałem że
też śledziłeś, widocznie coś pomyliłem.

Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem
pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci.
Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza. Ludzie
mają już wyryty kanion obok synapsy którą przepływa słowo 'nieobliczalność'.
A tym czasem problem stopu na komputerze jest całkowicie rozstrzygalny i
to banalnie prostym algorytmem, który przyśnił mi się po godzinie
zastanawiania, nie musiałem nawet sięgać do żadnych mądrych książek. MT
powoduje, że ludzie nie chcą się zastanowić nad prostym zadaniem, tylko
ślepo wierzą że nie można - nie lubię MT.

Do rzeczy. Bierzemy jeden komputer. Osadzamy w jego pamięci dowolny
program, np. implementację tego algorytmu który w poście wyżej
podałeś. Na drugim komputerze monitorujemy wykonanie programu w
pierwszym komputerze. Monitorowanie polega na zrzucaniu wszystkich
stanów pierwszego komputera do pamięci komputera drugiego. Innymi
słowy w komputerze drugim zapamiętujemy wszystkie stany jakie
kolejno pojawiają się w komputerze pierwszym. Jeśli program osiągnął
stop, to wiadomo, kończy się. Jeśli jakikolwiek stan się powtórzył, to
będzie się pętlił teoretycznie w nieskończoność, w praktyce do
uszkodzenia/wyłączenia komputera.

Pozdrawiam

do góry

On 2016-09-25, M.M. <m...@g...com> wrote:
[...]
>> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze
>> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
>> > który zarówno jedno i drugie zadanie rozwiąże.
>>
>>
>> Hmmm. Pewien jesteś?
>> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
>> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
[...]
> Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
> nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem
> pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
> możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci.
> Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza.

W swoim rozumowaniu mieszasz ze sobą wiele rzeczy.

Po pierwsze, twój algorytm, co to przyśnił ci się po godzinie
zastanawiania, to coś, co jest niewykonalne na gruncie fizyki
(potrzebuje więcej bitów pamięci niż wszechświat ma atomów), a operuje
na danych, które fizycznie wykonalne już są. Mieszanie rzeczy
praktycznie wykonalnych i teoretycznie wykonalnych (ale potrzebujących
zasobów nie do zdobycia na gruncie fizyki) daje de facto bezużyteczne
wyniki. Albo się trzymamy praktycznej wykonalności, albo mówimy
o granicach teoretycznych (pewnym wyjątkiem jest tu kryptografia, ale to
inna para kaloszy).

Po drugie, model obliczeń nie ma tu nic do rzeczy. Może być sobie
maszyną Turinga, maszyną RAM, maszyną Lispową albo nietypowanym
wyrażeniem lambda; nierozstrzygalność zostaje dokładnie tym samym.
Natomiast nijak nie wiem, co _ty_ rozumiesz przez "model obliczeń",
skoro "zmieniasz" go zostając przy tym samym.

A twoje rozumowanie jako dowód na "da się" jest jeszcze bardziej
bezużyteczne, bo trywialnym jest uzyskać znacznie mocniejsze
twierdzenie: zbiór programów, które się zakończą i które mieszczą się
w fizycznie wykonalnym komputerze, jest _językiem regularnym_, więc
wystarczy automat skończony i nie potrzeba maszyny Turinga. Jest tylko
jeden szkopuł: liczba stanów tego automatu będzie większa niż
astronomiczna.

--
Secunia non olet.
Stanislaw Klekot

do góry

On Sunday, September 25, 2016 at 11:03:28 PM UTC+2, Stachu 'Dozzie' K. wrote:
> On 2016-09-25, M.M. <m...@g...com> wrote:
> [...]
> >> > Kwestia modelu obliczeń. To tak jak z problemem stopu, na komputerze
> >> > zarówno jeden i drugi problem jest obliczalny. Można podać algorytm
> >> > który zarówno jedno i drugie zadanie rozwiąże.
> >>
> >>
> >> Hmmm. Pewien jesteś?
> >> Bo mi to wygląda na bzdury, i to z gatunku, za które A.L. wyrzucał za drzwi;>
> >> Zwłaszcza, że w linkoanym dowodzie nie ma nic o modelu obliczeń;>
> [...]
> > Generalnie osobiście nie lubię MT jako modelu obliczeń. MT ma
> > nieskończoną pamięć, komputery - nie. Jest to na tyle mylące, że potem
> > pewne problemy uważa się za niemożliwe do wykonania, a tymczasem one są
> > możliwe, tylko wymagają koszmarnego nakładu obliczeń i/albo pamięci.
> > Niemniej różnica pomiędzy możliwe a niemożliwe jest zasadnicza.
>
> W swoim rozumowaniu mieszasz ze sobą wiele rzeczy.
>
> Po pierwsze, twój algorytm, co to przyśnił ci się po godzinie
> zastanawiania, to coś, co jest niewykonalne na gruncie fizyki
> (potrzebuje więcej bitów pamięci niż wszechświat ma atomów), a operuje
> na danych, które fizycznie wykonalne już są. Mieszanie rzeczy
> praktycznie wykonalnych i teoretycznie wykonalnych (ale potrzebujących
> zasobów nie do zdobycia na gruncie fizyki) daje de facto bezużyteczne
> wyniki. Albo się trzymamy praktycznej wykonalności, albo mówimy
> o granicach teoretycznych (pewnym wyjątkiem jest tu kryptografia, ale to
> inna para kaloszy).
Wydaje Ci się że coś mieszam. To tak samo jakbyś napisał, że lepiej
nie robić projektu collatz, bo fizyka na to nie pozawala. Super-komputery
są coraz mocniejsze. Coraz więcej problemów dla coraz większych zbiorów
danych można na super komputerach sprawdzać. Fizyka z roku na rok
przeszkadza coraz mniej. Gdy uda się zbudować komputer 10^20 razy
szybszy, to też powiesz żeby lepiej nie sprawdzać, bo problem stopu
przeszkadza? Niektóre problemy, właśnie dla ważnych danych z praktycznego
punktu widzenia, można sprawdzać. Często dla dużych wartości danych
da się przeprowadzić dowód teoretyczny, a dla małych potrzebne są
szybkie komputery - jedna metoda właśnie z drugą współgra.



> Po drugie, model obliczeń nie ma tu nic do rzeczy. Może być sobie
> maszyną Turinga, maszyną RAM, maszyną Lispową albo nietypowanym
> wyrażeniem lambda; nierozstrzygalność zostaje dokładnie tym samym.
> Natomiast nijak nie wiem, co _ty_ rozumiesz przez "model obliczeń",
> skoro "zmieniasz" go zostając przy tym samym.
Maszyna turinga może przyjąć nieskończoną ilość stanów. Komputer
póki co ma ich ilość skończoną. Dlaczego uważasz ze to żadna różnica?



> A twoje rozumowanie jako dowód na "da się" jest jeszcze bardziej
> bezużyteczne, bo trywialnym jest uzyskać znacznie mocniejsze
> twierdzenie: zbiór programów, które się zakończą i które mieszczą się
> w fizycznie wykonalnym komputerze, jest _językiem regularnym_, więc
> wystarczy automat skończony i nie potrzeba maszyny Turinga. Jest tylko
> jeden szkopuł: liczba stanów tego automatu będzie większa niż
> astronomiczna.
A jeden akapit wyżej pisałeś, że obojętne jest czy się weźmie MT czy
komputer. Nie wiem co chcesz właściwie powiedzieć. Nic co powiedziałem
nie jest bezużyteczne. W mniejszych problemach od dawna się to stosuje w
praktyce i nikt nie marudzi że się nie uda bo problem stopu.


Nie wiem gdzie Ty widzisz mieszanie. Na MT problem stopu przeszkadza nawet
teoretycznie. Na komputerze problem stopu przeszkadza z powodów technicznych.
Proste, jasne, łatwe do udowodnienia stwierdzenie - nie wiem co naprawdę
chcesz powiedzieć, chyba doszukałeś się czegoś w moich slowach, czego nie
powiedziałem.


Pozdrawiam

do góry