Staredit Network > Forums > Null > Topic: SEN Q Challenge
SEN Q Challenge
Oct 4 2009, 10:09 pm
By: CecilSunkure  

Oct 7 2009, 8:46 am MillenniumArmy Post #21



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.
I'm not sure if I understand your instructions thoroughly so I went ahead and did this my way (which may or may not be the way you wanted us to do it.)


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);
   }
}


Post has been edited 1 time(s), last time on Oct 7 2009, 10:43 pm by MillenniumArmy.



None.

Oct 7 2009, 9:53 pm Vrael Post #22



Quote from Vrael
i.e. with pencil and paper and no calculator

Quote from Vrael
You have found this way an algorithm using only multiplication and division for computing log_a (b) with arbitrary precision

You're on the right track though, but nope :)



None.

Oct 7 2009, 9:55 pm Centreri Post #23

Relatively ancient and inactive

Technically, this isn't a calculator, and for all you know he might've used a pencil and paper at some point.



None.

Oct 7 2009, 10:00 pm Vrael Post #24



It doesn't matter Centreri, there are other things wrong with his solution. Not only that, but computers do calculations, and are therefore calculators.

Also, note that the solution is practically given to you in the problem I gave. However, also note that it completely possible to solve this problem without using the solution given and simply by thinking about this in the correct manner, which is how I did it since I found the "solution" a bit confusing in terms of x1 = n1 + y1, so you can think about it on your own. I simply gave the exact text of the problem as it was given to me.

Basically the problem asks you to find an algorithm for computing with arbitrary precision (note that this means it could be to 3 decimal places, or 3000 decimal places), using only integer operations, the value of a logarithm.

Hint: 3 + 5^-1 = 3.2 = approximately 3.169, 3 < 3 + (5 + kappa)^-1 < 3.2
Hope I haven't given it completely away with this hint :D

Post has been edited 3 time(s), last time on Oct 7 2009, 10:08 pm by Vrael.



None.

Oct 7 2009, 11:22 pm MillenniumArmy Post #25



Well i tried explaining it in the crossed-out section: At least when you get the integer value you simply divide your given value by the base until it's less than the base

9/2 = 4.5
4.5/2 = 2.25
2.25/2 = 1.125

3 iterations.
(for b = 9 and a = 2 it should be 3. And I changed the code I wrote a bit to make it easier to understand.)

Now for the fractional part... well it's hard to explain so I'll show you how I got it using your hint.

x = n + y
We know that n = 3 from the above steps so now we have to find the fractional value. We can express y in the form of:
y = 1/k

So let's begin: we'll guess k = 2.

x = 3 + 2^-1 = 3.5 Nope, too big. therefore we must increase our k value:
x = 3 + 3^-1 = 3.33 Still too big
x = 3 + 4^-1 = 3.25 Still too big
x = 3 + 5^-1 = 3.2 Still too big
x = 3 + 6^-1 = 3.167 Now it's too small. decrease our k value:
x = 3 + 5.9^-1 = 3.16949 Still too small
x = 3 + 5.89^-1 = 3.16978 Still too small
x = 3 + 5.889^-1 = 3.16981 Still too small
x = 3 + 5.8849^-1 = 3.169926422

I stop there because I believe it's precise enough.



None.

Oct 7 2009, 11:39 pm Vrael Post #26



Also on the right track, but not precisely the expression, since all what you have is a succession of guesses, and you're using the answer to find your guess. If you don't know the answer is 3.169..., your method won't work.

The correct answer will never deviate from the exact value of the logarithm in question algebraically.

Second hint: examine 'kappa' from the first hint more in-depth.
Quote from name:MilleniumArmy
Well i tried explaining it in the crossed-out section: At least when you get the integer value you simply divide your given value by the base until it's less than the base

9/2 = 4.5
4.5/2 = 2.25
2.25/2 = 1.125

3 iterations.
Also, examine this process more in depth and try to relate it to a logarithm. Ask yourself what is a logarithm, what does it relate? log_q (G) = c, in the general case. How can we use this knowledge to get integers? How do these integers relate to the logarithm?

You're on the right track though. Think of yourself as Aristotle or Plato or Pythagoras or something, all you have available to you is your knowledge and those operations which you can carry out by hand, you don't have the magical calculator to provide your answer then find the method, you need the method first to find the answer.



None.

Oct 25 2009, 12:26 am Vrael Post #27



Hint:
1 = 1/2 + 1/4 + 1/8 + 1/16 + 1/32 + 1/64 + . . . + 1/2n, n -> infinity

1 = 9/10 + 9/100 + 9/1000 + 9/10^4 + 9/10^5 + . . . + 9/10^n, n -> infinity



None.

Mar 2 2010, 4:34 am Aristocrat Post #28



Didn't anyone here take Calc BC? Sheesh. XD

I'll post the solution if no one gets it by Friday.



None.

Mar 2 2010, 4:47 am EzTerix Post #29



oh great if I have problems with my math homework I can just PM u guys :D



None.

Mar 5 2010, 7:44 am Rantent Post #30



You don't even need paper or pencil. My inspection from the definition.
log_2 (9) = x => 2^x = 9
2^3 = 8
So just a little more than three.
One can assume that 2^3.5 would be a little less than halfway between 8 and 16, probably 11.5 or something.



None.

Mar 5 2010, 8:37 am O)FaRTy1billion[MM] Post #31

👻 👾 👽 💪

Now how do you get the arbitrary precision out of that? ;o



TinyMap2 - Latest in map compression! ( 7/09/14 - New build! )
EUD Action Enabler - Lightweight EUD/EPD support! (ChaosLauncher/MPQDraft support!)
EUDDB - topic - Help out by adding your EUDs! Or Submit reference files in the References tab!
MapSketch - New image->map generator!
EUDTrig - topic - Quickly and easily convert offsets to EUDs! (extended players supported)
SC2 Map Texture Mask Importer/Exporter - Edit texture placement in an image editor!
\:farty\: This page has been viewed [img]http://farty1billion.dyndns.org/Clicky.php?img.gif[/img] times!

Mar 6 2010, 2:10 am Aristocrat Post #32



http://en.wikipedia.org/wiki/Power_Series

*coughcoughcoughhackwheezecough*



None.

Mar 6 2010, 7:53 pm Vrael Post #33



Quote from Rantent
You don't even need paper or pencil. My inspection from the definition.
log_2 (9) = x => 2^x = 9
2^3 = 8
So just a little more than three.
One can assume that 2^3.5 would be a little less than halfway between 8 and 16, probably 11.5 or something.
False.

Quote from name:doomedrusher
http://en.wikipedia.org/wiki/Power_Series

*coughcoughcoughhackwheezecough*
Also false, unless perhaps you have some other explanation for how this could work. So far Millenium Army has come the closest, perhaps read over what he's done and the hints I've given.

Quote from Rantent
You don't even need paper or pencil.
Actually, this method involves a lot of 1/x calculations, so you'd be doing a lot of long division if you actually had to find the numerical solution... unless your brain is super advanced and can find 1/x without paper and pencil :)

All this question is really asking for is the method to find this to arbitrary precision though. Perhaps I should just post the answer, it's been months and no one has gotten it.



None.

Mar 6 2010, 9:44 pm Aristocrat Post #34



Quote from Vrael
Quote from name:doomedrusher
http://en.wikipedia.org/wiki/Power_Series

*coughcoughcoughhackwheezecough*
Also false, unless perhaps you have some other explanation for how this could work. So far Millenium Army has come the closest, perhaps read over what he's done and the hints I've given.






:unsure:



None.

Mar 7 2010, 6:00 am Vrael Post #35



Well this isn't the solution I was looking for, but it certainly works and fulfills the criteria of the problem. Nice :)

Here was the real solution, I think a lot of you guys started on the right track:

log_2 (9) = log_2 ( 2^3 * 9/(2^3) )

=log_2(2^3) + log_2 (9/8)
= 3 + log_2 (9/8)
Here's the step everyone missed:
= 3 + ( log_(9/8) (2) )^(-1)
then we can pull a power of 9/8 out of 2, since 9/8 is less than 2
= 3 + (log_(9/8) ( (9/8)^5 * 2 /(9/8)^5 )) ^ -1
= 3 + ( 5 + log_(9/8) (65536/59049) ) ^ -1,
then rinse, repeat,
= 3 + ( 5 + (log_(65536/59049) (9/8))^-1 )^-1
and as you can see, each time you pull out a value and invert the log, you'll be left with a new value, which you can again pull the base of the logarithm out of, to get a new integer and a new logarithm that you can invert, and continue this process as long as you like. Algebraically, it will never deviate from the exact value of the logarithm. Numerically, you're going to be doing a shit ton of long division if you have no calculator :)



None.

Options
  Back to forum
Please log in to reply to this topic or to report it.
Members in this topic: None.
[10:29 pm]
Oh_Man -- homeworld 3 = massive disappointment
[10:05 am]
Moose -- ya
[05:23 am]
zsnakezz -- yes
[2024-5-12. : 8:51 pm]
l)ark_ssj9kevin -- Are you excited for Homeworld 3?
[2024-5-12. : 8:44 pm]
l)ark_ssj9kevin -- Hi Brusilov
[2024-5-12. : 4:35 pm]
O)FaRTy1billion[MM] -- Brusilov
Brusilov shouted: Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
my server that was hosting it died
[2024-5-10. : 8:46 pm]
NudeRaider -- Brusilov
Brusilov shouted: Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
https://armoha.github.io/eud-book/
[2024-5-10. : 8:36 am]
Brusilov -- Hey, what happened to EUDDB? Is there a mirror for it somewhere? Need to do a little research.
[2024-5-09. : 11:31 pm]
Vrael -- :wob:
[2024-5-09. : 8:42 pm]
Ultraviolet -- :wob:
Please log in to shout.


Members Online: Vrael, Roy