斐波那契(fibonacci)

  1. /// Fibonacci via Dynamic Programming
  3. /// fibonacci(n) returns the nth fibonacci number
  4. /// This function uses the definition of Fibonacci where:
  5. /// F(0) = F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  6. ///
  7. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  8. pub fn fibonacci(n: u32) -> u128 {
  9.     // Use a and b to store the previous two values in the sequence
  10.     let mut a = 0;
  11.     let mut b = 1;
  12.     for _i in 0..n {
  13.         // As we iterate through, move b's value into a and the new computed
  14.         // value into b.
  15.         let c = a + b;
  16.         a = b;
  17.         b = c;
  18.     }
  19.     b
  20. }
  22. /// fibonacci(n) returns the nth fibonacci number
  23. /// This function uses the definition of Fibonacci where:
  24. /// F(0) = F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  25. ///
  26. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  27. pub fn recursive_fibonacci(n: u32) -> u128 {
  28.     // Call the actual tail recursive implementation, with the extra
  29.     // arguments set up.
  30.     _recursive_fibonacci(n, 0, 1)
  31. }
  33. fn _recursive_fibonacci(n: u32, previous: u128, current: u128) -> u128 {
  34.     if n == 0 {
  35.         current
  36.     } else {
  37.         _recursive_fibonacci(n - 1, current, current + previous)
  38.     }
  39. }
  41. /// classical_fibonacci(n) returns the nth fibonacci number
  42. /// This function uses the definition of Fibonacci where:
  43. /// F(0) = 0, F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  44. ///
  45. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  46. pub fn classical_fibonacci(n: u32) -> u128 {
  47.     match n {
  48.         0 => 0,
  49.         1 => 1,
  50.         _ => {
  51.             let k = n / 2;
  52.             let f1 = classical_fibonacci(k);
  53.             let f2 = classical_fibonacci(k - 1);
  55.             match n % 4 {
  56.                 0 | 2 => f1 * (f1 + 2 * f2),
  57.                 1 => (2 * f1 + f2) * (2 * f1 - f2) + 2,
  58.                 _ => (2 * f1 + f2) * (2 * f1 - f2) - 2,
  59.             }
  60.         }
  61.     }
  62. }
  64. /// logarithmic_fibonacci(n) returns the nth fibonacci number
  65. /// This function uses the definition of Fibonacci where:
  66. /// F(0) = 0, F(1) = 1 and F(n+1) = F(n) + F(n-1) for n>0
  67. ///
  68. /// Warning: This will overflow the 128-bit unsigned integer at n=186
  69. pub fn logarithmic_fibonacci(n: u32) -> u128 {
  70.     // if it is the max value before overflow, use n-1 then get the second
  71.     // value in the tuple
  72.     if n == 186 {
  73.         let (_, second) = _logarithmic_fibonacci(185);
  74.         second
  75.     } else {
  76.         let (first, _) = _logarithmic_fibonacci(n);
  77.         first
  78.     }
  79. }
  81. fn _logarithmic_fibonacci(n: u32) -> (u128, u128) {
  82.     match n {
  83.         0 => (0, 1),
  84.         _ => {
  85.             let (current, next) = _logarithmic_fibonacci(n / 2);
  86.             let c = current * (next * 2 - current);
  87.             let d = current * current + next * next;
  89.             match n % 2 {
  90.                 0 => (c, d),
  91.                 _ => (d, c + d),
  92.             }
  93.         }
  94.     }
  95. }
  97. #[cfg(test)]
  98. mod tests {
  99.     use super::classical_fibonacci;
  100.     use super::fibonacci;
  101.     use super::logarithmic_fibonacci;
  102.     use super::recursive_fibonacci;
  104.     #[test]
  105.     fn test_fibonacci() {
  106.         assert_eq!(fibonacci(0), 1);
  107.         assert_eq!(fibonacci(1), 1);
  108.         assert_eq!(fibonacci(2), 2);
  109.         assert_eq!(fibonacci(3), 3);
  110.         assert_eq!(fibonacci(4), 5);
  111.         assert_eq!(fibonacci(5), 8);
  112.         assert_eq!(fibonacci(10), 89);
  113.         assert_eq!(fibonacci(20), 10946);
  114.         assert_eq!(fibonacci(100), 573147844013817084101);
  115.         assert_eq!(fibonacci(184), 205697230343233228174223751303346572685);
  116.     }
  118.     #[test]
  119.     fn test_recursive_fibonacci() {
  120.         assert_eq!(recursive_fibonacci(0), 1);
  121.         assert_eq!(recursive_fibonacci(1), 1);
  122.         assert_eq!(recursive_fibonacci(2), 2);
  123.         assert_eq!(recursive_fibonacci(3), 3);
  124.         assert_eq!(recursive_fibonacci(4), 5);
  125.         assert_eq!(recursive_fibonacci(5), 8);
  126.         assert_eq!(recursive_fibonacci(10), 89);
  127.         assert_eq!(recursive_fibonacci(20), 10946);
  128.         assert_eq!(recursive_fibonacci(100), 573147844013817084101);
  129.         assert_eq!(
  130.             recursive_fibonacci(184),
  131.             205697230343233228174223751303346572685
  132.         );
  133.     }
  135.     #[test]
  136.     fn test_classical_fibonacci() {
  137.         assert_eq!(classical_fibonacci(0), 0);
  138.         assert_eq!(classical_fibonacci(1), 1);
  139.         assert_eq!(classical_fibonacci(2), 1);
  140.         assert_eq!(classical_fibonacci(3), 2);
  141.         assert_eq!(classical_fibonacci(4), 3);
  142.         assert_eq!(classical_fibonacci(5), 5);
  143.         assert_eq!(classical_fibonacci(10), 55);
  144.         assert_eq!(classical_fibonacci(20), 6765);
  145.         assert_eq!(classical_fibonacci(21), 10946);
  146.         assert_eq!(classical_fibonacci(100), 354224848179261915075);
  147.         assert_eq!(
  148.             classical_fibonacci(184),
  149.             127127879743834334146972278486287885163
  150.         );
  151.     }
  153.     #[test]
  154.     fn test_logarithmic_fibonacci() {
  155.         assert_eq!(logarithmic_fibonacci(0), 0);
  156.         assert_eq!(logarithmic_fibonacci(1), 1);
  157.         assert_eq!(logarithmic_fibonacci(2), 1);
  158.         assert_eq!(logarithmic_fibonacci(3), 2);
  159.         assert_eq!(logarithmic_fibonacci(4), 3);
  160.         assert_eq!(logarithmic_fibonacci(5), 5);
  161.         assert_eq!(logarithmic_fibonacci(10), 55);
  162.         assert_eq!(logarithmic_fibonacci(20), 6765);
  163.         assert_eq!(logarithmic_fibonacci(21), 10946);
  164.         assert_eq!(logarithmic_fibonacci(100), 354224848179261915075);
  165.         assert_eq!(
  166.             logarithmic_fibonacci(184),
  167.             127127879743834334146972278486287885163
  168.         );
  169.     }
  171.     #[test]
  172.     /// Check that the itterative and recursive fibonacci
  173.     /// produce the same value. Both are combinatorial ( F(0) = F(1) = 1 )
  174.     fn test_iterative_and_recursive_equivalence() {
  175.         assert_eq!(fibonacci(0), recursive_fibonacci(0));
  176.         assert_eq!(fibonacci(1), recursive_fibonacci(1));
  177.         assert_eq!(fibonacci(2), recursive_fibonacci(2));
  178.         assert_eq!(fibonacci(3), recursive_fibonacci(3));
  179.         assert_eq!(fibonacci(4), recursive_fibonacci(4));
  180.         assert_eq!(fibonacci(5), recursive_fibonacci(5));
  181.         assert_eq!(fibonacci(10), recursive_fibonacci(10));
  182.         assert_eq!(fibonacci(20), recursive_fibonacci(20));
  183.         assert_eq!(fibonacci(100), recursive_fibonacci(100));
  184.         assert_eq!(fibonacci(184), recursive_fibonacci(184));
  185.     }
  187.     #[test]
  188.     /// Check that classical and combinatorial fibonacci produce the
  189.     /// same value when 'n' differs by 1.
  190.     /// classical fibonacci: ( F(0) = 0, F(1) = 1 )
  191.     /// combinatorial fibonacci: ( F(0) = F(1) = 1 )
  192.     fn test_classical_and_combinatorial_are_off_by_one() {
  193.         assert_eq!(classical_fibonacci(1), fibonacci(0));
  194.         assert_eq!(classical_fibonacci(2), fibonacci(1));
  195.         assert_eq!(classical_fibonacci(3), fibonacci(2));
  196.         assert_eq!(classical_fibonacci(4), fibonacci(3));
  197.         assert_eq!(classical_fibonacci(5), fibonacci(4));
  198.         assert_eq!(classical_fibonacci(6), fibonacci(5));
  199.         assert_eq!(classical_fibonacci(11), fibonacci(10));
  200.         assert_eq!(classical_fibonacci(20), fibonacci(19));
  201.         assert_eq!(classical_fibonacci(21), fibonacci(20));
  202.         assert_eq!(classical_fibonacci(101), fibonacci(100));
  203.         assert_eq!(classical_fibonacci(185), fibonacci(184));
  204.     }
  205. }