eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingszybki logarytm
Ilość wypowiedzi w tym wątku: 75

  • 41. Data: 2014-07-29 19:01:36
    Temat: Re: szybki logarytm
    Od: bartekltg <b...@g...com>

    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


  • 42. Data: 2014-07-29 19:09:19
    Temat: Re: szybki logarytm
    Od: bartekltg <b...@g...com>

    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





  • 43. Data: 2014-07-29 19:58:03
    Temat: Re: szybki logarytm
    Od: A.L. <a...@a...com>

    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.


  • 44. Data: 2014-07-29 20:04:48
    Temat: Re: szybki logarytm
    Od: A.L. <a...@a...com>

    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.


  • 45. Data: 2014-07-29 20:10:00
    Temat: Re: szybki logarytm
    Od: feldmarszałek tusk <N...@g...pl>

    pierwsza dyrektywa wspólnoty europejskiej...


  • 46. Data: 2014-07-29 20:25:30
    Temat: Re: szybki logarytm
    Od: Borneq <b...@a...hidden.pl>

    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.


  • 47. Data: 2014-07-30 16:41:21
    Temat: Re: szybki logarytm
    Od: bartekltg <b...@g...com>

    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





  • 48. Data: 2014-08-01 21:28:17
    Temat: Re: szybki logarytm
    Od: Borneq <b...@a...hidden.pl>

    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.


  • 49. Data: 2014-08-01 21:37:50
    Temat: Re: szybki logarytm
    Od: feldmarszałek tusk <N...@g...pl>

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


  • 50. Data: 2014-08-01 23:10:51
    Temat: Re: szybki logarytm
    Od: "R.e.m.e.K" <p...@w...pl>

    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

strony : 1 ... 4 . [ 5 ] . 6 ... 8


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: