MathFest 2008, Madison WI
Using Recursion to Solve the Pill Problem
by Kaleb Waite (Waitek@rockhurst.edu)
Faculty Mentor: Dr. Keith Brandt
Rockhurst University
Thank you to those of you who came to my MathFest talk! Click here to view my power point presentation.
Welcome to the official (and as far as I know, the only) website dedicated to the pill problem!
What is the pill problem you ask? Well, although this should be common knowledge to all but the most uninformed type,
I shall nontheless give a brief description of it in case some of the details have become vague since the problem was presented to you...
THE PILL PROBLEM: Suppose you have a bottle of Tylenol tablets and every day you wake up with a splitting headache which can only be fixed by
half a tablet of Tylenol, but a whole tablet makes you feel drugged. So, being the type of person who doesn't like headaches OR feeling drugged, you decide
to take your Tylenol bottle and grab a tablet--if it's a whole tablet, you split it in half and put the remaining half back in the bottle, otherwise
you grab a half tablet and take it. So there you go, pill problem solved right? WRONG! You see, you also happen to be a mathematician, and all this pill
popping has presented a provoking probability problem which could potentially be processed by a recursive function!!! The problem provoked asks this question:
What are the odds on a given day that the tablet you grab will be a whole tablet?
THE PILL FUNCTION:
Where:
P[n]=The probability on day n that the tablet is whole
w = The initial number of whole pills in the bottle
h = The initial number of half pills in the bottle
THE PILL SOLUTION:
In order to explore the properties of this recursive function, I developed a java program which takes in the initial whole and half pill count and outputs
the probability after each successive day that a whole pill will be grabbed, the time it took to complete the computation, and the number of times the recursive function
was called. This program went through four main phases of development, each of which has its
advantages, and each of which is successively more effective at solving the problem for larger numbers of pills given the 'reasonable timeframe' for computation which we
set at a max of overnight on my computer (a Dell Inspiron 6000 with a 1.6 Ghz Pentium M processor and 512MB RAM).
The first phase of development was simply to enter the recursive function as it is presented above without modification. The advantage to this solution is its simplicity.
There's nothing fancy happening, the computer is just using the "plug-and-chug" method to compute the answer. The drawback of this method is that the time required to
follow the recursion increased exponentially as pills were added to the initial conditions. Under this method, the maximum number of initial whole pills
which could be solved overnight was 21. To view some output (in Excel format) from this function click here. The executable needed
to run this function is provided here, and the source code is here.
The second phase of development began when it was discovered that when tracing through the recursive function, a great majority of the calculations made were redundant.
Thus, in order to save on all the time which was being spent re-computing the same thing, it was decided to use a data
structure to store the output of the function call. The data structure which was implemented in this phase was a 3-dimentional array of doubles (floating point numbers).
Each time a value of the function was computed it was stored in the array at position Array[day][whole][half]. Thus, when the function was
called, it would first check if the value had already been computed and if so, use that instead of recalculating it. The advantage of doing this was that the time
it took to compute the probability values for all values dropped to negligible amounts, but because arrays (especially multi-dimensional ones) require allocation of large
amounts of RAM (memory), the method was confined by the maximum size of the array. The limits on the amount of memory (RAM) available to the program capped this
method's capacity at 253 whole pills (with extended default Java heap size of 256 MB). This method is the fastest method I found to get results because array lookups are very fast, but the
amount of memory wasted using the array was very high (because not every permutation of Array[day][whole][half] was actually computed during execution). To view some output (in Excel format)
from this function click here. The executable needed to run this function is provided here,
and the source code is here.
The third phase of development integrated a space-saving concept of combining the location information (the day, whole, half combination) and the probability into a single number so that storage and retrieval
could be based on one number rather than four and the problem of empty memory slots would disappear. To accomplish this, I used the formula: (day*1000000 + whole*1000 + half + probability). The scope of this
formula is limited to 3-digit inputs because if, for example, I started with 1000 half-pills, the program would understand that as 1 whole pill. So, the input to this method produced a number which looks like: dddd,www,hhh.ppp where
dddd is the day, www is the number of whole pills, hhh is the number of half pills, and ppp is the probability for that function call. As the program computed these numbers, they were added to a list with the
first function value computed entered at the head of the list and each subsequent one also added as the head. So, when the program would call the recursive function, it would first search through the list to see
if the value dddd,www,hhh (probability truncated) was in the list. So, as the number of functions computed increased, the search times also increased proportionally. This implementation allowed the computation of
around 400 initial whole pills within the 12-hour limit. This method's main advantage was saving on memory space--the list I implemented had very minimal space wasted on overhead functionality. To view some output (in Excel format)
from this function click here. The executable needed to run this function is provided here, and the source code is here.
The final phase of development brought one more data structure into play in order to minimize the linear increase in search times which was the bottleneck in the previous phase.
A self-balancing binary tree (utilizing Java's TreeMap class) was created to store the values of probability indexed with the dddd,www,hhh format. Because the binary tree allowed search times to
be reduced from linear complexity to logarithmic complexity, the execution time of this method was very quick and successfully solved the largest possible problem under the encoding: 999 initial whole pills.
This program gave the full solution (from day 1 till pills run out) for this case in less than an hour. The method could also be expanded to solve larger problems by using a larger maximum number to encode the
day, whole, and half values but it was decided that 999 pills was more than sufficient for the original goal of discovering the probability of a bottle of pills. To view some output (in Excel format)
from this function click here. The executable needed to run this function is provided here, and the source code is here.
NOTE: in order to use the executables, they must first be saved to your computer. The output file will be created in the same directory the program is run from--Also note that until the program finishes execution
(use the task manager [ctrl+alt+del] to see if the java process is still running) the output file will be empty so do not attempt to open it! If you wish to view the output as it is processed,
the program must be run from the command line. Navigate to where the file was downloaded to using the "cd" command, and use the command "java -Xmx512M -jar PhaseI.jar" to run the program. Eventually, I hope
to write a better interface to streamline user interaction through an applet available on the webpage. Until then, I'm sorry for the inconvenience... Contact me with any problems you have!
This webpage was Kaleb's first shot at HTML coding, many thanks to Dr. Brandt for his help in getting it up!!! There's no more to see here, but you can go back to the top and start over if you like... or feel
free to check out the RU Math & Physics Department's webpage for tons of fun stuff.