eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingJak najszybciej obliczyć wieloskładnikową sumę potęg? › Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
  • X-Received: by 2002:a37:488f:: with SMTP id v137mr7602023qka.16.1581452501567; Tue,
    11 Feb 2020 12:21:41 -0800 (PST)
    X-Received: by 2002:a37:488f:: with SMTP id v137mr7602023qka.16.1581452501567; Tue,
    11 Feb 2020 12:21:41 -0800 (PST)
    Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erj
    e.net!2.eu.feeder.erje.net!feeder.erje.net!news.uzoreto.com!aioe.org!peer03.am4
    !peer.am4.highwinds-media.com!peer02.iad!feed-me.highwinds-media.com!news.highw
    inds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-g
    roups.googlegroups.com!not-for-mail
    Newsgroups: pl.comp.programming
    Date: Tue, 11 Feb 2020 12:21:41 -0800 (PST)
    In-Reply-To: <5...@g...com>
    Complaints-To: g...@g...com
    Injection-Info: google-groups.googlegroups.com; posting-host=217.97.69.9;
    posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
    NNTP-Posting-Host: 217.97.69.9
    References: <e...@g...com>
    <5...@g...com>
    User-Agent: G2/1.0
    MIME-Version: 1.0
    Message-ID: <6...@g...com>
    Subject: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
    From: Wojciech Muła <w...@g...com>
    Injection-Date: Tue, 11 Feb 2020 20:21:41 +0000
    Content-Type: text/plain; charset="UTF-8"
    Content-Transfer-Encoding: quoted-printable
    X-Received-Bytes: 3327
    X-Received-Body-CRC: 1209154207
    Xref: news-archive.icm.edu.pl pl.comp.programming:214750
    [ ukryj nagłówki ]

    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.

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

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: