On 29.07.2014 17:04, A.L. wrote:

>> Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
>> log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)

> http://stackoverflow.com/questions/11376288/fast-com
puting-of-log2-for-64-bit-integers

Ale w wątku cały czas mowa o zmiennym przecinku.

pzdr
bartekltg

do góry

On 29.07.2014 16:10, Borneq wrote:
> W dniu 2014-07-29 09:52, Borneq pisze:
>> Jak zrobić funkcję frexp? Trzeba bitowo grzebać we floacie, gdzie już
>
> To jest standardowa funkcja, ale dosyć długo liczona. Zajmuje prawie

U mnie szybko.
Kopiuje rejestr XMM do zwykłego i działą bitowo.
Musi trochę zajmować, aby poprawnie obsługiwać liczby podnormalne.

> połowę czasu liczenia logarytmów metoda Czebyszewa. A koprocesor od razu
> ma cechę i mantysę. Poza tym może zrównoleglić Hornera, tak że najpierw
> w logarytmicznym czasie wyliczy x,x^2,x^4,x^8,x^16.

Ale co to da? Chcesz wykorzystywać to, że bebechy procesora nie
będą czekać na wynik poprzedniej operacji? Na to kompilator
już sam wpadł, liczy kolejny etap hornera na zmianę dla licznika
i mianownika.

> Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
> log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)

I to wygląda na różnicę większą niż jedno przemnożenie:)

pzdr
bartekltg

do góry

On Tue, 29 Jul 2014 19:01:36 +0200, bartekltg <b...@g...com>
wrote:

>On 29.07.2014 17:04, A.L. wrote:
>
>>> Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
>>> log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)
>
>> http://stackoverflow.com/questions/11376288/fast-com
puting-of-log2-for-64-bit-integers
>
>Ale w wątku cały czas mowa o zmiennym przecinku.
>
>pzdr
>bartekltg

Nie zauwazylem

A.L.

do góry

On Tue, 29 Jul 2014 19:01:36 +0200, bartekltg <b...@g...com>
wrote:

>On 29.07.2014 17:04, A.L. wrote:
>
>>> Z przykładu widać że log2 jest znacznie szybciej wyliczany niż log czy
>>> log10, więc wiedząc to można uniknąć liczeń log(x)/log(2)
>
>> http://stackoverflow.com/questions/11376288/fast-com
puting-of-log2-for-64-bit-integers
>
>Ale w wątku cały czas mowa o zmiennym przecinku.
>
>pzdr
>bartekltg

No to moze to

http://www.icsi.berkeley.edu/pubs/speech/hardwareind
ependent08.pdf

http://www.ti.com/lit/an/spra218/spra218.pdf

Niejaki Borneq zrobil sobie z grupy swoj wlasny oddzial konslltacyjny.
Darmowy.

Moze tak, kolego Borneq, oderwac d... od stolka, pomyslec, poszukac,
pogoglowac, a jak juz naprawde nei wiadomo co, to dopiero wtedy
napisac na grupe.

Przynajmniej kiedys obowiazywaly takie zwyczaje na usenecie

A.L.

do góry

pierwsza dyrektywa wspólnoty europejskiej...

do góry

W dniu 2014-07-29 18:56, bartekltg pisze:
> wgryzę się głębiej. Na razie odpłynąłem w próbę zrozumienia,
> dlaczego funkcje wymierne dają tak znacznie lepsze wyniki
> niż wielomiany:).

O ile lepsze? Jak dużo stopień wielomianu musi być wyższy dla wielomianu
niż dla wyrażenia wymiernego?
Gdy mamy możliwość wykonania tego w sposób równoległy, to być może
opłaca się wielomian wyższego stopnia, choćby stopień był bardzo wysoki,
zamiast dzielenia.
Tylko obecnie nie ma możliwości wykonania Hornera równoległe, gdy mamy
kilka rdzeni, to zrównoleglenie polega ma wykonaniu wątków na kilku
rdzeniach, a nie można krótkiej operacji rozdzielać. Może komputery
przyszłości będą miały coś w rodzaju wbudowanego koprocesora FPGA, który
będzie mógł równolegle wykonywać operacje?
Do czego dziś mogą się przydać procedury Czebyszewa i Remeza? Może do
szybkiego obliczania funkcji, których nie obsługuje koprocesor. Na
przykład mamy rozkład normalny o wzorze e^{-x^2}
Całka tej funkcji nie da się wyrazić symbolicznie, ale e^{-x^2} można
rozwinąć w szereg Taylora, ten szereg scałkować. I otrzymać wzór do
obliczeń, a metoda Czebyszewa pozwoli na szybsze wykonanie niż szereg.

do góry

On 29.07.2014 20:25, Borneq wrote:
> W dniu 2014-07-29 18:56, bartekltg pisze:
>> wgryzę się głębiej. Na razie odpłynąłem w próbę zrozumienia,
>> dlaczego funkcje wymierne dają tak znacznie lepsze wyniki
>> niż wielomiany:).
>
> O ile lepsze? Jak dużo stopień wielomianu musi być wyższy dla wielomianu
> niż dla wyrażenia wymiernego?


W wersji z logarytmem wyniki były takie.
rząd licznika, rząd mianownika, błąd maksymalny

13 0 4.4669e-12
12 1 2.6577e-14
11 2 7.4195e-16
10 3 5.5135e-17
9 4 8.7641e-18
8 5 2.6887e-18
7 6 1.5005e-18
6 7 1.4947e-18
5 8 2.6568e-18
4 9 8.5841e-18
3 10 5.3464e-17
2 11 7.1071e-16
1 12 2.5028e-14
0 13 4.072e-12

Nie zawsze jest aż tak wyraźnie lepsza. W przypadku
logarytmu mamy bardzo niedaleko przedziału [0.5,1]
biegun, stąd miałaby pochodzić przewaga f wymiernych.

http://mathoverflow.net/questions/122539/the-unreaso
nable-effectiveness-of-pade-approximation
[tam też odnośćnik do większego pdfa]

To dalej nie jest aproksymacja w normie |.|_inf na przedziale,
tylko szereg. Coś więcej mam, ale na innym kompie, ale chyba
wiele nie dokładniejszego.


> Gdy mamy możliwość wykonania tego w sposób równoległy, to być może
> opłaca się wielomian wyższego stopnia, choćby stopień był bardzo wysoki,
> zamiast dzielenia.

W jakim sensie równolegle? Pogadać między procesorami raczej nie
zdążysz;)
Większy stopień to też najczęściej gorsze uwarunkowanie.

> Tylko obecnie nie ma możliwości wykonania Hornera równoległe, gdy mamy
> kilka rdzeni, to zrównoleglenie polega ma wykonaniu wątków na kilku
> rdzeniach, a nie można krótkiej operacji rozdzielać. Może komputery
> przyszłości będą miały coś w rodzaju wbudowanego koprocesora FPGA, który
> będzie mógł równolegle wykonywać operacje?

Wtedy to dowolny (w granicach rozsądku) wielomian policzę sobie
w czasie log_2 (n) ;-)

> Do czego dziś mogą się przydać procedury Czebyszewa i Remeza? Może do

Do tego samego, co 100 lat temu - do wyznaczania optymalnej sensie
normy max aproksymacji wielomianem danej funkcji.

A czy coś takiego jest Ci potrzebne, to już zależy od tego, co robisz.
Nie jest to coś, co każdy używa. Choć Remez wystąpił na matematyce
obliczeniowej (odpowiednik metod numerycznych na matematyce) u mnie.

pzdr
bartekltg

do góry

W dniu 2014-07-30 16:41, bartekltg pisze:
> Wtedy to dowolny (w granicach rozsądku) wielomian policzę sobie
> w czasie log_2 (n) ;-)

Policzmy:
mamy wielomian 10-tego stopnia: a_0+a_{1}x+a_{2}x^2+...a_{10}x^{10}
Schemat Hornera
((((((((((a_{10}*x)+a_9)x+a_8)x+a_7)x+a_6)x+a_5)x+a_
4)x+a_3)x+a_2)x+a_1)+a_0

Rozkład wygodny do obliczeń równoległych:
a_0+a_{1}x+x^2*(a_{2}+a_{3}x)+
x^4*(a_{4}+a_{5}x+x^2*(a_{6}+a_{7}x) )+
x^8*(a_{8}+a_{9}x+a_{10}x^2)

1. krok - mnożenie przez x
o blizenie x^2:= x*x
a_{1}x
a_{3}x
a_{5}x
a_{7}x
a_{9}x
2. krok, ale krótki, tylko dodawanie
f0 := a_0+a_{1}x
f1 := a_{2}+a_{3}x
f2 := a_{4}+a_{5}x
f3 := a_{6}+a_{7}x
f4 := a_{8}+a_{9}x
otrzymujemy:
f0+x^2*(f1)+
x^4*(f2+x^2*(f3) )+
x^8*(f4+a_{10}x^2)

3. krok mnożenie przez x^2
obliczenie x^4 := x^2*x^2
g0 := x^2*(f1)
g1 := x^2*(f3)
g2 := a_{10}x^2
otrzymujemy
f0+g0+
x^4*(f2+g1 )+
x^8*(f4+g2)

4. krok, ale krótki, tylko dodawanie
h0 := f0+g0
h1 := f2+g1
h2 := f4+g2
otrzymujemy
h0 + x^4*h1 + x^8*h2
5. krok mnożenie przez x^4
obliczenie x^8 := x^4*x^4
x^4*h1
6. dodawanie
h0 + x^4*h1
7. mnożenie x^8*h2
8. dodawanie
(h0 + x^4*h1) + x^8*h2

8 kroków w tym 4 mnożenia

Chociaż z drugiej strony mnożeni i dodawanie obecnie to tyle samo za to
dzielenie dużo więcej
dodawanie, mnożenie na int32 czy też float tylko 1 takt, dzielenie
stałoprzecinkowe 7-8 a zmiennoprzecinkowe 13 taktów.

do góry

weź nie wykładaj w moim wątku teorii strzelania z tuskowej dupy,
tylko napisz konkretnie jak wyliczyć 10^x...

do góry

Dnia Fri, 01 Aug 2014 21:37:50 +0200, feldmarszałek tusk napisał(a):

> weź nie wykładaj w moim wątku teorii strzelania z tuskowej dupy,
> tylko napisz konkretnie jak wyliczyć 10^x...

Kup sobie kalkulator jelopie :-P

--
pozdro
R.e.m.e.K

do góry