-
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.
Następne wpisy z tego wątku
- 12.02.20 00:48 osobliwy nick
Najnowsze wątki z tej grupy
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
- Ada-Europe Conference - 6 March Extended Final Deadline
- Szybkie pytanko do fachowców od Bourne shella
Najnowsze wątki
- 2024-03-28 Warszawa => International freight forwarder <=
- 2024-03-28 Warszawa => Technical Tribe Leader (Java Background) <=
- 2024-03-28 Eltec nie zyje?
- 2024-03-28 Katowice => Application Engineer for Service and Deployments <=
- 2024-03-28 Wrocław => Mid PHP Developer (Laravel) <=
- 2024-03-28 Vectra 'Plan domowy bez limitu'
- 2024-03-28 Szczecin => Starszy inżynier oprogramowania (Rust) <=
- 2024-03-28 Zielona Góra => Spedytor międzynarodowy <=
- 2024-03-28 Wnuczek z Wehrmachtu idzie na rympal.
- 2024-03-28 Bażanowice => Inżynier Industrializacji - Elektronik <=
- 2024-03-28 Warszawa => Senior Account Manager <=
- 2024-03-28 Czy kompozyty (poliamid) są lepsze od stopów metali?
- 2024-03-28 nowa Skoda z potężnym silnikiem
- 2024-03-27 o Pegasusie raz jeszcze
- 2024-03-27 Gdańsk => Transport Operations Coordinator Deep Sea with Spanish or P