Created
April 17, 2016 18:24
-
-
Save sgade/5defc45d66cbb2167c5b94a11f27c148 to your computer and use it in GitHub Desktop.
Fibonacci with big numbers (and progress)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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