I moved my blog a few days ago to
codebetter.com, I'm sure most of you know the story by now.
This is just a notice to anyone to subscribes to
redirect your aggregator to my new url:
http://codebetter.com/blogs/ben.reichelt/Rss.aspx
I would also encourage you to subscribe to the main
feed at codebetter.com
http://codebetter.com/blogs/MainFeed.aspx
thanks for reading!
Firefox does not support scrollable divs with the mouse wheel.
I poked around in the extensive bug database trying to find this listed, but the
number of bugs is just too daunting. This really sucks, because we develop our
stuff to work on ie as well as Firefox, so whenever we run into a div with a
scroll bar, the screen just kind of jumps around. I'm surprised that I haven't
heard much about this problem from other people, as the mouse wheel has become
invaluable to me, I hate having to move my mouse to the scroll bar, and manually
move it down......
Hmm, is
this the sound of a
Google web browser rumor starting up again?? Ben Goodger has left the Mozilla Foundation where he was a lead engineer of the Firefox browser. Coincidence? I think not.......
Now we've seen a slow way to generate the fibonacci numbers, and we've seen why its so slow, now we'll try to do better. Here's my proposed improvement to our recursive function that we made the first day:
static long Fibo(long n)
{
//
// check the base cases
//
if (n <= 1)
return 0;
if (n == 2)
return 1;
//
// initialize our array of fibonacci numbers
//
long[] numbers = new long[n];
numbers[0] = 0;
numbers[1] = 1;
//
// calculate the 2nd through nth
// fibonacci numbers in the array
//
for (long i = 2; i < n; i++)
{
numbers[i] = numbers[i - 1] + numbers[i - 2];
}
return numbers[n - 1];
}
So what we're doing here is that instead of making recursive calls to the Fibo function, we are just storing the fibonacci numbers in an array of length n. We don't have the recursion tree at all now, as there are no recursive calls. All we have is the overhead of the array, and a loop that will loop n times. During each loop interation, we simply add the two previous numbers in the array, and put the result in the current array position. Using this function we can easily get the 50th, 100th, or 1000000th fibonacci number, no problem. Go ahead, try it! The response is nearly immediate! However, there is one more little thing we can change to make the function even better.
In the code above, we maintain an array of the 0 to nth fibonacci numbers, when really, all we need is the current number, and the previous number, in order to generate the next one. So we can remove the overhead costs that are associated with the array:
static long Fibo(long n)
{
//
// check the base cases
//
if (n <= 1)
return 0;
if (n == 2)
return 1;
//
// initialize our loop varibles
//
long x = 0;
long y = 1;
long current = 0;
//
// calculate the 2nd through nth
// fibonacci numbers, but without
// the array overheard
//
for (long i = 2; i < n; i++)
{
current = x + y;
x = y;
y = current;
}
return current;
}
Here, instead of an array of length n, we simply have x, y, and current. We still have the loop that will iterate n times, but each time the loop adds x and y and then puts the value of y into x, and the new value into y. We can store all the values we need in just three variables!
I ran some tests and compared the results of the 3 different functions, heres what I found:
| | 10 | 20 | 30 | 40 | 50 |
| Slow | 125000 | 62500 | 312500 | 37484375 | 4.18E+09 |
| Better | 140625 | 78125 | 31250 | 31250 | 0 |
| Best | 93750 | 109375 | 46875 | 78125 | 0 |
So you can see that the difference in the functions is trivial when finding the 10th or 20th fibonacci number. However, the difference becomes very noticeable when generating the 40th number, and once we get to the 50th, the difference is staggering. I went and ate dinner while the slow function was processing the 50th number! The number