September 14, 2012 9:00 AM
We use iterate from the Standard Prelude to calculate the tribonacci sequence:
(define (tribs n)
(iterate n + 1 1 2))
Thus, the first 25 elements of the tribonacci sequence are:
> (tribs 25)
(1 1 2 4 7 13 24 44 81 149 274 504 927 1705 3136 5768 10609
19513 35890 66012 121415 223317 410744 755476 1389537)
We use the matrix datatype from the Standard Prelude, matrix multiplication from the exercise on matrices and matrix powering from the exercise on fibonacci numbers to define this calculation of the nth tribonacci number:
(define (trib n)
(matrix-ref
(matrix-power
#( #(1 1 0)
#(1 0 1)
#(1 0 0))
n) 2 0))
Here’s an example (that’s all one big number):
> (trib 1000)
149995252232719672994127119633436824577569749158277812578756625414
806969052829656874238599632454281061578352939019541212503423640707
076075654939096072721522668597272334783989205780788704954034154039
4345570010550821354375819311674972209464069786275283520364029575324
Finally, we calculate the tribonacci constant as the ratio between two successive tribonacci numbers:
> (inexact->exact (/ (trib 1000) (trib 999)))
1.8392867552141612
You can run the program at http://programmingpraxis.codepad.org/mxq30iLw.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
A python version that uses the numpy library for matrices
import itertools as IT import numpy M = numpy.matrix([[1,1,0], [1, 0 ,1], [1, 0, 0]], dtype=float) def tribonacci(): a, b, c = 0, 0, 1 while 1: yield c a, b, c = b, c, a + b + c def tripow(N): return int((M ** N)[0,0]) print list(IT.islice(tribonacci(), 10)) #-> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149] print tripow(9) # -> 149 x = list(IT.islice(tribonacci(), 1000)) print x[-1] / float(x[-2]) # -> 1.83928675521By Paul on September 14, 2012 at 5:54 PM
Another Python version with the power of a matrix explicitly in the code.
import itertools as IT M = [[1,1,0], [1, 0 ,1], [1, 0, 0]] def vecvec(a, b): return sum(ai*bi for ai, bi in zip(a, b)) def matmul(a, b): """ number of columns in a must be equal to number of rows in b""" bt = zip(*b) return [[vecvec(ai, btj) for btj in bt] for ai in a] def mpow(a, nn): """"matrix a in the power nn Build the 1, 2, 4, 8 ... powers of a and find binary of nn Finally multiply the required powers of a """ powers = [a] binary = [] while nn: binary.append(nn & 1) nn /= 2 if nn: powers.append(matmul(powers[-1], powers[-1])) mats = (powi for powi, bi in zip(powers, binary) if bi) return reduce(lambda a, b: matmul(a, b), mats) def tribonacci(): a, b, c = 0, 0, 1 while 1: yield c a, b, c = b, c, a + b + c def tripow(N): return mpow(M, N)[0][0] print list(IT.islice(tribonacci(), 20)) #-> [1, 1, 2, 4, 7, 13, 24, 44, 81, 149] print tripow(9) # -> 149 x = list(IT.islice(tribonacci(), 1000)) print x[-1] / float(x[-2]) # -> 1.83928675521 print tripow(35) / float(tripow(34)) # -> 1.83928675521By Paul on September 14, 2012 at 9:18 PM
Calculation of the limit of the ratio as one of the roots the characteristic polynomial.
This is also the real eigenvalue of the powering matrix.
/* Maxima transcript */ (%i40) r : rhs(solve(z^3-z^2-z-1, z)[3]); sqrt(11) 19 1/3 4 1 (%o40) (-------- + --) + -------------------- + - 3/2 27 sqrt(11) 19 1/3 3 3 9 (-------- + --) 3/2 27 3 (%i41) string(optimize(r)); (%o41) block([%1],%1:(sqrt(11)/sqrt(3)^3+19/27)^(1/3),%1+4/(9*%1)+1/3) (%i42) float(r); (%o42) 1.839286755214161By Jan Van lent on September 15, 2012 at 1:04 PM
It’s been a while since I’ve used GNU Octave (Matlab clone), so I thought I’d give it a try. Not particularly clever, but it was good practice to brush up on working with matrices.
format long; function t = tribo(n) a = 0; b = 0; t = 1; for i = 2:n tmpa = a; tmpb = b; tmpt = t; a = b; b = t; t = a + b + t; endfor return; endfunction function t = tripow(n) T = [1, 1, 0; 1, 0, 1; 1, 0, 0]; t = (T^n)(1, 1); return; endfunction function l = lim(n) l = tripow(n) / tripow(n - 1); return; endfunctionBy Graham on September 15, 2012 at 3:10 PM
My implementation in Common lisp
By cage on September 15, 2012 at 4:25 PM
As I mentioned in a recent comment on the fibonacci post, it’s actually impossible to achieve O(log n) performance for arbitrarily large n. The sequence is (to a close approximation) exponential, so the lengths of the binary or decimal values increase linearly. It is thus impossible for any algorithm to run in sublinear time.
By treeowl on September 16, 2012 at 8:34 PM
Another Python solution:
def gen_tribonacci(): a, b, c = 0, 0, 1 while True: yield c a, b, c = b, c, a + b + c def nth_tribonacci(n): m = matpow([[1, 1, 0], [1, 0, 1], [1, 0, 0]], n) return m[2][0] def matpow(m, n): if n == 1: return m if n % 2: return matmult(m, matpow(matmult(m, m), n / 2)) return matpow(matmult(m, m), n / 2) def matmult(m1, m2): return [[dot(row, col) for col in zip(*m2)] for row in m1] def dot(a, b): return sum([x * y for x, y in zip(a, b)]) def tribonacci_const(n): ts = take(n, gen_tribonacci()) return float(ts[-1]) / ts[-2] def take(n, g): result = [] for _ in xrange(n): result.append(g.next()) return result if __name__ == '__main__': print(take(10, gen_tribonacci())) print(nth_tribonacci(8)) print(tribonacci_const(1000))By Catalin Cristu (@catalin_c) on September 18, 2012 at 8:03 AM
#include
using namespace std;
int main()
{
unsigned long int Counter;
unsigned long int result = 0;
unsigned long int numa, numb, numc;
numa = 0;
numb = 0;
numc = 1;
unsigned long int number;
cout << "Qual o numero que desejas conhecer da sequencia tribonacci?" << endl <> number;
cout << endl << endl;
for(Counter = 0; Counter < number – 1; Counter++)
{
result = numa + numb + numc;
numa = numb;
numb = numc;
numc = result;
}
cout << "O Valor Tribonacci do numero " << number << " e igual a: " << result;
return 0;
}
By Victor Chavauty on September 24, 2012 at 3:19 AM