Article View: pl.comp.programming
Article #216806Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
From: Wojciech Muła
Date: Tue, 11 Feb 2020 20:21
Date: Tue, 11 Feb 2020 20:21
16 lines
3113 bytes
3113 bytes
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.
Technical Details
Message-ID:
<6a2ed13a-8d04-4668-804f-6a71e6ef5584@googlegroups.com>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.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.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mailReferences:
<e033f360-7c36-45f9-8399-7196d5549805@googlegroups.com> <5f0caf0d-beac-4603-b727-7365ae80329b@googlegroups.com>Show Full Headers
Complete Article Headers
X-Received: by 2002:ac8:5513:: with SMTP id j19mr4157824qtq.143.1581452501756; 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: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erje.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.highwinds-media.com!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail Newsgroups: pl.comp.programming Date: Tue, 11 Feb 2020 12:21:41 -0800 (PST) In-Reply-To: <5f0caf0d-beac-4603-b727-7365ae80329b@googlegroups.com> Complaints-To: groups-abuse@google.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: <e033f360-7c36-45f9-8399-7196d5549805@googlegroups.com> <5f0caf0d-beac-4603-b727-7365ae80329b@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <6a2ed13a-8d04-4668-804f-6a71e6ef5584@googlegroups.com> Subject: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg? From: Wojciech Muła <wojtek.mula@gmail.com> Injection-Date: Tue, 11 Feb 2020 20:21:41 +0000 X-Received-Bytes: 3327 X-Received-Body-CRC: 1209154207 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit