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