Skip to content

Instantly share code, notes, and snippets.

@sgade
Created April 17, 2016 18:24
Show Gist options
  • Save sgade/5defc45d66cbb2167c5b94a11f27c148 to your computer and use it in GitHub Desktop.
Save sgade/5defc45d66cbb2167c5b94a11f27c148 to your computer and use it in GitHub Desktop.
Fibonacci with big numbers (and progress)
package main
import (
"bufio"
"fmt"
"math/big"
"os"
"strconv"
"strings"
"time"
"gopkg.in/cheggaaa/pb.v1"
)
// getNumberInput reads input from the stdin and returns it parsed as a number.
func getNumberInput(prompt string) (int, error) {
reader := bufio.NewReader(os.Stdin)
for {
fmt.Printf("%v", prompt)
if text, err := reader.ReadString('\n'); err != nil {
return -1, err
} else {
text = strings.Replace(text, "\n", "", -1)
if value, err := strconv.Atoi(text); err == nil {
return value, nil
}
}
}
return -1, fmt.Errorf("Unexpected end of infinite loop.")
}
// fib calculates the n'th fibonacci number.
// Progress is reported via the progress channel while the final result is transmitted via the result channel.
func fib(n int64, result chan big.Int, progress chan float64) {
if n < 1 {
result <- big.Int{}
return
}
// initial values
a, b := big.NewInt(0), big.NewInt(1)
// constants
one := big.NewInt(1)
nBig := big.NewInt(n)
// report start
progress <- 0.0
for i := big.NewInt(0); i.Cmp(nBig) == -1; i.Add(i, one) {
//a, b = a+b, a
tmp := a
a.Add(a, b)
b.Set(tmp)
// progress reporting
iBig := big.NewInt(0).Set(i)
iBig.Mul(iBig, big.NewInt(10000))
p := big.NewInt(0).Div(iBig, nBig)
progress <- (float64(p.Int64()) / 10000.0)
}
// report end
progress <- 1.0
result <- *a
}
func main() {
n, err := getNumberInput("fib(n) = x; n = ")
if err != nil {
panic(err)
}
result := make(chan big.Int)
progress := make(chan float64)
go fib(int64(n), result, progress)
// wait for it to start
<-progress
bar := pb.New(10000)
bar.ShowCounters = false
bar.ShowTimeLeft = false
bar.ShowBar = false
bar.ShowPercent = false
bar.Prefix(fmt.Sprintf("Calculating fib(%v)... ", n))
bar.Start()
running := true
startTimeout := time.After(3 * time.Second)
for running {
select {
case <-startTimeout:
// show bar only after timeout
bar.ShowPercent = true
bar.ShowBar = true
bar.ShowSpeed = true
case p := <-progress:
if bar.ShowBar {
barValue := int(p * 10000)
bar.Set(barValue)
}
if p >= 1.0 {
running = false
}
}
}
bar.FinishPrint("Done!")
r := <-result
fmt.Printf("fib(%v) = %v\n", n, &r)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment