-
Notifications
You must be signed in to change notification settings - Fork 158
/
fibonacci.rs
70 lines (60 loc) · 2.03 KB
/
fibonacci.rs
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
use super::{Example, ONE, ZERO};
use miden_vm::{math::Felt, Assembler, DefaultHost, MemAdviceProvider, Program, StackInputs};
// EXAMPLE BUILDER
// ================================================================================================
pub fn get_example(n: usize) -> Example<DefaultHost<MemAdviceProvider>> {
// generate the program and expected results
let program = generate_fibonacci_program(n);
let expected_result = vec![compute_fibonacci(n)];
println!(
"Generated a program to compute {}-th Fibonacci term; expected result: {}",
n, expected_result[0]
);
Example {
program,
stack_inputs: StackInputs::try_from_ints([0, 1]).unwrap(),
host: DefaultHost::default(),
expected_result,
num_outputs: 1,
}
}
/// Generates a program to compute the `n`-th term of Fibonacci sequence
fn generate_fibonacci_program(n: usize) -> Program {
// the program is a simple repetition of 4 stack operations:
// the first operation moves the 2nd stack item to the top,
// the second operation duplicates the top 2 stack items,
// the third operation removes the top item from the stack
// the last operation pops top 2 stack items, adds them, and pushes
// the result back onto the stack
let program = format!(
"begin
repeat.{}
swap dup.1 add
end
end",
n - 1
);
Assembler::default().compile(program).unwrap()
}
/// Computes the `n`-th term of Fibonacci sequence
fn compute_fibonacci(n: usize) -> Felt {
let mut t0 = ZERO;
let mut t1 = ONE;
for _ in 0..n {
t1 = t0 + t1;
core::mem::swap(&mut t0, &mut t1);
}
t0
}
// EXAMPLE TESTER
// ================================================================================================
#[test]
fn test_fib_example() {
let example = get_example(16);
super::test_example(example, false);
}
#[test]
fn test_fib_example_fail() {
let example = get_example(16);
super::test_example(example, true);
}