BP Forums
Knuth Numbers recursion - Printable Version

+- BP Forums (https://bpforums.info)
+-- Forum: Programming Discussion (https://bpforums.info/forumdisplay.php?fid=34)
+--- Forum: Java (https://bpforums.info/forumdisplay.php?fid=41)
+--- Thread: Knuth Numbers recursion (/showthread.php?tid=898)

Knuth Numbers recursion - Miriam - 04-21-2015

Hello,

I recently had a final exam on which my teacher asked to write a method for Knuth numbers recursion. I got a stack overflow on my implementation, and I am new on Java, so I am not sure what happened, it might be that I had the wrong formula for Knuth numbers? I would love some feedback.

Here is the question, and my code

Knuth numbers are given by the recursive formula Kn+1 = 1 + min (2 * Ka, 3 * Kb) where a is the smallest integer larger than n/2.0 and b is the smallest integer larger than n/3.0. The use of doubles in the denominator is necessary to ensure that integer division is not used.

For example, if n is 7, then a equals 4 and b equals 3 and thus K8 = 1 + min (2* K4, 3 * K3).

If n is 8, then a equals 5 while b remains 3 and thus K9 = 1 + min (2 * K5, 3 * K3).
If n is 9, then a remains 5 while b equals 4 and thus K10 = 1 + min(2 * K5, 3 * K3).

Mathematically, “the smallest integer larger than x” is the “ceiling” function. If n is an int, then n / 2 is calculated using integer division, discarding the remainder; but you want the division to give you a double. Thus you need code that looks like this:

int a = Math.ceil(n / 2.0);
int b = Math.ceil(n / 3.0);

Since the equation defining Knuth numbers is a recursive one, we must have a base case; let’s assume that K0 = 1.

Create and test a class called KnuthNumbers (in a project also called KnuthNumbers) which includes a static method to compute Knuth numbers.

my code:


Code:
public class KnuthNumbers
{
   /**
    * Recursive Knuth Numbers 1, 3, 3, 4, 7, 7, 7, 9, 9, 10, 13, ...  
    */
   public static int knuthNumber(final double n)
   throws DataFormatException{
       double a = Math.ceil(n / 2.0);
       double b = Math.ceil(n / 3.0);
       // bad input
       if (n < 1)
           throw new DataFormatException("n cannot be less then 1");
       if (n > 12)
           throw new DataFormatException("n is too large. Max is 12");
       //base case
       if (n == 1)
           return 1;

       //recursion

       return knuthNumber(a + b);
   }
}




TEST:

Code:
public class KnuthNumbersTest
{
   

   @Test
   public void testKnuthNumber(){
       long startTime = 0;
       long endTime = 0;
       double result = 0;

       try {
           assertEquals(-1, KnuthNumbers.knuthNumber(-3));
           fail("number should not be negative");
       }
       catch (DataFormatException e){
           assertEquals("n cannot be less then 1", e.getMessage());
       }
       catch (Exception e) {
           fail("Unexpected exception: " + e.toString());
       }

       try {
           assertEquals(0, KnuthNumbers.knuthNumber(0));
           fail("number should not be zero");
       }
       catch (DataFormatException e){
           assertEquals("n cannot be less then 1", e.getMessage());
       }
       catch (Exception e) {
           fail("Unexpected exception: " + e.toString());
       }

       try {
           assertEquals(1, KnuthNumbers.knuthNumber(1.0));
           assertEquals(9, KnuthNumbers.knuthNumber(5.4));
           assertEquals(13, KnuthNumbers.knuthNumber(7.6));
       }
       catch (Exception e) {
           fail ("Unexpected exception: " + e.toString());
       }

   }

}


RE: Knuth Numbers recursion - brandonio21 - 04-22-2015

Hey Miriam, good to see you here and welcome to BP Forums!


So I was looking into your problem, and I was having a lot of difficulty with it, too. That is, until I researched the definition of Knuth numbers. According to WolframAlpha, the Knuth numbers are actually defined as:

[Image: NumberedEquation1.gif]
That is, Kn+1 = 1 + min(2Ka, 3Kb) where:
a = floor(n/2)
b = floor(n/3)

Thus, using floor instead of ceil, we are able to simplify the algorithm to something like this:


Code:
public class KnuthNumbers
{
 public static int knuthNumber(final int n)
 {
   if (n == 0)
     return 1;

   int a = (n-1) / 2;
   int b = (n-1) / 3;

   return 1 + Math.min(2*knuthNumber(a), 3*knuthNumber(b));
 }
}

As you can see, there are a few things that have changed from your definition. I'll outline them below:
  • I have changed the parameter to an int because n will never be a double since it is an index.
  • The problem specifies the base case to be K0 = 1, so I changed the base case from what you had to match the base case in the problem.
  • Instead of using Math.ceil as specified in the problem, since Wolfram's definition specifies that it is floor instead, we can simply use integer division, which automatically gives us the floor value.
  • Your final return statement did not seem to match the definition of Knuth's numbers as given in the problem, so I changed that.
I realize that I left out your DataFormat statements, but I wanted to keep the answer as barebones as possible.

I hope this helped!