Obliczanie wartości n-tego elementu ciągu tribonacciego poprzez potęgowanie macierzy.

Czy da się obliczyć n-ty element w ciągu tribonacciego w podobny sposób, jak w ciągu fibonacciego? Może istnieje inny sposób, szybszy niż metoda rekurencyjna?

Pewnie jakiś wzór jest, ale taki ciąg rośnie na tyle szybko, że spokojnie możesz go prostym algorytmem liczyć dopóki wyniki mieszczą się w typie danych (oczywiście nie naiwnym, nie rób algorytmu O(ft(n)), tylko O(n)).

Dla przykładu wystarczy n=1167, żeby wynik nie mieścił się w zakresie zmiennej double. Przy takim n czas wykonania takiego algorytmu jest praktycznie natychmiastowy.

Mam do obliczenia ostatnie cztery cyfry, do tego wielu różnych elementów, więc najlepsze, co do tej pory wymyśliłem, to O(nlogn) [sortowanie danych wejściowych + jednokrotny przelot do największego elementu, po drodze zapamiętując dla mniejszych]. Chciałbym to zrobić szybciej, bo w niektórych przypadkach leci prawie 5 sekund. Przy symbolu newtona udało mi się zejść z 0.16s do 0.005 dzięki temu wzorowi z ułamkami i myślałem, że tu też coś w tym stylu istnieje.

zajrzyj tu http://mathworld.wolfram.com/TribonacciNumber.html

Znalazłem na OEIS coś takiego, ale nie potrafię tego rozszyfrować. Rozumiecie ten zapis?

(PARI) {a(n) = polcoeff( if( n<0, x / ( 1 + x + x^2 - x^3), x^2 / ( 1 - x - x^2 - x^3) ) + x*O(x^abs(n)), abs(n))} /* Michael Somos, Sep 03 2007 */

(Maxima) a(n):=sum(sum(if mod(4*k-i, 3)>0 then 0 else binomial(k, (4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1, k-1), i, k, n), k, 1, n); [From Kruchinin Vladimir, Aug 18 2010] 

W maximie:
binomial to symbol Newtona
sum(sumowane_wyrażenie,zmienna,granica_dolna,granica_górna)
np. sum(k*k,k,2,66) to

int suma=0;
for(int k=2;k<=66;k++)
    suma+=k*k;

Dzięki! Więc jeżeli zrobię potęgowanie macierzy szybkim potęgowaniem, powinienem otrzymać złożoność O(logn), prawda? To znaczne przyspieszenie względem O(n). Wieczorem zabieram się do pisania, zobaczymy, co z tego wyjdzie.

Nie napisałeś od razu, że chcesz tylko 4 ostatnie cyfy. W takim wypadku sprawa jest prostsza:

	int getFib(long n) {
		if (n < 0)
			throw new IllegalArgumentException();
		if (n >= 124000)
			n %= 124000;
		if (n == 0)
			return 0;
		else if (n == 1)
			return 1;
		else if (n == 2)
			return 1;
		int a = 1;
		int b = 1;
		int c = 2;
		for (long i = 3; i < n; i++) {
			int nc = a + b + c;
			a = b;
			b = c;
			if (nc >= 20000)
				c = nc - 20000;
			else if (nc >= 10000)
				c = nc - 10000;
			else
				c = nc;
		}
		return c;
	}

OK, dziękuję ślicznie za odpowiedzi, potęgowanie macierzy zrobię, jak będę miał trochę wolnego czasu, bo na razie męczę się z medianą multizbioru różnic wszystkich liczb w zbiorze - masakra... :)

Zrobiłem kiedyś potęgowanie macierzy + algorytm Karatsuby do mnożenia, ale dla liczb Fibonacciego, a nie Tribonacciego: http://4programmers.net/Forum/C_i_.NET/166847-VS2008_WM_fibonacci_duze_liczby?p=672490#id672490