-
Data: 2020-02-11 10:04:30
Temat: Re: Jak najszybciej obliczyć wieloskładnikową sumę potęg?
Od: g...@g...com szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]W dniu wtorek, 11 lutego 2020 08:01:34 UTC+1 użytkownik Wojciech Muła napisał:
> 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.
>
Nawet ten właśnie przykład jest jednym z przykładów dydaktycznych w najlepszej
książce programistycznej ewer:
https://mitpress.mit.edu/sites/default/files/sicp/fu
ll-text/book/book-Z-H-11.html#%_sec_1.2.4
Następne wpisy z tego wątku
- 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
- Grok zaczął nadużywać wulgaryzmów i wprost obrażać niektóre znane osoby
- Can you activate BMW 48V 10Ah Li-Ion battery, connecting to CAN-USB laptop interface ?
- We Wrocławiu ruszyła Odra 5, pierwszy w Polsce komputer kwantowy z nadprzewodzącymi kubitami
- Ada-Europe - AEiC 2025 early registration deadline imminent
- John Carmack twierdzi, że gdyby gry były optymalizowane, to wystarczyły by stare kompy
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2025
- Linuks od wer. 6.15 przestanie wspierać procesory 486 i będzie wymagać min. Pentium
- ,,Polski przemysł jest w stanie agonalnym" - podkreślił dobitnie, wskazując na brak zamówień.
- Rewolucja w debugowaniu!!! SI analizuje zrzuty pamięci systemu M$ Windows!!!
- Brednie w wiki - hasło Dehomag
- Perfidne ataki krakerów z KRLD na skrypciarzy JS i Pajton
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- Instytut IDEAS może zacząć działać: "Ma to być unikalny w europejskiej skali ośrodek badań nad sztuczną inteligencją."
- U nas propagują modę na SI, a w Chinach naukowcy SI po kolei umierają w wieku 40-50lat
Najnowsze wątki
- 2025-07-25 Warszawa => Konsultant Wiodący SAP PP <=
- 2025-07-25 Re: Brawo !!! Osy chronione w Niemczech. Za usunięcie gniazda grozi mandat
- 2025-07-25 cudzoziemiec bez biletu
- 2025-07-25 Gdynia => Sales Executive / KAM <=
- 2025-07-25 Inżynierzy z prawomocnym...
- 2025-07-25 Łódź => Mainframe (z/OS, Assembler) Developer <=
- 2025-07-25 Warszawa => Inżynier oprogramowania .Net <=
- 2025-07-25 Kraków => Senior Fullstack Engineer (Low-Code Platform) <=
- 2025-07-25 Skrobanie
- 2025-07-25 Lublin => Konsultant ds. Wdrożeń ERP (moduł FK) <=
- 2025-07-25 Warszawa => Senior Frontend Developer (React + React Native) <=
- 2025-07-25 Re: Boeing Bad Dream (Koszmar) Liner rozbity w Delhi ...
- 2025-07-24 Re: Wypadek kolejowy na stacji Wiesiółka- analiza tragicznego zdarzenia z czerwca 2001 roku.
- 2025-07-23 Re: Tysiące wypadków na niebezpiecznych przejazdach kolejowych a Polskie Linie Kolejowe nic nie robią odlat, bo kierowca pociągu nie ginie
- 2025-07-23 Re: Tysiące wypadków na niebezpiecznych przejazdach kolejowych a Polskie Linie Kolejowe nic nie robią odlat, bo kierowca pociągu nie ginie