斐波那契(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. }