Skip to content

Instantly share code, notes, and snippets.

@bosley
Last active September 16, 2020 20:08
Show Gist options
  • Save bosley/00bcac39eaf4d289f191a6dd27f26902 to your computer and use it in GitHub Desktop.
Save bosley/00bcac39eaf4d289f191a6dd27f26902 to your computer and use it in GitHub Desktop.
package main
import (
"fmt"
)
// Calculate fib sequence
// This is done linerally as recursive calculation is an exponential explosion
// in time, and after the around 35th digit or so would be unreasonable to calculate
//
// https://en.wikipedia.org/wiki/Fibonacci_number
//
func fib(n int) uint64 {
// make the list
seq := make([]uint64, n+1, n+2)
// edge case < 2, create the space for 0 and 1
if n < 2 {
seq = seq[0:2]
}
// Manually set n-1, and n-2
seq[0] = 0
seq[1] = 1
// f(n) = f(n-1) + f(n-2)
for i := 2; i <= n; i++ {
seq[i] = seq[i-1] + seq[i-2]
}
return seq[n]
}
// Recursive calculation - This could take a very long time (see above)
//
func fibRecurse(n int) uint64 {
// Edge case 0
if n <= 0 {
return 0
}
// Edge case 1
if n == 1 {
return 1
}
// Recurse to calculate
// f(n) = f(n-1) + f(n-2)
return fibRecurse(n-1) + fibRecurse(n-2)
}
// Get the digit of the fib sequence that the user wants to calculate to
//
func getNth() int {
complete := false
destInt := 0
for !complete {
fmt.Print("Enter the \"nth\" digit to calculate to: ")
fmt.Scan(&destInt)
if destInt < 0 {
fmt.Println("Number must be greater than or equal to 0 !")
} else {
complete = true
}
}
return destInt
}
// Entry point
//
func main() {
// Get the 'nth' number that they want to calculate to
destInt := getNth()
// Calculate the number offset by 1 as the fib function 0-indexes
for i := 0; i <= destInt-1; i++ {
// Print number and space
fmt.Print(fib(i))
// Uncomment to see how slow fibRecurse is
//
//fmt.Print(fibRecurse(i))
fmt.Print(" ")
}
fmt.Println("")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment