eGospodarka.pl
bezpłatny program PIT 2019

eGospodarka.plGrupypl.comp.programming › Jak najszybciej obliczyć wieloskładnikową sumę potęg?
Ilość wypowiedzi w tym wątku: 8

  • 1. Data: 2020-02-07 13:48:30
    Temat: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: osobliwy nick <o...@g...com>

    Mam do wykonania pewną procedurę i zastanawiam się jak skonstruować algorytm, który
    wykonałby to najszybciej. Weźmy pewną liczbę zapisaną binarnie. Docelowo mają to być
    liczby 128-bitowe, ale w tym przykładzie weźmy liczbę 1011011 = 64+32*0+16+8+4*0+2+1.
    Interesują nas tylko bity, które mają wartość niezerową: 64+16+8+2+1. Dla tych bitów
    musimy policzyć następujące współczynniki:

    x1=64/2^(y-1) * 1
    x2=16/2^(y-1) * 2
    x3=8/2^(y-1) * 3
    x4=2/2^(y-1) * 4
    x5=1/2^(y-1) * 8

    Współczynników będzie tyle samo, co jedynek w zapisie binarnym naszej liczby. y to
    liczba jedynek w zapisie binarnym naszej liczby, w naszym przykładzie wynosi 5. Gdy
    mamy te współczynniki:

    x1=4
    x2=2
    x3=2
    x4=1
    x5=1

    Obliczamy liczbę:

    L = (a^0*x1+a^1*x2+a^2*x3+a^3*x4+a^4*x5)*2^(y-1)

    "a" może by równe jakiejś liczbie całkowitej podzielonej przez 2, na przykład: 0.5,
    1.5, 2.5, -3.5 itd. Zastanawiam się jak to najszybciej wykonać. Jeśli liczba ma mieć
    wiele bitów np. 128, to ostatnia potęga również wynosić aż 127. Stąd niezbędny jest
    algorytm szybkiego potęgowania. Jednak nawet wówczas może zajść potrzeba wykonania aż
    128 potęgowań.

    Czy da się te potęgowania wykonać jakoś symultanicznie? Algorytm nie musi czekać na
    obliczenie np. a^10, żeby móc zacząć liczyć a^11. Mógłby liczyć wszystkie potęgi na
    raz. Liczenie tego po kolei zajmie t1+t2+t3+...tn czasu, gdzie "ti" to czasy
    potęgowania kolejnych a^i. A gdyby algorytm liczył symultanicznie, to zajmie mu to co
    najwyżej tyle czasu ile potrzebuje dla najwyższej, ostatniej potęgi. Czy coś takiego
    jest możliwe? Ma to jakąś nazwę w branży?


  • 2. Data: 2020-02-07 13:52:04
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: osobliwy nick <o...@g...com>

    Pomyliłem się w zapisie tych współczynników, tak ma to wyglądać:

    x1=64/2^(y-1) * 1
    x2=16/2^(y-1) * 2
    x3=8/2^(y-1) * 4
    x4=2/2^(y-1) * 8
    x5=1/2^(y-1) * 16

    Ale nie zmienia sensu posta.


  • 3. Data: 2020-02-11 08:01:33
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: Wojciech Muła <w...@g...com>

    On Friday, February 7, 2020 at 1:48:31 PM UTC+1, osobliwy nick wrote:
    > Mam do wykonania pewną procedurę i zastanawiam się jak skonstruować algorytm, który
    wykonałby to najszybciej. Weźmy pewną liczbę zapisaną binarnie. Docelowo mają to być
    liczby 128-bitowe, ale w tym przykładzie weźmy liczbę 1011011 = 64+32*0+16+8+4*0+2+1.
    Interesują nas tylko bity, które mają wartość niezerową: 64+16+8+2+1. Dla tych bitów
    musimy policzyć następujące współczynniki:
    >
    > x1=64/2^(y-1) * 1
    > x2=16/2^(y-1) * 2
    > x3=8/2^(y-1) * 3
    > x4=2/2^(y-1) * 4
    > x5=1/2^(y-1) * 8
    >
    > Współczynników będzie tyle samo, co jedynek w zapisie binarnym naszej liczby. y to
    liczba jedynek w zapisie binarnym naszej liczby, w naszym przykładzie wynosi 5. Gdy
    mamy te współczynniki:
    >
    > x1=4
    > x2=2
    > x3=2
    > x4=1
    > x5=1
    >
    > Obliczamy liczbę:
    >
    > L = (a^0*x1+a^1*x2+a^2*x3+a^3*x4+a^4*x5)*2^(y-1)
    >
    > "a" może by równe jakiejś liczbie całkowitej podzielonej przez 2, na przykład: 0.5,
    1.5, 2.5, -3.5 itd. Zastanawiam się jak to najszybciej wykonać. Jeśli liczba ma mieć
    wiele bitów np. 128, to ostatnia potęga również wynosić aż 127. Stąd niezbędny jest
    algorytm szybkiego potęgowania. Jednak nawet wówczas może zajść potrzeba wykonania aż
    128 potęgowań.
    >
    > Czy da się te potęgowania wykonać jakoś symultanicznie? Algorytm nie musi czekać na
    obliczenie np. a^10, żeby móc zacząć liczyć a^11. Mógłby liczyć wszystkie potęgi na
    raz. Liczenie tego po kolei zajmie t1+t2+t3+...tn czasu, gdzie "ti" to czasy
    potęgowania kolejnych a^i. A gdyby algorytm liczył symultanicznie, to zajmie mu to co
    najwyżej tyle czasu ile potrzebuje dla najwyższej, ostatniej potęgi. Czy coś takiego
    jest możliwe? Ma to jakąś nazwę w branży?

    Policzenie całkowitej potęgi x^128 wymaga tylko log_2(128) = 7 mnożeń:

    x = wejście
    x2 = x*x // x^2
    x4 = x2*x2 // x^4
    x8 = x4*x4 // x^8
    x16 = x8*x8 // x^16
    x32 = x16*x16 // x^32
    x64 = x32*x32 // x^64
    x128 = x64*x64 // x^128

    Jak już masz te czynniki policzone, to łatwo z nich dostać dowolne potęgi.
    Np. x^73 = x^{64 + 8 + 1} = x * x8 * x64; albo x^55 = x^{32 + 16 + 4 + 2 + 1} = x *
    x2 * x4 * x16 * x32.

    Ogólnie tu widać ładne możliwości dla SIMDów, ale najpierw spróbowałbym zobaczyć co
    zrobi porządny kompilator. :)

    w.


  • 4. Data: 2020-02-11 10:04:30
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: g...@g...com

    W dniu wtorek, 11 lutego 2020 08:01:34 UTC+1 użytkownik Wojciech Muła napisał:
    > On Friday, February 7, 2020 at 1:48:31 PM UTC+1, osobliwy nick wrote:
    > > Mam do wykonania pewną procedurę i zastanawiam się jak skonstruować algorytm,
    który wykonałby to najszybciej. Weźmy pewną liczbę zapisaną binarnie. Docelowo mają
    to być liczby 128-bitowe, ale w tym przykładzie weźmy liczbę 1011011 =
    64+32*0+16+8+4*0+2+1. Interesują nas tylko bity, które mają wartość niezerową:
    64+16+8+2+1. Dla tych bitów musimy policzyć następujące współczynniki:
    > >
    > > x1=64/2^(y-1) * 1
    > > x2=16/2^(y-1) * 2
    > > x3=8/2^(y-1) * 3
    > > x4=2/2^(y-1) * 4
    > > x5=1/2^(y-1) * 8
    > >
    > > Współczynników będzie tyle samo, co jedynek w zapisie binarnym naszej liczby. y
    to liczba jedynek w zapisie binarnym naszej liczby, w naszym przykładzie wynosi 5.
    Gdy mamy te współczynniki:
    > >
    > > x1=4
    > > x2=2
    > > x3=2
    > > x4=1
    > > x5=1
    > >
    > > Obliczamy liczbę:
    > >
    > > L = (a^0*x1+a^1*x2+a^2*x3+a^3*x4+a^4*x5)*2^(y-1)
    > >
    > > "a" może by równe jakiejś liczbie całkowitej podzielonej przez 2, na przykład:
    0.5, 1.5, 2.5, -3.5 itd. Zastanawiam się jak to najszybciej wykonać. Jeśli liczba ma
    mieć wiele bitów np. 128, to ostatnia potęga również wynosić aż 127. Stąd niezbędny
    jest algorytm szybkiego potęgowania. Jednak nawet wówczas może zajść potrzeba
    wykonania aż 128 potęgowań.
    > >
    > > Czy da się te potęgowania wykonać jakoś symultanicznie? Algorytm nie musi czekać
    na obliczenie np. a^10, żeby móc zacząć liczyć a^11. Mógłby liczyć wszystkie potęgi
    na raz. Liczenie tego po kolei zajmie t1+t2+t3+...tn czasu, gdzie "ti" to czasy
    potęgowania kolejnych a^i. A gdyby algorytm liczył symultanicznie, to zajmie mu to co
    najwyżej tyle czasu ile potrzebuje dla najwyższej, ostatniej potęgi. Czy coś takiego
    jest możliwe? Ma to jakąś nazwę w branży?
    >
    > Policzenie całkowitej potęgi x^128 wymaga tylko log_2(128) = 7 mnożeń:
    >
    > x = wejście
    > x2 = x*x // x^2
    > x4 = x2*x2 // x^4
    > x8 = x4*x4 // x^8
    > x16 = x8*x8 // x^16
    > x32 = x16*x16 // x^32
    > x64 = x32*x32 // x^64
    > x128 = x64*x64 // x^128
    >
    > Jak już masz te czynniki policzone, to łatwo z nich dostać dowolne potęgi.
    > Np. x^73 = x^{64 + 8 + 1} = x * x8 * x64; albo x^55 = x^{32 + 16 + 4 + 2 + 1} = x *
    x2 * x4 * x16 * x32.
    >

    Nawet ten właśnie przykład jest jednym z przykładów dydaktycznych w najlepszej
    książce programistycznej ewer:

    https://mitpress.mit.edu/sites/default/files/sicp/fu
    ll-text/book/book-Z-H-11.html#%_sec_1.2.4


  • 5. Data: 2020-02-11 18:02:38
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: "M.M." <m...@g...com>

    On Friday, February 7, 2020 at 1:48:31 PM UTC+1, osobliwy nick wrote:
    > Mam do wykonania pewną procedurę i zastanawiam się jak skonstruować algorytm, który
    wykonałby to najszybciej. Weźmy pewną liczbę zapisaną binarnie. Docelowo mają to być
    liczby 128-bitowe, ale w tym przykładzie weźmy liczbę 1011011 = 64+32*0+16+8+4*0+2+1.
    Interesują nas tylko bity, które mają wartość niezerową: 64+16+8+2+1. Dla tych bitów
    musimy policzyć następujące współczynniki:
    >
    > x1=64/2^(y-1) * 1
    > x2=16/2^(y-1) * 2
    > x3=8/2^(y-1) * 3
    > x4=2/2^(y-1) * 4
    > x5=1/2^(y-1) * 8
    >
    > Współczynników będzie tyle samo, co jedynek w zapisie binarnym naszej liczby. y to
    liczba jedynek w zapisie binarnym naszej liczby, w naszym przykładzie wynosi 5. Gdy
    mamy te współczynniki:
    >
    > x1=4
    > x2=2
    > x3=2
    > x4=1
    > x5=1
    >
    > Obliczamy liczbę:
    >
    > L = (a^0*x1+a^1*x2+a^2*x3+a^3*x4+a^4*x5)*2^(y-1)
    >
    > "a" może by równe jakiejś liczbie całkowitej podzielonej przez 2, na przykład: 0.5,
    1.5, 2.5, -3.5 itd. Zastanawiam się jak to najszybciej wykonać. Jeśli liczba ma mieć
    wiele bitów np. 128, to ostatnia potęga również wynosić aż 127. Stąd niezbędny jest
    algorytm szybkiego potęgowania. Jednak nawet wówczas może zajść potrzeba wykonania aż
    128 potęgowań.
    >
    > Czy da się te potęgowania wykonać jakoś symultanicznie? Algorytm nie musi czekać na
    obliczenie np. a^10, żeby móc zacząć liczyć a^11. Mógłby liczyć wszystkie potęgi na
    raz. Liczenie tego po kolei zajmie t1+t2+t3+...tn czasu, gdzie "ti" to czasy
    potęgowania kolejnych a^i. A gdyby algorytm liczył symultanicznie, to zajmie mu to co
    najwyżej tyle czasu ile potrzebuje dla najwyższej, ostatniej potęgi. Czy coś takiego
    jest możliwe? Ma to jakąś nazwę w branży?

    Dużo zależy od:
    1) jaka jest dziedzina (typ) liczb?
    2) jakie wartości są znane w czasie kompilacji?
    3) jakie wartości są znane dopiero w czasie wykonania?
    4) jaki jest rozkład prawdopodobieństwa wartości?
    5) jaka jest wymagana dokładność obliczeń?
    6) Jaki jest czasu wykonania poszczególnych instrukcji na Twoim sprzęcie?
    7) Jaki jest czas dostępu do danych w porównaniu do czasu wykonania instrukcji?

    Trzeba popróbować...

    Jeśli wartości jest mało, dokładność duża nie jest wymagana, to może
    bufor w ram z gotowymi wartościami.

    return buff[ hash( (int)(a*2) , x1 , ... , x5 ) % buff_size ] * (1<<(y-1));

    Czy się opłaci zależy do odpowiedzi na punkt 6, 7 i od tego, czy uda się
    dla Twoich statystycznych danych napisać funkcję hash.

    A może schemat Hornera?

    (w przykładzie obciąłem do x4, dla większych potęg zysk jest większy)
    a^0*x1 + a^1*x2 + a^2*x3 + a^3*x4 = //4 mnożenia, 3 dodawania, 4 potęgowania
    x1 + a*x2 + a*a*x3 + a*a*a*x4 = //6 mnożeń 3 dodawania
    x1 + a*(x2+a*x3+a*a*x4) = //4 mnożenia 3 dodawania
    x1 + a*(x2 + a*(x3+a*x4) = //3 mnożenia 3 dodawania

    Pozdrawiam


  • 6. Data: 2020-02-11 20:19:57
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: osobliwy nick <o...@g...com>

    Ogólnie algorytm szybkiego potęgowania jest mi znany. Chodzi mi natomiast o coś
    innego. Ten algorytm trzeba wykonać dla wielu potęg, które wchodzą w skład sumy.
    Jeśli wykonamy po kolei:

    a^1
    a^2
    a^3
    ...
    a^64

    To zajmie nam to t1+t2+t3+...+t64 czasu. Niezależnie, czy użyjemy algorytmu szybkiego
    potęgowania. Natomiast ja chciałbym, aby program zaczął liczyć niezależnie w tym
    samym momencie a^1, a^2, ..., a^64. Wówczas powinno to zająć co najwyżej tyle ile
    czas potęgowania największego wykładnika. Czy coś takiego jest możliwe? Co więcej
    chciałbym, aby w międzyczasie program liczył jeszcze inne, niezależne rzeczy, które
    przydadzą się później. Wszystko po to, aby oszczędzić czas i nie wykonywać tych
    operacji po kolei, zwłaszcza, że ich wyniki są od siebie niezależne. Dopiero po ich
    uzyskaniu trzeba policzyć sumę, ale liczenie ich po kolei jest trochę stratą czasu,
    zakładając, że można uruchomić kilka procesów jednocześnie. Czy ma to sens?


  • 7. Data: 2020-02-11 21:21:41
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: Wojciech Muła <w...@g...com>

    On Tuesday, February 11, 2020 at 8:19:59 PM UTC+1, osobliwy nick wrote:
    > Ogólnie algorytm szybkiego potęgowania jest mi znany. Chodzi mi natomiast o coś
    innego. Ten algorytm trzeba wykonać dla wielu potęg, które wchodzą w skład sumy.
    Jeśli wykonamy po kolei:
    >
    > a^1
    > a^2
    > a^3
    > ...
    > a^64
    >
    > To zajmie nam to t1+t2+t3+...+t64 czasu. Niezależnie, czy użyjemy algorytmu
    szybkiego potęgowania. Natomiast ja chciałbym, aby program zaczął liczyć niezależnie
    w tym samym momencie a^1, a^2, ..., a^64. Wówczas powinno to zająć co najwyżej tyle
    ile czas potęgowania największego wykładnika. Czy coś takiego jest możliwe? Co więcej
    chciałbym, aby w międzyczasie program liczył jeszcze inne, niezależne rzeczy, które
    przydadzą się później. Wszystko po to, aby oszczędzić czas i nie wykonywać tych
    operacji po kolei, zwłaszcza, że ich wyniki są od siebie niezależne. Dopiero po ich
    uzyskaniu trzeba policzyć sumę, ale liczenie ich po kolei jest trochę stratą czasu,
    zakładając, że można uruchomić kilka procesów jednocześnie. Czy ma to sens?

    Ma sens i odpowiedź to operacje SIMD, a więc wektorowe. Możesz równocześnie liczyć
    kilka (4/8/16/32/64) niezależnych par działań matematycznych. Ale to nie jest
    trywialne.

    Dlatego zachęcam w pierwszej kolejności do sięgnięcia po proste rozwiązania. Jako
    ciekawostkę podam, że żeby policzyć dla jednej liczby 64 potęgi dla wykładników od 1
    do 64 przyzwoity kompilator C++ (czyli GCC) wygeneruje dokładnie 63 instrukcje
    mnożenia.

    w.


  • 8. Data: 2020-02-12 00:48:26
    Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    Od: osobliwy nick <o...@g...com>

    Ok, więc właśnie to chciałem wiedzieć. Ogólnie ja osobiście dopiero zamierzam robić
    podejście do Pythona w tym roku, znam totalne podstawy C, więc ja nie będę tego
    programował. Moje pytanie było bardziej w kontekście zlecenia komuś tego rodzaju
    projektu do wykonania. Mam znajomego programistę, który na przykład nie słyszał o
    tego typu podejściu i nie wie jak się do tego zabrać. Zaś, gdybym chciał to komuś
    zlecić, to muszę wiedzieć w ogóle czego chcę, jak to się nazywa i co jest możliwe, a
    co nie. Próbuję też szacować teoretyczną złożoność takiej procedury i okazuje się być
    ona zupełnie inna dla instrukcji jedna po drugiej t1+t2+...+t64 i zupełnie inna, gdy
    można wykonać wszystkie na raz.

    Pomysł wziął się stąd, że czytałem kiedyś komentarz dotyczący działania algorytmu
    szyfrującego AES, w którym ktoś stwierdził, że algorytm działa tak szybko, bo, z tego
    co zrozumiałem, można wykonywać kilka niezależnych operacji od siebie na raz, że one
    jakoś się zazębiają. Tutaj ktoś napisał pracę poświęconą AES i SIMD:

    https://ieeexplore.ieee.org/document/7393076

    Na wikipedii też wspomniano o AES w artykule o SIMD:

    https://pl.wikipedia.org/wiki/Streaming_SIMD_Extensi
    ons



strony : [ 1 ]



Szukaj w grupach

bezpłatny program PIT 2019

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: