po/eu proponuję, żeby zajęli się włażeniem w dupę europy tuska i
gronkiewicz waltz...

czy istnieje jakiś prosty algorytm wyliczana punktów na osi x, gdy
rysujemy wykres w skali logarytmicznej?

do góry

On 20.07.2014 21:06, feldmarszałek tusk wrote:

> czy istnieje jakiś prosty algorytm wyliczana punktów na osi x, gdy
> rysujemy wykres w skali logarytmicznej?

Użyć logarytmu. Jeśli rysujesz, tych punktów nie masz dużo.


Zostawiając psychiatrie, jak zrobić szybki logarytm?
Dla ułatwienia o podstawie 2.
Odpowiedź prosta, rozbić" liczbę na cechę/mantysę, choćby
funkcją frexp (x) -> (y,n) : x = y*2^n, 0.5<=y<1

teraz ~log2 = n + f(y)
gdzie y jest wielomianem lub funkcją wymierną, którą
jak dobierać, już nam Czebyszew, Remez pokazali.


O jedną rzecz trzeba zadbać. Jeśli f(0.5) i f(1)
nie różnią się o 1 (tak jak prawdziwy log2) na wykresie
całości będzie widać skoki. "Logarytm" może nawet nie
być monotoniczny. Można zadbać o to dodatkowo ręcznie,
albo zauważyć, że brzegowe węzły kontrolne w algorytmie
Remeza zbiegają do brzego obszaru. Nieparzysty stopień
aproksymacji załatwia nam problem.

Zbudujmy najpierw coś ręcznie

double shitlog2(double x)
{
int w;
x = frexp(x,&w);
return w + 2.0*(x-1.0);
}
Błąd bezwzględny niecałe 9%, wyniki dokładne dla pełnych liczb.
Błęd tylko w jedną stronę, łatwo zredukować o połowę, kosztem
'estetyki' log(1)==0 ;-)

Prosta pętla ze zmienną double i jednym wyliczeniem logarytmu jest
4.5 raza szybsza.
Nic dziwnego.

Ale idźmy dalej. Zrobiłem kilka funkcji tego typu, w tym:

double mylog2_pade_7_6(double x)
{
int w;
x = frexp(x,&w);
return w+
(-0.138283895467597308734825929 +
x* (-4.75644115041872693502244398 +
x *(-28.2901284421308848729647527 +
x *(-31.020711652270330663079404 +
x *(26.954639037773333537566195 +
x *(32.065091647893956780806165 +
(5.14481531055604261525940722 +
0.0410191440642069963727475423* x)* x))))))
/(0.01773580523008302467852483039 +
x *(1.066870914453938639820160162 +
x* (11.40739806765892909737152090 +
x* (35.97371731450040844764454601 +
x* (38.11130966747411808773004738 +
x* (12.86083151020947229832310848 + x))))));
}

Analityczny błąd (max) tego przybliżenia to 1.5*10^-18, nie dziwi
więc, że licząc na doubleach błąd krąży wokół epsylona maszynowego.

To, co interesujące, to to, że ta wersja, równie dokładna, jest 30%
szybsza!

Coś źle kompilowałem, czy logarytm jest lekko niedopieszczony?
A może mój algorytm pomija coś potrzebnego do komfortowego
uniwersalnego działania, co jest tak obciążające?
Dodanie if (x<=0) return nan(""); praktycznie nic nie zmienia.

gcc 4.8.2 z ubuntu.
Kompilowane z -march=native -mtune=native
potem jeszcze -funsafe-math-optimizations -mfpmath=sse -msse2 (bez
zmian. ) -O2, -O3, nie ma znaczenia.

W clang3.4 std::log2 jest ciut szybszy, własny 1/5 wolniejszy, ale nadal
wygrywa.

całość:
http://pastebin.com/WuYW6MTJ

BTW, jak przekazać funkcję jako argument funkcji szablonowej,
jeśli ta funkcja jest klasycznie przeładowana. log2<double>
nie działa. Wsadziłem je lambdą (sprawdziłem, bez narzutu;-)),
ale to armata na wróbla.

pzdr
bartekltg

do góry

On Tue, 22 Jul 2014 14:31:22 +0200, bartekltg <b...@g...com>
wrote:

>Zostawiając psychiatrie, jak zrobić szybki logarytm?
[..]
>(-0.138283895467597308734825929 +
> x* (-4.75644115041872693502244398 +
> x *(-28.2901284421308848729647527 +
> x *(-31.020711652270330663079404 +
> x *(26.954639037773333537566195 +
> x *(32.065091647893956780806165 +
>(5.14481531055604261525940722 +

Polecam tablice logarytmiczne. Jeszcze szybsze

A.l.

do góry

On 22.07.2014 14:36, A.L. wrote:
> On Tue, 22 Jul 2014 14:31:22 +0200, bartekltg <b...@g...com>
> wrote:
>
>> Zostawiając psychiatrie, jak zrobić szybki logarytm?
> [..]
>> (-0.138283895467597308734825929 +
>> x* (-4.75644115041872693502244398 +
>> x *(-28.2901284421308848729647527 +
>> x *(-31.020711652270330663079404 +
>> x *(26.954639037773333537566195 +
>> x *(32.065091647893956780806165 +
>> (5.14481531055604261525940722 +
>
> Polecam tablice logarytmiczne. Jeszcze szybsze

Nie są szybsze:)

Zresztą, o co Ci chodzi, przecież tak (m.in) się
implementuje funkcje.

pzdr
bartekltg

do góry

On Tue, 22 Jul 2014 15:00:55 +0200, bartekltg <b...@g...com>
wrote:

>On 22.07.2014 14:36, A.L. wrote:
>> On Tue, 22 Jul 2014 14:31:22 +0200, bartekltg <b...@g...com>
>> wrote:
>>
>>> Zostawiając psychiatrie, jak zrobić szybki logarytm?
>> [..]
>>> (-0.138283895467597308734825929 +
>>> x* (-4.75644115041872693502244398 +
>>> x *(-28.2901284421308848729647527 +
>>> x *(-31.020711652270330663079404 +
>>> x *(26.954639037773333537566195 +
>>> x *(32.065091647893956780806165 +
>>> (5.14481531055604261525940722 +
>>
>> Polecam tablice logarytmiczne. Jeszcze szybsze
>
>Nie są szybsze:)
>
>Zresztą, o co Ci chodzi, przecież tak (m.in) się
>implementuje funkcje.
>
>pzdr
>bartekltg
>

Nie przypominam sobie kiedy ostatio muisalem implementowac wlasny
logarytm...

A.L.

do góry

On 22.07.2014 15:04, A.L. wrote:
> On Tue, 22 Jul 2014 15:00:55 +0200, bartekltg <b...@g...com>
> wrote:
>
>> On 22.07.2014 14:36, A.L. wrote:
>>> On Tue, 22 Jul 2014 14:31:22 +0200, bartekltg <b...@g...com>
>>> wrote:
>>>
>>>> Zostawiając psychiatrie, jak zrobić szybki logarytm?
>>> [..]
>>>> (-0.138283895467597308734825929 +
>>>> x* (-4.75644115041872693502244398 +
>>>> x *(-28.2901284421308848729647527 +
>>>> x *(-31.020711652270330663079404 +
>>>> x *(26.954639037773333537566195 +
>>>> x *(32.065091647893956780806165 +
>>>> (5.14481531055604261525940722 +
>>>
>>> Polecam tablice logarytmiczne. Jeszcze szybsze
>>
>> Nie są szybsze:)
>>
>> Zresztą, o co Ci chodzi, przecież tak (m.in) się
>> implementuje funkcje.


> Nie przypominam sobie kiedy ostatio muisalem implementowac wlasny
> logarytm...

I co z tego wynika? Nikogo nie namawiam do implementowania (choć,
co ciekawe, można bez trudu znaleźć komercyjne i darmowe biblioteki
które to robią, najczęściej w celu pararelizacji).

Pytanie było inne.

Może rozjaśnię: Dlaczego napisany na kolanie logarytm
jest szybszy niż zaimplementowany standardowo.
Jeśli ta metoda nie ma jakiejś wyraźnej wady, ludzie
z gcc mogliby zrobić dokładnie to samo.


Zerknąłem do tego, co robi oryginalny log. Też głownie
mnoży i dodaje, ma jednak nieco więcej skoków.

pzdr
bartekltg

do góry

W dniu wtorek, 22 lipca 2014 15:58:25 UTC+2 użytkownik bartekltg napisał:
> On 22.07.2014 15:04, A.L. wrote:
>
> > On Tue, 22 Jul 2014 15:00:55 +0200, bartekltg <b...@g...com>
>
> > wrote:
>
> >
>
> >> On 22.07.2014 14:36, A.L. wrote:
>
> >>> On Tue, 22 Jul 2014 14:31:22 +0200, bartekltg <b...@g...com>
>
> >>> wrote:
>
> >>>
>
> >>>> Zostawiając psychiatrie, jak zrobić szybki logarytm?
>
> >>> [..]
>
> >>>> (-0.138283895467597308734825929 +
>
> >>>> x* (-4.75644115041872693502244398 +
>
> >>>> x *(-28.2901284421308848729647527 +
>
> >>>> x *(-31.020711652270330663079404 +
>
> >>>> x *(26.954639037773333537566195 +
>
> >>>> x *(32.065091647893956780806165 +
>
> >>>> (5.14481531055604261525940722 +
>
> >>>
>
> >>> Polecam tablice logarytmiczne. Jeszcze szybsze
>
> >>
>
> >> Nie są szybsze:)
>
> >>
>
> >> Zresztą, o co Ci chodzi, przecież tak (m.in) się
>
> >> implementuje funkcje.
>
>
>
>
>
> > Nie przypominam sobie kiedy ostatio muisalem implementowac wlasny
>
> > logarytm...
>
>
>
> I co z tego wynika? Nikogo nie namawiam do implementowania (choć,
>
> co ciekawe, można bez trudu znaleźć komercyjne i darmowe biblioteki
>
> które to robią, najczęściej w celu pararelizacji).
>
>
>
> Pytanie było inne.
>
>
>
> Może rozjaśnię: Dlaczego napisany na kolanie logarytm
>
> jest szybszy niż zaimplementowany standardowo.
>
> Jeśli ta metoda nie ma jakiejś wyraźnej wady, ludzie
>
> z gcc mogliby zrobić dokładnie to samo.
>
>
>
>
>
> Zerknąłem do tego, co robi oryginalny log. Też głownie
>
> mnoży i dodaje, ma jednak nieco więcej skoków.
>
>
powody sa lub ich nie ma.. (co do tego to moze zalezy od platformy ale te funkcje sa
znane z powolnosci i ztck to np niemal nikt nie uzywa pow() - moze poza AL'em ;/)

a jaki to jest 'oryginalny log'? jest to jakies zrodło w c w asmie czy cos takiego?
ztcw to w
x87 sa dwie funkcje

FYL2X - liczy y*lg_2(x) (jesli y=lg_b(2) => liczy lg_b(x) )

FYL2XP1 - y*lg_2(x+1) "more precise than lg_2(x) if x is close to zero" (acz tego
troche nie rozumiem - to jak sie tego uzywa?)

do góry

>
>
> a jaki to jest 'oryginalny log'? jest to jakies zrodło w c w asmie czy cos takiego?
ztcw to w
>
> x87 sa dwie funkcje
>
>
>
> FYL2X - liczy y*lg_2(x) (jesli y=lg_b(2) => liczy lg_b(x) )
>
>
>
> FYL2XP1 - y*lg_2(x+1) "more precise than lg_2(x) if x is close to zero" (acz tego
troche nie rozumiem - to jak sie tego uzywa?)

do kompletu jest jeszcze funkcja
F2XM1
wszystkie te trzy funkcje sa jakies dziwne i ograniczone np dziedzina tej ostatniej
podobno [-1.0
do 1.0] (jak w takim razie liczy sie exp()'a)
a dziedzina FYL2XP1 podobno: "-0.29289... to +0.29289..." - ciagle nie rozumiem jak
tego uzywac
do liczenia dokladniejszych logarytmow dla okolic 1.0 - ale tez nie mam troche
sily/czasu sie w to wglebiac

do góry

On 22.07.2014 16:16, firr wrote:
>>>
>>>
>>> Zerknąłem do tego, co robi oryginalny log. Też głownie
>>> mnoży i dodaje, ma jednak nieco więcej skoków.

> powody sa lub ich nie ma.. (co do tego to moze zalezy od platformy

Przestań "dresować".

> a jaki to jest 'oryginalny log'? jest to jakies zrodło w c w asmie
> czy cos takiego? ztcw to w x87 sa dwie funkcje

Napisałem o tym w ostatniej linijce posta. Kompilator nie użył
koprocesora, tylko liczy jakiś szereg używając sse,
po drodze używając paru porównań.

Wymuszenie użycia koprocesora przez -mfpmath=387 nic nie daje,
bo treść log2 się linkuje w wersji sse.

Jak bardzo chcesz źródło, to masz.
http://pastebin.com/BZpVhHGb
najpierw std, potem to co wypluł kompilator z f.wymiernej + frexp.
[bardzo ładnie sam przeplata liczenie licznika i mianownika]


> FYL2X - liczy y*lg_2(x) (jesli y=lg_b(2) => liczy lg_b(x) )
> FYL2XP1 - y*lg_2(x+1) "more precise than lg_2(x) if x is close to
> zero" (acz tego troche nie rozumiem - to jak sie tego uzywa?)

Jeśli masz liczbę postaci 1+dx to logartym (naturalny dla
uproszczenia) tegobędzie z grubsza wynosił dx. Ale precyzja
1+dx to 16 cyfr, jeśli dx jesst na poziomie 10^-10 to
dx ma tylko 6 cyfr znaczących. I tyle ma też wynik.

A logartym w tym punkcie jest przydatny. Zwłaszcza, ze
dx może być równe 10^-40 ;-)
log1p (x) = log(1+x) tyle, że gdy x jest małe, znacznie dokładniej.

pzdr
bartekltg

do góry

W dniu wtorek, 22 lipca 2014 17:23:09 UTC+2 użytkownik bartekltg napisał:
> On 22.07.2014 16:16, firr wrote:
>
> >>>
>
> >>>
>
> >>> Zerknąłem do tego, co robi oryginalny log. Też głownie
>
> >>> mnoży i dodaje, ma jednak nieco więcej skoków.
>
>
>
> > powody sa lub ich nie ma.. (co do tego to moze zalezy od platformy
>
>
>
> Przestań "dresować".
>
>
>
> > a jaki to jest 'oryginalny log'? jest to jakies zrodło w c w asmie
>
> > czy cos takiego? ztcw to w x87 sa dwie funkcje
>
>
>
> Napisałem o tym w ostatniej linijce posta. Kompilator nie użył
>
> koprocesora, tylko liczy jakiś szereg używając sse,
>
> po drodze używając paru porównań.
>
>
>
> Wymuszenie użycia koprocesora przez -mfpmath=387 nic nie daje,
>
> bo treść log2 się linkuje w wersji sse.
>
>
>
> Jak bardzo chcesz źródło, to masz.
>
> http://pastebin.com/BZpVhHGb
>
> najpierw std, potem to co wypluł kompilator z f.wymiernej + frexp.
>
> [bardzo ładnie sam przeplata liczenie licznika i mianownika]
>
>
>
>
>
> > FYL2X - liczy y*lg_2(x) (jesli y=lg_b(2) => liczy lg_b(x) )
>
> > FYL2XP1 - y*lg_2(x+1) "more precise than lg_2(x) if x is close to
>
> > zero" (acz tego troche nie rozumiem - to jak sie tego uzywa?)
>
>
>
> Jeśli masz liczbę postaci 1+dx to logartym (naturalny dla
>
> uproszczenia) tegobędzie z grubsza wynosił dx. Ale precyzja
>
> 1+dx to 16 cyfr, jeśli dx jesst na poziomie 10^-10 to
>
> dx ma tylko 6 cyfr znaczących. I tyle ma też wynik.
>
>
>
> A logartym w tym punkcie jest przydatny. Zwłaszcza, ze
>
> dx może być równe 10^-40 ;-)
>
> log1p (x) = log(1+x) tyle, że gdy x jest małe, znacznie dokładniej.
>
>
ok, ten asm troche za dlugi bym to rozczytywal
no ale ok, - i tak tego rodzaju funkcji log/exp/pow uzywa sie bardzo rzadko, dzialają
one tez baardzo wolno - lepiej jest jest je mysle stablicowac pod konkretny
przyopadek [ew ominac w jakis inny sposob] - taka stablicowana funkcja bedzie wtedy
pewnie z kilkadziesiat razy szybsza
(ostatnio sprawdzalem czy tablizowanie dzielen
daje speedup w moim rasteryzerze i byl speedup
(z 1% czy 2% w skali aplikacji ale jednak)
- czyli praktyczny wniosek w tego rodzaju funkcje wogole nie nalezy sie jak na dzis
pewnie bawic,
tablicowac i po robocie] (pewnie jeszcze nalezy sprawdzic czy w tych oryginalnych
wolnych nie ma bledów bo chyba moga one miec rozne dziwne
nieprecyzyjnosci, nie jestem pewien]

do góry