-
X-Received: by 2002:ac8:2af4:: with SMTP id c49mr1184479qta.367.1581404493706; Mon,
10 Feb 2020 23:01:33 -0800 (PST)
X-Received: by 2002:ac8:2af4:: with SMTP id c49mr1184479qta.367.1581404493706; Mon,
10 Feb 2020 23:01:33 -0800 (PST)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!wsisiz.edu.pl!goblin1!goblin.stu.neva.r
u!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googleg
roups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Mon, 10 Feb 2020 23:01:33 -0800 (PST)
In-Reply-To: <e...@g...com>
Complaints-To: g...@g...com
Injection-Info: google-groups.googlegroups.com; posting-host=131.228.32.166;
posting-account=VFwkXwoAAADdT4-lLKRZrMYkTjizGoyn
NNTP-Posting-Host: 131.228.32.166
References: <e...@g...com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8...@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 07:01:33 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:214746
[ 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?
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.
Następne wpisy z tego wątku
- 11.02.20 10:04 g...@g...com
- 11.02.20 18:02 M.M.
- 11.02.20 20:19 osobliwy nick
- 11.02.20 21:21 Wojciech Muła
- 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-04-19 Uziom
- 2024-04-18 Prokurator Wrzosek jest już w porządku [Bodnatura po-praworządności]
- 2024-04-18 Warszawa => Sprzedawca usług rekrutacyjnych <=
- 2024-04-18 Jak uszkodzona sonda lambda wpływa na dawkowanie paliwa?
- 2024-04-18 Warszawa => Spedytor międzynarodowy <=
- 2024-04-18 Warszawa => International freight forwarder <=
- 2024-04-18 Warszawa => Regular Data Analytics/SQL Specialist <=
- 2024-04-18 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2024-04-18 (U)EFI - ksiązka, dokument
- 2024-04-18 Wrocław => Dyrektor Handlowy (branża usług/produktów IT) <=
- 2024-04-18 (Ponownie) odkryto, że ładowanie pulsacyjne robi dobrze
- 2024-04-18 Warszawa => Inżynier DevOps (Kubernetes, AWS) <=
- 2024-04-18 Wrocław => Key Account Manager <=
- 2024-04-18 Kraków => Mid PHP Developer (Laravel) <=
- 2024-04-18 Miejsce na kopertę