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