Documentation
¶
Overview ¶
Package fib computes Fibonacci numbers by tail recursion, as a state machine:
fib(n) = fib(n, 0, 1) fib(n, a, b) = a if n == 0 fib(n, a, b) = fib(n-1, b, a+b) otherwise
The machine is the call fib(n, a, b): it holds all three arguments, and each EvCall evaluates it once. A tail call replaces the arguments, so the machine is the next call and nothing is left to return to. The holder's loop is the trampoline: it fires until the call has returned.
a and b are big integers of up to Bits bits. A big.Int holds a slice, so a machine holding one could not be compared with ==; the machine holds each number as Words 64-bit words instead, and its accessors return them as big.Int values.
Index ¶
Constants ¶
const ( Words = 16 // 64-bit words in a number Bits = Words * 64 // bits in a number )
The size of the numbers the call holds.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Event ¶
type Event uint8
Event is an input to Fire.
const (
EvCall Event // evaluate fib(n, a, b) once
)
Event values.
type Machine ¶
type Machine struct {
// contains filtered or unexported fields
}
Machine is the call fib(n, a, b). Build it with New and change it only with Fire.
Source Files
Directories