1  
 2  program test.alpha {
 3      // This calculates the n-th fibonacci number (up to 64th)
 4      transition fibonacci(public n: u8) -> u128 {
 5          assert(n <= 64u8);
 6  
 7          let f0: u128 = 0u128;
 8          let f1: u128 = 1u128;
 9          let c: u8 = 0u8;
10  
11          let z: u8 = reverse_bits(n);
12  
13          for i:u8 in 0u8..8u8 {
14              if n > 0u8 {
15                  let f2i1: u128 = f1 * f1 + f0 * f0;
16                  let f2i: u128 =  f0 * (2u128 * f1 - f0);
17                  if z & 1u8.shl(c) == 0u8 {
18                      f0 = f2i;
19                      f1 = f2i1;
20                  } else {
21                      f0 = f2i1;
22                      f1 = f2i + f2i1;
23                  }
24                  c = c + 1u8;
25                  n = n >> 1u8;
26              }
27          }
28  
29          return f0;
30      }
31  
32      function reverse_bits(n: u8) -> u8 {
33          let reverse: u8 = 0u8;
34  
35          for i:u8 in 0u8..8u8 {
36              if n > 0u8 {
37                  reverse = reverse << 1u8;
38  
39                  if n & 1u8 == 1u8 {
40                      reverse ^= 1u8;
41                  }
42  
43                  n = n >> 1u8;
44              }
45          }
46  
47          return reverse;
48      }
49  }