Recursion with exponents

[doburomirushii nikku]

I'm trying to do a recursion that will find log 2^8 and return 3. Also if it gets log 2^15 it should return 3 also (so it rounds it down). Then I want to design a similar recusion method that will only find a perfect log such as log 2^8 = 3, but return -1 for log 2^15.

Here is my code for it.

public static int floorLog(int base, int value)
{
if (value == 1)
{
return 0;
}
 
if (base == value)
{
return 1;
}
else
{
return 1 + floorLog(base * base, value);
}
}    

I know you need a base case for recusion so that would be if the value was 1...then whatever the base is would have to be rasied to the 0 power. Then there is also if base == value...The method would return 1.

But I'm now really sure how my recursion case should go. I understand that what I'm doing is going to do 2, then 2 * 2, then 4 * 4, ect., which is incorrect. So how can I preserve the base value?

I think I want the method to do this:

1 + floorLog(2, 8)
1 + floorLog(2 * 2, 8)
1 + floorlog(2 * 2 * 2, 8)
At this point I want it to return in my base case...I'm just not sure how to translate it recursively.

Thanks.

Edit: I forgot...I need to do it without importing java.math
[ April 10, 2006: Message edited by: doburomirushii nikku ]

[Rusty Shackleford]

You when say log 2^8 do you mean log 256, 2^8= 256

Or log(base 8) 2?

log 2^8 ~=2.408 rounded down is 2.

log(base2) 8 is 3.
I am just curious about your notation.

public static int floorLog(int base, int value){
if (value == 1)
{
return 0;
}
if (base == value)
{
return 1;
}
else
{
return 1 + floorLog(base * base, value);
}
}

Just a few thoughts off the top of my head. I gotta get to class, sorry for the lack of details.

That looks like infinite recursion to me, value stays the same, while base base increases and there is no guarantee that it will ever equal value. You need a value that changes each recursive call that is used for the exit condition.

Google for the power series of log and use the fact that log(base n) x <==> log(base 10) x/log(base n). Hopefully that can point you in the right direction.
[ April 10, 2006: Message edited by: Rusty Shackleford ]

[doburomirushii nikku]

Yeah I mean log(base 8) 2. Thanks for the reply...I will look that up and see if it helps.

Edit: Figured it out...

 public static int floorLog(int base, int value)
{
if (value == 1)
{
return 0;
}
 
if (base == value)
{
return 1;
}
                if (value < base) 
                {
                        return 0;
                }
else
{
value = value / base;
 return 1 + floorLog(base, value);
}
}   

[ April 10, 2006: Message edited by: doburomirushii nikku ]

[Rusty Shackleford]

Good job.

I should have mentioned that when using power series it gives a way to figure it out to as many decimal places as you need, and is a bit of a heavyweight solution for your specific problem. Sorry about that. However, if the next assignment adds to it, by letting the accuracy be determined at runtime, you have the tools to do that.