eGospodarka.pl
bezpłatny program PIT 2019

eGospodarka.plGrupypl.comp.programmingJak najszybciej obliczyć wieloskładnikową sumę potęg? › Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
  • X-Received: by 2002:ac8:2af4:: with SMTP id c49mr3346468qta.367.1581440558728; Tue,
    11 Feb 2020 09:02:38 -0800 (PST)
    X-Received: by 2002:ac8:2af4:: with SMTP id c49mr3346468qta.367.1581440558728; Tue,
    11 Feb 2020 09:02:38 -0800 (PST)
    Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erj
    e.net!feeder.erje.net!news.albasani.net!weretis.net!feeder7.news.weretis.net!ne
    ws.uzoreto.com!feeder1.cambriumusenet.nl!feed.tweak.nl!209.85.160.216.MISMATCH!
    news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegro
    ups.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Tue, 11 Feb 2020 09:02:38 -0800 (PST)
    In-Reply-To: <e...@g...com>
    Complaints-To: g...@g...com
    Injection-Info: google-groups.googlegroups.com; posting-host=77.254.43.15;
    posting-account=xjvq9QoAAAATMPC2X3btlHd_LkaJo_rj
    NNTP-Posting-Host: 77.254.43.15
    References: <e...@g...com>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <5...@g...com>
    Subject: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    From: "M.M." <m...@g...com>
    Injection-Date: Tue, 11 Feb 2020 17:02:38 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    Xref: news-archive.icm.edu.pl pl.comp.programming:214748
    [ ukryj nagłówki ]

    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

Podziel się

Poleć ten post znajomemu poleć

Wydrukuj ten post drukuj


Następne wpisy z tego wątku

Najnowsze wątki z tej grupy


Najnowsze wątki
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: