This year programming competition in tech-fest at college, was organised by the friend with whom I team up for participating in competitions of other colleges. It was obviously better than previous years. I mean,questions were good, had considerable participants and most importantly, programming was supposed to be done using gcc/g++/java.
There was a question which asked to print the n^th term of Fibonacci series where 0<=n<=5000. Frankly such a large number does not fit in whatever predefined data type you can think of. Creating something like BigInteger of java would have been impossible during the competition and I am not an expert when it comes to java, so I skipped the problem. The coordinators accepted solution for 20 to 30 terms from other teams but demanded it for 5000 from me :P (being famous has its drawbacks !!!). Still I concentrated on other problems (got through this one but couldn't go to the finals because its timing clashed with another one :( ).
Later that night, after the competition was over, one of the coordinators pinged me on gtalk and asked sarcastically for the solution. This got on my nerves and I determined that I will smack the 5000th element on their face.
There was a bigint library I had created about an year ago which stored numbers in character arrays and manipulated them. I shuffled through my code directory, found it and quickly created a recursive function using memorisation to serve the purpose. The problem was that it worked fine for inputs upto 1302 but gave a segmentation fault for numbers above that. Puzzled and perplexed I resorted to Internet search and discovered that it was because of default stack size of 1MB allocated to every process. A few minutes later I stumbled upon the solution to increasing it which was as simple as adding
ulimit -s unlimited
to
/home/<user_name>/.bashrc
file and starting a new session. This increased the stack size to unlimited i.e now my program could use all the RAM available.
After this was done, my program successfully calculated and printed the sequence upto 7000 but ran out of RAM after this and gave Bus Error.
I redirected the output of the program to a text file, attached it to a mail and sent it to the coordinators ;)
Here is a screenshot showing a terminal window with the 7000th Fibonacci number and the state of my system while calculating it.
P.S: The code for my program is hosted at www.github.com/bhanuvrat/bigint .
Are you using a recursive algorithm for factorial algorithm? Coz the recurrence tree structure can get really bad!
ReplyDeleteusing a dynamic algorithm we can bring down the complexity from exponential to linear .
I am using recursion with memorisation .. what to do for DP?
ReplyDeleteWhy don't you use python?
ReplyDeletePython will handle all the *BIGINT* limits you mentioned above. Moreover, python code is so fast that you will forget that its an interpreted language.
Please use dynamic+iterative algorithm as its the most suitable programming methodology you can choose at this point. Its very important that the programmer not to assume much about the system's *CAPABILITIES* while writing the code. Its better not to use system stack. One cannot say at what time, which system can allocate how much memory to the process. Moreover, sometimes the execution environment of the system, the code may be running need not have enough memory to allocate to the *USER QUOTA* for the process. Most of the well configured servers that uses "cgroups" simply KILLS it[the process]. Hope you got what I meant.
@arjun
ReplyDeleteI did not use Python because the day I had written this code, I was fully unaware of the language, and even now I am still in the process of learning it.
Can you elaborate more on dynamic + iterative please?
As far as system's capabilities are concerned, my program just called a function recursively causing the system stack to be used. What wrong with that?
When the system's stack was exhausted I was curious on how to exceed its limit, thats when I went about exploring the possibilities.
Yes, I got what you meant, but this was just an experimental project not something I would deploy on a real time server :)