-
71. Data: 2014-08-11 11:00:03
Temat: Re: szybki logarytm
Od: "slawek" <h...@s...pl>
Użytkownik "A.L." napisał w wiadomości grup
dyskusyjnych:v9oft91vbihn361kr92asl6q7hanjg1g2t@4ax.
com...
>Przynajmniej kiedys obowiazywaly takie zwyczaje na usenecie
Idealizujesz. Spam, trolle i inne takie były "od zawsze".
-
72. Data: 2014-08-11 11:40:23
Temat: Re: szybki logarytm
Od: bartekltg <b...@g...com>
W dniu sobota, 9 sierpnia 2014 21:53:32 UTC+2 użytkownik slawek napisał:
> On Sat, 9 Aug 2014 11:13:24 -0700 (PDT), bartekltg
> > Mnożenie 100 000 razy daje na doublach błąd 27x epsylon, użycie pow=
> Jak to oszacowaleś?
A jak myślisz. Odpaliłem program z pętlą.
Dla danych, jakie podałeś.
Uwaga na optymalizacje.
Jakbym miał szacować, wyszło by mi kilka razy więcej.
pzdr
bartekltg
-
73. Data: 2014-08-11 15:36:32
Temat: Re: szybki logarytm
Od: "slawek" <h...@s...pl>
Użytkownik "bartekltg" napisał w wiadomości grup
dyskusyjnych:d41ec718-59f4-4adc-bb47-f41164f032c3@go
oglegroups.com...
> > > Mnożenie 100 000 razy daje na doublach błąd 27x epsylon
>A jak myślisz. Odpaliłem program z pętlą.
To jesteś lepszy niż Chuck (liczący od 1 do Infinity, dla pewności dwa
razy).
Bo udowodniłeś, że dla dowolnych liczb 100 000 mnożeń zawsze daje błąd
dokładnie 27*epsilon. Szacun.
A tak, nota bene, plus czy minus? Bo przecież wystarczy po tych mnożeniach
np. odjąć 27*epsilon i wynik będzie - zawsze, wszędzie i w ogóle - całkiem
dokładny!
(Z drugiej strony trochę głupio, że trzeba dodatkowych 99 999 mnożeń aby
podnieść precyzję, no ale nie ma że boli - jest Wielki Algorytm Bartka - i
od dziś możemy wykonywać wszystkie mnożenia na liczbach double z odpowiednią
korekcją. Oczywiście - gdy Bartek nam wyjawi czy ma być plus czy minus.)
A już bez robienia beki: udowodniłeś, że w szczególnym przypadku różnica
wynosi tyle a tyle; w ogólnym przypadku (a tylko ten jest interesujący)
niczego nie udowodniłeś.
To tak, jakbyś twierdził, że w Lotto wychodzą kolejne liczby, bo ostatnio
wyszło 46, 47 i 48 (serio, tyle było w sobotę). Owszem, to prawda - czasem
wychodzą - ale możliwość zastosowania tej informacji do przewidywania jakie
wyjdą w następnym losowaniu jest znikoma. Z tym że Lotto to 48 liczb od 1 do
48, a 100 000 mnożeń to 100 001 liczb i do tego double. Jako ćwiczenie
oblicz sobie ile jest różnych kombinacji w każdym z tych przypadków.
(A i drobiazg - skąd brałeś "dokładną wartość"? Wypadałoby Mathematicę
zmusić do policzenia z jakąś setką cyfr po przecinku, bo wzorek (1+x)^n = 1
+ n*x jest rzecz jasna przybliżony, a reszt chyba ci się nie chciało
liczyć.)
-
74. Data: 2014-08-11 16:10:52
Temat: Re: szybki logarytm
Od: bartekltg <b...@g...com>
W dniu poniedziałek, 11 sierpnia 2014 10:39:50 UTC+2 użytkownik slawek napisał:
> IMHO, jeżeli a[n] jest bliskie 1, np. dla każdego n = 1,2, ..., m mamy 0.99
> < a[n] < 1.01, to w pesymistycznym przypadku można spodziewać się błędu
> m*epsilon.
Nie.
Pomyśl raz jeszcze.
W każdym kroku popełniasz błąd rzędu epsylon,
ale błąd ten ma losowy znak, bo i zaokrąglenie
podczas każdego działania jest do najbliższego
reprezentanta, (można udowodnić, że obcinając
kilka początkowych cyfr liczb w ciągu geometrycznym
pozostałości mają rozkład bardzo bliski jednostajnemu).
Z tego mamy coś bardzo przypominającego realizację
błądzenia losowego. A wtedy skumulowany błąd zachowuje
się jak ~sqrt(n).
Zresztą, można znów po prostu popatrzeć na eksperyment.
https://www.dropbox.com/sh/kaau8744yye8xhs/AADt6ikWb
AQ-ZERllRQfONawa
100 000 000 kroków i dwie liczby
'oryginalna' 1.000000001;
i nieco większa 1.0000100001;
Tym razem porównywane do wartości bezpośredniego potęgowania.
Pierwsza bardzo słabo miesza, więc wzrost przewidywany
poniżej zaczyna się z opóźnieniem. Druga idealnie wg teorii.
Ciągłe linie to err = c*sqrt(N).
> Dlaczego tak? Bo przy mnożeniu "z grubsza" dodają się błędy względne, a te
Jak widzisz, nie.
> Względny błąd jest ok, ale reguła 27*epsilon po prostu nie działa.
Jaka znowu reguła. To wynik dla konkretnych liczb.
Przeczytaj poprzedni post raz jeszcze, nie jest trudny.
BTW. ogólna uwaga jest słuszna, lepiej liczyć coś szybko
niż wolno.
;-)
pzdr
bartekltg
-
75. Data: 2014-08-11 17:48:41
Temat: Re: szybki logarytm
Od: slawek <f...@f...com>
On Mon, 11 Aug 2014 07:10:52 -0700 (PDT), bartekltg
<b...@g...com> wrote:
> Z tego mamy coś bardzo przypominającego realizację
> błądzenia losowego. A wtedy skumulowany błąd zachowuje
> się jak ~sqrt(n).
Poczytaj co napisałem wcześniej, jest tam i o sqrt(m).
Ale w pesymistycznym przypadku będzie m*epsilon.