Using a Binary Search to find a power constant

Question

I have been on this for 2 days.

I have the following equation

B-N*E = Sum N, i=1 (P1-E/i^a) sorry for the poor formatting.

I know:

• B = 10000
• N = 50
• E = 15
• P1 = 3000

So:

9250 = Sum N, i=1 (2985/i^a)

The tutorial I am reading states: We can efficiently solve this equation for α to additive error less than .01 via binary search.

But I am not sure how I do a binary search for the power constant...

Answer 1

I hope you're working with a computer, or some sort of technology.

You want to bracket the value of $a$ within some interval. For instance $a=0$ causes the sum to be too large, while $a=2$ causes the sum to be too small. So the correct value of $a$ lies between $0$ and $2$. You now bisect this interval (checking what happens if $a=1$). You will then replace your interval where $a$ lies with an interval half as large (either $[0,1]$ or $[1,2]$. You keep doing this until you get an interval that gives you the desired accuracy for $a$.

This method is also called the bisection method.

Answer 2

It is not very clear what you are trying to optimise.

What you need to do is calculate or guess a value of a which is too small and one that is too big. Having got those, try a value between them. If this is too big then try a value between the lower limit and the midpoint. If it is too small then try a value which is between between the midpoint and the upper limit. Now, you have restricted the range of possible answers; try the midpoint of those and repeat.

For example, let's try to find the square root of $2$ this way.

We can guess and then check that $1$ is too small.

We can guess and then check that $2$ is too big.

Now, we try $1.5$. $1.5^2 = 2.25$ so that is too big.

So, we know that the answer is between $1$ and $1.5$. So, we try $1.25$ next.

If you cannot guess an upper limit then one strategy is to make any guess and keep doubling it until it is too big. Let's suppose that we are trying to find the square root of $10$ but we have no idea what it is.

We start with $1$ and we find that it is too small.

So, we double it and try $2$ which is also too small.

So, we double it and try $4$ which is too big.

We now know that the answer is between $2$ and $4$ so we can return to the previous algorithm and try $3$. We find that $3$ is too small so we try $3.5$ etc.