lib/github.com/athas/fibs/fibs

Generating the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, and so forth.

This file provides both parallel and sequential implementations. In practice, the sequential implementations are probably preferable in all realistic cases, as the integers storing the Fibonacci numbers will overflow far before enough parallelism is available.

↑val fibs: (n: i64) -> [n]i32

Generate the first n Fibonacci numbers using a parallel algorithm.

Work: O(n)

Span: O(log(n))

↑val fib: (n: i64) -> i32

Generate the nth Fibonacci number (0-indexed) using a parallel algorithm. Specifically, fib n == last (fibs (n+1), but fib is more efficient. However, fib_seq is likely even more efficient.

Work: O(n)

Span: O(log(n))

↑val fibs_seq: (n: i64) -> [n]i32

Generate the first n Fibonacci numbers using a sequential O(n) algorithm.

↑val fib_seq: (n: i64) -> i32

Generate the nth Fibonacci number (0-indexed) using a sequential O(n) algorithm.