-
Notifications
You must be signed in to change notification settings - Fork 0
/
fibonacci-numbers.html
218 lines (171 loc) · 7 KB
/
fibonacci-numbers.html
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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
<p><!doctype html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="markdown.css" type="text/css" rel="stylesheet"></link>
<link href="prettify.css" type="text/css" rel="stylesheet"></link>
<script type="text/javascript" src="js/jquery-1.7.1.min.js"></script>
<script type="text/javascript" src="js/google-code-prettify/prettify.js"></script>
<script type="text/javascript" src="https://d3eoax9i5htok0.cloudfront.net/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/javascript" src="js/myscripts.js"></script>
<title>Thousand Note - Fibonacci Numbers</title>
</head></p>
<p><body onload="styleCode()"></p>
<p><a href="index.html">Thousandnote</a></p>
<h1>Fibonacci Numbers</h1>
<p>Problem:</p>
<blockquote>
<blockquote>
<p>Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:</p>
<p>1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</p>
<p>By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.</p>
</blockquote>
<p>I'd like you to come up with 3 different solutions. The first has to be iterative. The second has to be recursive. And the last has to be efficient. Use the information you learn from the previous two solutions and any clues in the question to come up with a clever solution to the stated problem that has the fastest running time. If you can, time the three implementations and see if your optimizations are notable improvements.</p>
</blockquote>
<h2>Your solutions</h2>
<p>In Java,</p>
<pre><code>public static void iterativeway(){
out.println("Iterative way:");
int sum=2;
int fib=0;
int start1=1;
int start2=2;
out.println(start1);
out.println(start2);
while(start1+start2<=max){
fib=start1+start2;
start1=start2;
start2=fib;
if(fib%2==0){
sum+=fib;
}
out.println(fib);
}
out.println("Sum=" + sum);
}
public static void recursiveway(int x, int y, int sum){
if(x==1 && y==2)
{
out.println("Recursive way:");
out.println(x);
out.println(y);
}
if(x+y>max)
{
out.println("Sum=" +sum);
}
else
{
if((x+y)%2==0)
{
sum+=(x+y);
}
out.println((x+y));
recursiveway(y,x+y,sum);
}
}
public static String efficientway()
{
double x= (1+Math.sqrt(5.0))/2;
double y= -(1/(x));
out.println("Efficient way:");
int fib=0;
int i=3;
int sum=0;
while(fib<max){
sum+=fib;
fib=(int) Math.round((((Math.pow(x,i)+ Math.pow(y, i))/(Math.sqrt(5.0)))));
i+=3;
}
String total= "Sum=" +sum;
return total;
}
</code></pre>
<p>These all work and come up with the right solution.
The efficient way is good. You noticed or picked up
on an important pattern in the data, which is that
even fibonacci numbers only occur every third term.
This is because of this fact,</p>
<pre><code>Odd + Even = Even + Odd = Odd
Odd + Odd = Even
Even + Even = Even
</code></pre>
<p>Which is based on the properties of addition mod 2,</p>
<pre><code>(1 + 0) mod 2 = (0 + 1) mod 2 = 1 mod 2
(1 + 1) mod 2 = 2 mod 2 = 0 mod 2
(0 + 0) mod 2 = 0 mod 2
</code></pre>
<p>And only two of these cases occur in the traditional Fibonacci sequence.
Otherwise we'd be trapped, so to speak, among even numbers.</p>
<h2>And Your Main</h2>
<pre><code>public static void main(String[] args) throws IOException
{
out = new PrintStream("output.txt");
starttime=System.currentTimeMillis();
iterativeway();
endtime=System.currentTimeMillis();
out.println("Total iterative time =" + (endtime-starttime) +"ms");
starttime=System.currentTimeMillis();
recursiveway(1,2,2);
endtime=System.currentTimeMillis();
out.println("Total recursive time =" + (endtime-starttime)+"ms");
starttime=System.currentTimeMillis();
out.println(efficientway());
endtime=System.currentTimeMillis();
out.println("Total efficient time =" + (endtime-starttime)+"ms");
out.println("test end");
}
</code></pre>
<p>There are a few inefficiencies I'd like to address here. One of the major intentions
of <a href="http://en.wikipedia.org/wiki/Object_oriented_programming">object-oriented programming</a>
is the idea of <a href="http://en.wikipedia.org/wiki/Code_reuse">code reuse</a>. In general, though
there are exceptions, you should not be copying and pasting major parts of your code.
If there are parts of your code that look very similar save the names of certain variables
you should be thinking about how to refactor that code into a more reusable form.</p>
<p>Refactoring the <code>main</code> would consequently have encouraged you to refactor all of the
functions in general to have a common <a href="http://en.wikipedia.org/wiki/Interface_(object-oriented_programming)">interface</a>,
which is a very important part of modularity, one of the main tenets of of object-oriented programming.</p>
<h2>Python Comparison</h2>
<p>Two ways to generate Fibonacci numbers I came up with real quick.</p>
<pre><code>def fib(n):
"""
Naive recursive implemention for generating a fibonacci number.
.. note::
The stack gets overwhelmed if n is too large, and runs horribly slow.
"""
if n == 0 or n == 1:
# Base cases
return n
else:
# Recursive call
return fib(n-1) + fib(n-2)
def smartFib(n):
"""
Smarter implementation of generating a fibonacci number.
It saves past values and uses them to calculate future values.
"""
l = [0, 1] # Base cases
while l[-1] < n:
# Append a new value to the list made up of the last two values.
l.append(l[-2] + l[-1])
return l
</code></pre>
<p>There are no sums being done here, but that can easily be added in.
I give these two examples just to show the difference between recursive
and iterative calls. Your iterative solution is constantly swapping values,
this iterative solution saves them for future use. Both recursive calls
require vast amounts of memory and can be slow and costly to do. However,
note that the recursive call doesn't need both values <code>x</code> and <code>y</code> as
in your solution, but only <code>n</code> or the upper limit as in mine.</p>
<h2>Math</h2>
<p>A brilliant solution to the problem, but with a limit of <code>1000000</code>, which I found on a forum, is as follows,</p>
<pre><code>Phi (golden ratio) is the approximate ratio between
two consecutive terms in a Fibonacci sequence.
The ratio between consecutive even terms approaches
phi^3 (4.236068) because each 3rd term is even.
Use a calculator and round the results to the nearest
integer when calculating the next terms:
2,8,34,.. multiplying by 4.236068 each time: 144,610,
2584,10946,46368,196418 & 832040
The sum is 1089154
</code></pre>
<p>Enjoy!</p>