🚀 go-pugleaf

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.