układ równań iteracyjny/rekurencyjny eqr: Witajcie, Mam zadanie do zoptymalizowania, dlatego poszukuję szybkiego wyliczenia dwóch wartości: mam: − n = (1.2.3 .. 64) //liczby naturalne − C = cos(Pi/64) //stała − S = sin(Pi/64) //stała A(1) = 1; B(1) = 0; A(n) = A(n−1) * C + B(n−1) * S B(n) = B(n−1) * C + A(n−1) * S i pytanie, jak szybko wyliczyć np. A(50) i B(50), bez liczenia elementów pośrednich ?

Adamm:

A(n−1) B(n−1) B(n−1) A(n−1)	C S S C		A(n) B(n) B(n) A(n)
		=

C S S C		A(n) B(n) B(n) A(n)
	n−1 =

	C−α S S C−α
det(		) = (C−α)2−S2 = 0 ⇔ α=C+S lub α=C−S

α=C+S

−S S S −S		0 0		1 1
	N{x y} =		⇒ wektor własny

α=C−S

S S S S	x y		0 0		1 −1
		=		⇒ wektor własny

C S S C		1 1 −1 1	C−S 0 0 C+S	1/2 −1/2 1/2 1/2
	=

C S S C		1 1 −1 1	(C−S)n−1 0 0 (C+S)n−1	1/2 −1/2 1/2 1/2
	n−1 =				=

	Mn−1+Nn−1 Mn−1−Nn−1 Mn−1−Nn−1 Mn−1+Nn−1
(1/2)

gdzie M=C+S, N=C−S zatem:

	(C+S)n−1+(C−S)n−1
A(n) =
	2

	(C+S)n−1−(C−S)n−1
B(n) =
	2

Adamm: wiem że pewnie nie o to chodziło, ale myślę że zaszedł wielki postęp

eqr: Dzięki za chęci Nie do końca o to chodziło, w dodatku ja zrobiłem mały błąd, powinno być: A(n) = A(n−1) * C − B(n−1) * (− S) B(n) = A(n−1) * (− S) + B(n−1) *C A to zmienia postać rzeczy, wyliczyłem pierwsze 6 wzorów i nie wygląda to różowo... A(1) = 1 B(1) = 0 A(2) = C B(2) = S A(3) = C²−S² B(3) = −2SC A(4) = C³−3S²C B(4) = S³+3C²S A(5) = C⁴+S⁴−6S²C² B(5) = 4S³C−4C³S A(6) = C⁵+5S⁴C−10C³s² B(6) = −S⁵−5C⁴S+10S³C² Reasumując jeżeli wyliczamy to za pomocą sin/cos to każdy element następny będzie wielomianem stopnia n−1, a to przy liczeniu na kompie dla mnie daje w szczególnym przypadku wielomian stopnia 511 (w przypadku liczenia do 512)... Co mija się z celem

Adamm: właściwie, uprasza to bardzo dużo A(n) = A(n−1)C + B(n−1)S B(n) = B(n−1)C − A(n−1)S A(1) = sin(π/2) B(1) = cos(π/2) A(n−1) = sin(a_n−1) B(n−1) = cos(a_n−1) A(n) = sin(a_n+π/64) B(n) = cos(a_n+π/64) a_n = π/2+(n−1)π/64 A(n) = sin(π/2+(n−1)π/64) B(n) = cos(π/2+(n−1)π/64)

eqr: Wielkie dzięki − 100% pokrycia na wykresie, dane w 100% zgodne z tym co program generuje Teraz mogę usunąć pobieranie danych z tablicy i liczyć w każdym wątku swoją wartość −> wąskim gardłem jest dostęp do pamięci, dlatego poszukiwałem takiego rozwiązania. Problem rozwiązany

Saizou : mogłeś też (jeśli to programujesz) obliczać tylko poprzedni wyraz i potem go kasować (ew nadpisywać zmienne), bo tylko to potrzebujesz do obliczania kolejnego

eqr: Robię to na GPU, gdzie mam na jeden blok 512 wątków, a więc te 512 wątków liczy jedną linijkę tablicy 2D(1024x1024) Niestety odczyt z pamięci RAM GPU kosztuje... więc wpadłem na pomysł wyliczania tego Niestety jak każdy wątek liczy sinusa i cosinusa, to już mogę powiedzieć, że wychodzi gorzej To co sugerujesz zadziała dobrze przy jednym wątku, inaczej nie będzie to efektywne, bo wchodzimy w programowanie sekwencyjne, a nie równoległe i całe przyśpieszenie leci do kosza na GPU. Zapis do Schared na GPU też odpada, bo raz użyte dane siedzą w cache − odczyt następuje tylko jeden raz na dany Kernel i tam chciałem to przyśpieszyć, ale obliczenia sin/cos są znacznie droższe niż odczyt i tak zapchanej pamięci.

eqr: aha, już miałem to wyliczone wcześniej i z tablicowane (metoda iteracyjna z dodawaniem sin i cos), ale nadal szukałem optymalizacji i skrócenie czasu obliczeń, bo wiem że 5% wątków lata pusto bo czeka na dane, a teraz niestety ale to pamięć nie jest dociążona w 100%