/*\nAlgorithm 1.2.2L: Binary approximation of y = logb x\n\nSuppose that we have a binary computer and a number x, 1 <= x < 2.\nShow that the following algorithm, which uses only shifting addition, \nand subtraction operations proportional to the number of place of \naccuracy desired, may be used to calculate an approximation to \ny = logb x.\n\nL1. [Initialize]  Set y <- 0, z <- x shifted right 1, k <- 1.\nL2. [Test for end]  If x == 1, stop.\nL3. [Compare]  If x - z < 1, go to L5.\nL4. [Reduce values]  Set x <- x - z, z <- x shifted right k, \n                     y <- y + logb (2^k/(2^k - 1)), and go to L2.\nL5. [Shift]  Set z <- z shifted right 1, k <- k + 1, and go to L2.\n*/\n\npublic class Test {\n\n   // desired precision in bits\n   static long precision = 5;\n\n   // the log base\n   static long base = 10;\n\n   // convert double to binary representation\n   // (implied decimal places)\n   //   example: double2binary(1.5) = 150000\n   static long double2binary(double x)\n   {\n      return (long)(x * Math.pow(10, precision));\n   }\n\n   // convert binary back to double\n   // (backing out implied decimal places)\n   //    example: binary2double(150000) = 1.5\n   static double binary2double(double x)\n   {\n      return x / Math.pow(10, precision);\n   }\n\n   // shift right operation\n   //    example: shiftRight(12340) = 1234\n   static long shiftRight(long x, long n)\n   {\n      if (n == 0)\n      {\n         return x;\n      }\n      else\n      {\n         return shiftRight(x / base, n-1);\n      }\n   }\n\n   // mimic a fixed log table that is precision in length.\n   // eventually I'll convert to a lookup table.\n   static long logTable(long k)\n   {\n      return double2binary(\n         Math.log(Math.pow(2, k) / (Math.pow(2, k) - 1.0)) /\n            Math.log(base));\n   }\n\n   // test out the algorithm\n   public static void main(String[] args) {\n      // L1. Initialize values\n      long x = double2binary(1.5);\n      long y = 0;\n      long z = shiftRight(x, 1);\n      long k = 1;\n\n      // used to prevent infinite loop till I get it working\n      long i = 1;\n\n      // L2. Test x == 1.\n      while (x != 1)\n      {\n         i = i + 1;\n         if (i > 50) break;\n         System.out.println(i + ", " + k + ", " +\n            x + ", " + y + ", " + z);\n\n         // L3.  Compare\n         if ((x - z) >= 1)\n         {\n            // L4. Reduce values *)\n            x = x - z;\n            z = shiftRight(x, k);\n            y = y + logTable(k);\n         }\n         else\n         {\n            // L5. Shift\n            z = shiftRight(z, 1);\n            k = k + 1;\n         }\n      }\n\n      System.out.println("result = " + binary2double(y));\n      System.out.println("should = " + (Math.log(1.5) / Math.log(base)));\n   }\n}