Why is my program returning Nan for some values and not others?

Question

In Algorithms 4th Edition (Sedgewick) there is a question I have been attempting:

I have limited knowledge in maths and way out of practice. I was using this thread as I was having a hard time tracking down the equation to calculate logarithms (my poor search skills) and have implemented the program so far:

public class HelloWorld {
    static final int TAYLOR_ITERS = 20;

    public static void main(String[] args) {
        System.out.println(HelloWorld.lg(3));
        System.out.println(Math.log(3));
    }

    public static double lg(int n) {
        double answer = 0;
        for (int i = 1; i < TAYLOR_ITERS; i++) {

            double temp = (n - 1);
            int power = i;
            while (power != 1) {
                temp *= (n - 1);
                power--;
            }
            if (i % 2 == 0) {
                answer -= ((temp) / i);
            }
            else {
                answer += ((temp) / i);
            }
        }
        return answer;
    }

    public static double exercise(int n) {
        double answer = HelloWorld.lg(n) / HelloWorld.lg(2);
        return answer;
    }
}

Firstly, I apologise for any bad code structure/conventions, this is my first time using Java after using C and mostly Python. Without a power function I used a for loop to times temp by itself i-1 times, as when i==2 temp*temp = temp^2, and power then = 1, and the loop won't continue. I then use mod 2 to check whether i is odd or even, as I think that the series provided in the link above alternates between subtraction and addition for even/odd iterations.

Clearly there are some big differences between what Math.log() returns and my own log function, but I can't clearly see what is going wrong

Answer 1

First, the reason your code blows up is that the Taylor series for lg only works for values in the range between 0 and 2; above 2 -- which are nearly all the cases you want -- it diverges rapidly, quickly producing numbers larger than can be handled in the floating-point system Java uses. You can fix(?) this by instead computing the log of the reciprocal and negating it, but even there for values not close to one it converges very slowly, taking much more than the 20 iterations you allowed.

But the key is that you misread the assignment. It doesn't ask for the actual log-base-2; it asks for the largest integer not greater than the log-base-2. That's a very different thing; it is simply the position of the highest bit in the binary representation of n, and since Java (like essentially all computers in the last six decades) uses binary integers this is trivial; as commented by Guy just divide by 2 (or equivalently shift-right by 1) until you 'use up' all bits below the one that started out highest. Or slightly less obvious but even more efficient, you can do a binary search for the high bit.

The following code illustrates both (all) methods, and in the process shows how many iterations of Taylor are needed to get even a decent approximation that is still not quite correct for larger values and would need to be fudged.

public class SO78863494ilog2 {

    public static double abs (double x) { return x<0? -x: x; }

    public static double lg_taylor (double x) {
        if( x <= 0 || x > 2 ) throw new RuntimeException("invalid for lg_taylor"); 
        double t=0, p=1; track=0;
        for(int i = 1; abs(p *= x-1)/i>1e-9; i++){ t = i%2==0? t-p/i: t+p/i; track++; }
        // or t += (i%2==0?-1:+1)*p/i or more clever/sneaky (i%2*2-1)*p/i 
        return t;
    }
    public static int track;
    public static double lg_2 = -lg_taylor(1.0/2);
    public static double log2 (int n){ return -lg_taylor(1.0/n)/lg_2; }

    public static int ilog2 (int n){
        if( n <= 0 ) throw new RuntimeException("invalid for ilog2");
        int l=0; while(n>1){ n/=2; l++; } // or n>>=1;
        return l;
    }
    public static int ilog2opt (int n){
        if( n <= 0 ) throw new RuntimeException("invalid for ilog2");
        int l=0, t;
        if( (t=n>>16)>0 ){ n=t; l+=16; }
        if( (t=n>>8) >0 ){ n=t; l+=8;  }
        if( (t=n>>4) >0 ){ n=t; l+=4;  }
        if( (t=n>>2) >0 ){ n=t; l+=2;  }
        if( (t=n>>1) >0 ){ n=t; l+=1;  }
        return l;
    }

    public static void main(String[] args){
        int[] data = {3,4,15,16,63,64,255,256,1023,1024,4095,4096,16383,16384};
        for(int t : data) System.out.printf ("%5d: %f(%d) %d %d%n", t, log2(t), track, ilog2(t), ilog2opt(t));
    }
}

-->

    3: 1.584962(41) 1 1
    4: 2.000000(57) 2 2
   15: 3.906891(222) 3 3
   16: 4.000000(236) 4 4
   63: 5.977280(872) 5 5
   64: 6.000000(885) 6 6
  255: 7.994353(3218) 7 7
  256: 8.000000(3230) 8 8
 1023: 9.998589(11618) 9 9
 1024: 9.999999(11629) 10 10
 4095: 11.999642(41329) 11 11
 4096: 11.999995(41338) 12 12
16383: 13.999891(144821) 13 13
16384: 13.999979(144829) 14 14