echo/examples/algos/fibonacci.echo at main · csfh/echo · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
; Fibonacci — iterative nth term and prefix list fill.
; Run: xo run examples/algos/fibonacci.echo

/ std/io
/ std/str
/ std/test

; F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
$ fib = (n) {
    ? n < 0 {
        ! "fib of negative"
    }
    ? n == 0 {
        ^ 0
    }
    ? n == 1 {
        ^ 1
    }
    ~ a = 0
    ~ b = 1
    ~ i = 2
    * i <= n {
        $ next = a + b
        ~ a = b
        ~ b = next
        ~ i = i + 1
    }
    ^ b
}

; Fill pre-sized xs[0..n] with F(0)..F(n-1). Length of xs must be n.
$ fib_fill = (xs, n) {
    ? n <= 0 {
        ^ xs
    }
    ~ xs[0] = 0
    ? n == 1 {
        ^ xs
    }
    ~ xs[1] = 1
    ~ i = 2
    * i < n {
        ~ xs[i] = xs[i - 1] + xs[i - 2]
        ~ i = i + 1
    }
    ^ xs
}

| fib(0) {
    $ v {
        io.print(str.from_int(v))
    }
    ! err {
        io.print(str.from_int(err))
    }
}
| fib(1) {
    $ v {
        io.print(str.from_int(v))
    }
    ! err {
        io.print(str.from_int(err))
    }
}
| fib(10) {
    $ v {
        io.print(str.from_int(v))
    }
    ! err {
        io.print(str.from_int(err))
    }
}
| fib(20) {
    $ v {
        io.print(str.from_int(v))
    }
    ! err {
        io.print(str.from_int(err))
    }
}
~ buf = [0, 0, 0, 0, 0, 0, 0, 0]
$ filled = fib_fill(buf, 8)
~ i = 0
* i < 8 {
    io.print(str.from_int(filled[i]))
    ~ i = i + 1
}

test.bench("fib_40", () {
    | fib(40) {
        $ v {}
        ! e {}
    }
})

test.bench("fib_30", () {
    | fib(30) {
        $ v {}
        ! e {}
    }
})

\ fib, fib_fill