test/fibo.go

   1 // skip
   2
   3 // Copyright 2014 The Go Authors. All rights reserved.
   4 // Use of this source code is governed by a BSD-style
   5 // license that can be found in the LICENSE file.
   6
   7 // Usage:
   8 // fibo <n>     compute fibonacci(n), n must be >= 0
   9 // fibo -bench  benchmark fibonacci computation (takes about 1 min)
  10 //
  11 // Additional flags:
  12 // -half        add values using two half-digit additions
  13 // -opt         optimize memory allocation through reuse
  14 // -short       only print the first 10 digits of very large fibonacci numbers
  15
  16 // Command fibo is a stand-alone test and benchmark to
  17 // evaluate the performance of bignum arithmetic written
  18 // entirely in Go.
  19 package main
  20
  21 import (
  22         "flag"
  23         "fmt"
  24         "math/big" // only used for printing
  25         "os"
  26         "strconv"
  27         "testing"
  28         "text/tabwriter"
  29         "time"
  30 )
  31
  32 var (
  33         bench = flag.Bool("bench", false, "run benchmarks")
  34         half  = flag.Bool("half", false, "use half-digit addition")
  35         opt   = flag.Bool("opt", false, "optimize memory usage")
  36         short = flag.Bool("short", false, "only print first 10 digits of result")
  37 )
  38
  39 // A large natural number is represented by a nat, each "digit" is
  40 // a big.Word; the value zero corresponds to the empty nat slice.
  41 type nat []big.Word
  42
  43 const W = 1 << (5 + ^big.Word(0)>>63) // big.Word size in bits
  44
  45 // The following methods are extracted from math/big to make this a
  46 // stand-alone program that can easily be run without dependencies
  47 // and compiled with different compilers.
  48
  49 func (z nat) make(n int) nat {
  50         if n <= cap(z) {
  51                 return z[:n] // reuse z
  52         }
  53         // Choosing a good value for e has significant performance impact
  54         // because it increases the chance that a value can be reused.
  55         const e = 4 // extra capacity
  56         return make(nat, n, n+e)
  57 }
  58
  59 // z = x
  60 func (z nat) set(x nat) nat {
  61         z = z.make(len(x))
  62         copy(z, x)
  63         return z
  64 }
  65
  66 // z = x + y
  67 // (like add, but operating on half-digits at a time)
  68 func (z nat) halfAdd(x, y nat) nat {
  69         m := len(x)
  70         n := len(y)
  71
  72         switch {
  73         case m < n:
  74                 return z.add(y, x)
  75         case m == 0:
  76                 // n == 0 because m >= n; result is 0
  77                 return z.make(0)
  78         case n == 0:
  79                 // result is x
  80                 return z.set(x)
  81         }
  82         // m >= n > 0
  83
  84         const W2 = W / 2         // half-digit size in bits
  85         const M2 = (1 << W2) - 1 // lower half-digit mask
  86
  87         z = z.make(m + 1)
  88         var c big.Word
  89         for i := 0; i < n; i++ {
  90                 // lower half-digit
  91                 c += x[i]&M2 + y[i]&M2
  92                 d := c & M2
  93                 c >>= W2
  94                 // upper half-digit
  95                 c += x[i]>>W2 + y[i]>>W2
  96                 z[i] = c<<W2 | d
  97                 c >>= W2
  98         }
  99         for i := n; i < m; i++ {
 100                 // lower half-digit
 101                 c += x[i] & M2
 102                 d := c & M2
 103                 c >>= W2
 104                 // upper half-digit
 105                 c += x[i] >> W2
 106                 z[i] = c<<W2 | d
 107                 c >>= W2
 108         }
 109         if c != 0 {
 110                 z[m] = c
 111                 m++
 112         }
 113         return z[:m]
 114 }
 115
 116 // z = x + y
 117 func (z nat) add(x, y nat) nat {
 118         m := len(x)
 119         n := len(y)
 120
 121         switch {
 122         case m < n:
 123                 return z.add(y, x)
 124         case m == 0:
 125                 // n == 0 because m >= n; result is 0
 126                 return z.make(0)
 127         case n == 0:
 128                 // result is x
 129                 return z.set(x)
 130         }
 131         // m >= n > 0
 132
 133         z = z.make(m + 1)
 134         var c big.Word
 135
 136         for i, xi := range x[:n] {
 137                 yi := y[i]
 138                 zi := xi + yi + c
 139                 z[i] = zi
 140                 // see "Hacker's Delight", section 2-12 (overflow detection)
 141                 c = ((xi & yi) | ((xi | yi) &^ zi)) >> (W - 1)
 142         }
 143         for i, xi := range x[n:] {
 144                 zi := xi + c
 145                 z[n+i] = zi
 146                 c = (xi &^ zi) >> (W - 1)
 147                 if c == 0 {
 148                         copy(z[n+i+1:], x[i+1:])
 149                         break
 150                 }
 151         }
 152         if c != 0 {
 153                 z[m] = c
 154                 m++
 155         }
 156         return z[:m]
 157 }
 158
 159 func bitlen(x big.Word) int {
 160         n := 0
 161         for x > 0 {
 162                 x >>= 1
 163                 n++
 164         }
 165         return n
 166 }
 167
 168 func (x nat) bitlen() int {
 169         if i := len(x); i > 0 {
 170                 return (i-1)*W + bitlen(x[i-1])
 171         }
 172         return 0
 173 }
 174
 175 func (x nat) String() string {
 176         const shortLen = 10
 177         s := new(big.Int).SetBits(x).String()
 178         if *short && len(s) > shortLen {
 179                 s = s[:shortLen] + "..."
 180         }
 181         return s
 182 }
 183
 184 func fibo(n int, half, opt bool) nat {
 185         switch n {
 186         case 0:
 187                 return nil
 188         case 1:
 189                 return nat{1}
 190         }
 191         f0 := nat(nil)
 192         f1 := nat{1}
 193         if half {
 194                 if opt {
 195                         var f2 nat // reuse f2
 196                         for i := 1; i < n; i++ {
 197                                 f2 = f2.halfAdd(f1, f0)
 198                                 f0, f1, f2 = f1, f2, f0
 199                         }
 200                 } else {
 201                         for i := 1; i < n; i++ {
 202                                 f2 := nat(nil).halfAdd(f1, f0) // allocate a new f2 each time
 203                                 f0, f1 = f1, f2
 204                         }
 205                 }
 206         } else {
 207                 if opt {
 208                         var f2 nat // reuse f2
 209                         for i := 1; i < n; i++ {
 210                                 f2 = f2.add(f1, f0)
 211                                 f0, f1, f2 = f1, f2, f0
 212                         }
 213                 } else {
 214                         for i := 1; i < n; i++ {
 215                                 f2 := nat(nil).add(f1, f0) // allocate a new f2 each time
 216                                 f0, f1 = f1, f2
 217                         }
 218                 }
 219         }
 220         return f1 // was f2 before shuffle
 221 }
 222
 223 var tests = []struct {
 224         n    int
 225         want string
 226 }{
 227         {0, "0"},
 228         {1, "1"},
 229         {2, "1"},
 230         {3, "2"},
 231         {4, "3"},
 232         {5, "5"},
 233         {6, "8"},
 234         {7, "13"},
 235         {8, "21"},
 236         {9, "34"},
 237         {10, "55"},
 238         {100, "354224848179261915075"},
 239         {1000, "43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875"},
 240 }
 241
 242 func test(half, opt bool) {
 243         for _, test := range tests {
 244                 got := fibo(test.n, half, opt).String()
 245                 if got != test.want {
 246                         fmt.Printf("error: got std fibo(%d) = %s; want %s\n", test.n, got, test.want)
 247                         os.Exit(1)
 248                 }
 249         }
 250 }
 251
 252 func selfTest() {
 253         if W != 32 && W != 64 {
 254                 fmt.Printf("error: unexpected wordsize %d", W)
 255                 os.Exit(1)
 256         }
 257         for i := 0; i < 4; i++ {
 258                 test(i&2 == 0, i&1 != 0)
 259         }
 260 }
 261
 262 func doFibo(n int) {
 263         start := time.Now()
 264         f := fibo(n, *half, *opt)
 265         t := time.Since(start)
 266         fmt.Printf("fibo(%d) = %s (%d bits, %s)\n", n, f, f.bitlen(), t)
 267 }
 268
 269 func benchFibo(b *testing.B, n int, half, opt bool) {
 270         for i := 0; i < b.N; i++ {
 271                 fibo(n, half, opt)
 272         }
 273 }
 274
 275 func doBench(half, opt bool) {
 276         w := tabwriter.NewWriter(os.Stdout, 0, 8, 2, ' ', tabwriter.AlignRight)
 277         fmt.Fprintf(w, "wordsize = %d, half = %v, opt = %v\n", W, half, opt)
 278         fmt.Fprintf(w, "n\talloc count\talloc bytes\tns/op\ttime/op\t\n")
 279         for n := 1; n <= 1e6; n *= 10 {
 280                 res := testing.Benchmark(func(b *testing.B) { benchFibo(b, n, half, opt) })
 281                 fmt.Fprintf(w, "%d\t%d\t%d\t%d\t%s\t\n", n, res.AllocsPerOp(), res.AllocedBytesPerOp(), res.NsPerOp(), time.Duration(res.NsPerOp()))
 282         }
 283         fmt.Fprintln(w)
 284         w.Flush()
 285 }
 286
 287 func main() {
 288         selfTest()
 289         flag.Parse()
 290
 291         if args := flag.Args(); len(args) > 0 {
 292                 // command-line use
 293                 fmt.Printf("half = %v, opt = %v, wordsize = %d bits\n", *half, *opt, W)
 294                 for _, arg := range args {
 295                         n, err := strconv.Atoi(arg)
 296                         if err != nil || n < 0 {
 297                                 fmt.Println("invalid argument", arg)
 298                                 continue
 299                         }
 300                         doFibo(n)
 301                 }
 302                 return
 303         }
 304
 305         if *bench {
 306                 for i := 0; i < 4; i++ {
 307                         doBench(i&2 == 0, i&1 != 0)
 308                 }
 309         }
 310 }