Thursday, September 20, 2012

Recursive Fibonacci

So after bashing my head against the wall working on Fibonacci recursively and thinking "why on earth is this so slow," I realized the solution was reducing everything to a lot of ones and adding them all up. While addition and basic arithmetic for a CPU is exceptionally fast, this was slow due to the magnitude, and would cause way too much recursion for it to even be considered a correct solution. So I searched the web figuring someone far smarter than myself would have not only realized this, but come up with a real solution for it. Sure enough, I found one. The solution they used was in C, so I found it a bit ugly as it required two function calls (so you can call it with one argument). So I converted it to Haskell.

Before posting, the short explanation is this. Fibonacci numbers are found by adding up the previous two numbers. This is not to say you should call it inappropriately like this.

fib :: Integer-> Integer
fib 0 = 0
fib 1 = 1
fib x = fib (x - 1) + fib (x - 2)

However, this is often the solution I see in tutorials about recursion and very legitimate sources. I feel the reasoning for this is to use only one function call and as little code as possible to make an "elegant", or at least readable solution. The solution I found, while it is not the prettiest thing, it is far more efficient and very fast and after taking some time to really read it, makes far more sense true to the derivation of Fibonacci numbers. So here is the solution I found and converted to Haskell.

fib :: Integer-> Integer
fib 0 = 0
fib n =
        fib2 1 _ n2 = n2
        fib2 x n1 n2 = fib2 (x - 1) n2 (n1 + n2)
        fib2 n 0 1

Credit to the solution here. Glad to see people finding valid recursive solutions and letting people like myself know there's a better way.

1 comment:

  1. There’s a really generous welcome bonus on offer that provides you a lot as} $1,500 with a 250% deposit match or a lot as} $2,500 코인카지노 with a 350% deposit match should you use crypto. Subsequent offers and promos embody refer-a-friend bonuses, weekly mystery rewards, and Cafe Casino Perks . Speaking of beginners and new players – has a generous welcome offer of a lot as} $5,000 on the table these who|for many who|for people who} enroll with the on line casino. Other than that, have the ability to|you possibly can} play a handful of American and European Roulette variants at Wild Casino, and high rollers are welcome at this online on line casino. The table limit begins from around $1 and goes as high as $1,000, and you'll play on desktop and on cell. VIP members, however, get access to video games that begin staking as a lot as $90,000.


Tag Cloud

.NET (2) A+ (5) ad ds (1) addon (4) Android (4) anonymous functions (1) application (9) arduino (1) artificial intelligence (1) backup (1) bash (6) camera (2) certifications (3) comptia (5) css (2) customize (11) encryption (3) error (13) exploit (5) ftp (1) funny (4) gadget (4) games (3) GUI (5) hardware (16) haskell (6) help (14) HTML (3) imaging (2) irc (1) it (1) java (2) javascript (13) jobs (1) Linux (19) lua (1) Mac (4) malware (1) math (6) msp (1) network (13) perl (2) php (3) plugin (2) powershell (8) privacy (2) programming (24) python (10) radio (2) regex (3) repair (2) security (16) sound (2) speakers (2) ssh (1) story (5) Techs from the Crypt (5) telnet (1) tools (13) troubleshooting (11) tutorial (9) Ubuntu (4) Unix (2) virtualization (2) web design (6) Windows (16) world of warcraft (1) wow (1) wx (1)