Quote from Vrael
Category: Math
The approximate value of log_2 (9), which you can obtain with a calculator, is 3.16993. . . Explain how you can figure out that 3 < log_2 (9) < 3.5 by integer multiplication or division (i.e. with pencil and paper and no calculator, reducing it to a computation with integers.)
Write x1 = log_2 (9) = n1 + y1 where n1 is the integer part of x1 and y1 is in (0,1) is the fractional part. Explain how you get the integer n1 by integer multiplication and division.
Define x2 = 1/y1. Interpret x2 as a logarithm.
Note that x2 > 1 so you can decompose x2 again into its integer and fractional part x2 = n2 + y2. How do you get n2 by integer multiplication and division?
You can now continue with x3 = 1/y2 and so on. After k steps you get bored and stop. How do you get an approximate value of x1 = log_2(9) from the integers n1, n2,..,nk, starting with the case k = 2?
You have found this way an algorithm using only multiplication and division for computing log_a (b) with arbitrary precision.
Edit: Note that log_2 (9) is simply the example given. The correct answer is a method that will work for any log_a (b).
Hint: the answer shares some similarity with infinite series, almost like an Euler product.
The approximate value of log_2 (9), which you can obtain with a calculator, is 3.16993. . . Explain how you can figure out that 3 < log_2 (9) < 3.5 by integer multiplication or division (i.e. with pencil and paper and no calculator, reducing it to a computation with integers.)
Write x1 = log_2 (9) = n1 + y1 where n1 is the integer part of x1 and y1 is in (0,1) is the fractional part. Explain how you get the integer n1 by integer multiplication and division.
Define x2 = 1/y1. Interpret x2 as a logarithm.
Note that x2 > 1 so you can decompose x2 again into its integer and fractional part x2 = n2 + y2. How do you get n2 by integer multiplication and division?
You can now continue with x3 = 1/y2 and so on. After k steps you get bored and stop. How do you get an approximate value of x1 = log_2(9) from the integers n1, n2,..,nk, starting with the case k = 2?
You have found this way an algorithm using only multiplication and division for computing log_a (b) with arbitrary precision.
Edit: Note that log_2 (9) is simply the example given. The correct answer is a method that will work for any log_a (b).
Hint: the answer shares some similarity with infinite series, almost like an Euler product.
To find the logarithm of 9 in base 2, we solve for the integer (n1) and fractional (y1) parts of the answer (x1.)
We first find the integer part by dividing our variable by the base. We divide our result again by the base until the answer is no longer larger than the base value:
9/2 = 4.5
4.5/2 = 2.25
2.25/2 = 1.125
We stop there because 1.125 < 2. This took three iterations, therefore our integer value (n1) is 3.
For the fractional part, we square the very last value we got from our previous step m = (1.125)^2 = 1.12652625
we also begin with a number n = 0.5
First we want to make sure that m > base. But as we can see it is not greater than our base so we must run some iterations by squaring m and dividing n by 2 until m > base. Here's how it would look:
m = 1.12652625^2 = 1.6018, n = 0.5/2 = 0.25
m = 1.6108^2 = 2.56578, n = 0.25/2 = 0.125
With that, we can move on. Now we will run another series of iterations until m is less than our base value: divide m by our base, divide n by 2, and square m. For these series we take the summation of our m values (before we divide each one by two) and this will give us our fractional part of the answer. And then you...
...
ah fuck it, I'll just show you the code I wrote:
vraelSux.java
import java.io.*;
import java.util.*;
public class vraelSux {
public static void main(String[] args) {
// Used for the final answers
int integer = 0;
double fraction = 0;
double partial= 0.5;
double finalAnswer;
double x;
Scanner sc = new Scanner(System.in);
System.out.println("Damnit Vrael you suck nuts cuz you made me actually code this out");
// I am going to assume that you will enter *valid* values.
// As in, neither of your values will be less than 1.
// And, let's please make life simple and assume that our desired calculated value will be an integer
System.out.println("");
System.out.print("Enter a base: ");
int a = sc.nextInt();
System.out.print("Enter the value you want calculated: ");
int b = sc.nextInt();
// used for the purposes of our iterations
x = (double)b;
// Let the games begin
// This while loop gives us our integer value
while ( x >= a ) {
integer++;
x = x / a;
}
// This while loop gives us our fractional value
// Assume a precision of 10^-10
while ( partial> 0.0000000001 ) {
if ( x >= a ) {
fraction += partial;
x = x / a;
}
partial*= 0.5;
x *= x;
}
// Combine the integer and fraction values to get our answer
finalAnswer= integer + 2*fraction;
System.out.println("");
System.out.print ("log" + b + "(" + a + ") = " + finalAnswer);
}
}
import java.util.*;
public class vraelSux {
public static void main(String[] args) {
// Used for the final answers
int integer = 0;
double fraction = 0;
double partial= 0.5;
double finalAnswer;
double x;
Scanner sc = new Scanner(System.in);
System.out.println("Damnit Vrael you suck nuts cuz you made me actually code this out");
// I am going to assume that you will enter *valid* values.
// As in, neither of your values will be less than 1.
// And, let's please make life simple and assume that our desired calculated value will be an integer
System.out.println("");
System.out.print("Enter a base: ");
int a = sc.nextInt();
System.out.print("Enter the value you want calculated: ");
int b = sc.nextInt();
// used for the purposes of our iterations
x = (double)b;
// Let the games begin
// This while loop gives us our integer value
while ( x >= a ) {
integer++;
x = x / a;
}
// This while loop gives us our fractional value
// Assume a precision of 10^-10
while ( partial> 0.0000000001 ) {
if ( x >= a ) {
fraction += partial;
x = x / a;
}
partial*= 0.5;
x *= x;
}
// Combine the integer and fraction values to get our answer
finalAnswer= integer + 2*fraction;
System.out.println("");
System.out.print ("log" + b + "(" + a + ") = " + finalAnswer);
}
}
Post has been edited 1 time(s), last time on Oct 7 2009, 10:43 pm by MillenniumArmy.
None.