Mathematical puzzles

Will · May 30th, 2010, 06:07 AM

Yeah thats it! Well I hope it is, the debugger was confusing me because the values weren't showing what I expected but then I realised it was calling the method twice in the return and working that out as it came along.

At first I expected it just to spit the result out and not work through the other two and evaluate their results as well. Not sure if what I have written makes sense but it does to me.

Will · May 30th, 2010, 06:38 AM

That was sort of fun but turns out that recursive method is far too inefficient to actually use...

Will · May 30th, 2010, 08:06 AM

If anyone is interested this seems to be a more efficient way to do it:

Code:

static int Fibonacci(int x)
        {
            //if (x <= 1)
            //    return 1;
            //return Fibonacci(x - 1) + Fibonacci(x - 2); //TO INEFFICIENT

            int previous = -1;
            int result = 1;
            int i = 0;

            for (i = 0; i <= x; ++i)
            {
                int sum = result + previous;
                previous = result;
                result = sum;
            }
            return result;
        }

DrPurdum · May 30th, 2010, 08:38 AM

Hi Will:

As a general rule, division is the slowest math operation you can do. If you want to experiment, try writing a tight loop that divides a floating point number by 10 a million times and time it. Then write the same loop and mutliply it by .1 a million times. While I haven't run this experiment for some time, the divide used to be about twice as slow. Perhaps new optimizing compilers are better now, but my guess is that division is still the slowest operator. Bit shifting was an old assembler language trick to do quick divides and multiplies by two, but that's probably an H-bomb to kill an ant now.

Methods and functions can call themselves in what is called a recursive function call. You might Google that for some explanations. Calculating a factorial is a classic example of recursion. Keep in mind, however, that each recursive call places a new set of parameters on the stack during each function call, driving the stack deeper and deeper. It's not uncommon to run out of stack space and crash the system if you don't code the terminating criteria correctly.

Anyway, it's encouraging that you're experimenting...it's a great way to improve your coding skills.