Documentation ¶
Overview ¶
Package fib contains sample benchmarks for Fibonacci numbers.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BigFib ¶
BigFib returns the nth number in the Fibonacci series using a loop instead of recursion. It uses the Go standard library 'big' package to handle large numbers.
func Fib ¶
Fib returns the nth number in the Fibonacci series using recursion.
A good example of the use of benchmarks to increase efficiency and performance is found by benchmarking two versions of code that produce the Fibonacci numbers.
As shown below, the common recursion method slows down very quickly and by the 40th iteration is nearly worthless.
In contrast, a looping method using three variables to carry over numbers from each iteration maintains adequate efficiency over a much larger range of input numbers.
For even larger numbers, the looping method is combined with the Go standard library 'big' package that can handle very large numbers. Although it loses efficiency faster then the looping method, it is able to calculate the 100,000th fibonacci number without much effort on a six year old laptop.
number of digits in Fib(100000): 20899
fibFunc = Fib
BenchmarkFib1-8 462941701 2.518 ns/op BenchmarkFib2-8 163377795 7.904 ns/op BenchmarkFib3-8 94761864 12.37 ns/op BenchmarkFib10-8 2723514 445.4 ns/op BenchmarkFib20-8 20402 55050 ns/op BenchmarkFib40-8 2 779317892 ns/op
fibFunc = FibLoop
BenchmarkFib1-8 404492092 2.793 ns/op BenchmarkFib2-8 316388378 3.713 ns/op BenchmarkFib3-8 278436595 4.307 ns/op BenchmarkFib10-8 142531582 8.438 ns/op BenchmarkFib20-8 82595132 14.58 ns/op BenchmarkFib40-8 38278879 31.35 ns/op BenchmarkFib10000-8 203696 5667 ns/op
BigFib
BenchmarkBigFib10-8 1847473 596.2 ns/op BenchmarkBigFib100-8 349316 3062 ns/op BenchmarkBigFib1000-8 24037 43525 ns/op BenchmarkBigFib10000-8 1377 808891 ns/op BenchmarkBigFib-8 21 47725780 ns/op
func FibLoop ¶
FibLoop returns the nth number in the Fibonacci series using a loop instead of recursion. Uses Int64.
func FibLoopU ¶
FibLoopU returns the nth number in the Fibonacci series using a loop instead of recursion. Uses Uint64.
func TestMaxInt64 ¶
func TestMaxInt64()
Types ¶
This section is empty.