In my Artificial Intelligence class, I encountered this equation where I have to solve for b, the effective branching factor of a tree:
N = 1 + b^1 + b^2 + .... + b^d
I have the number N, how do I solve for b?
I was given a hint that this could be solved using interpolation but I don't really understand how. My understanding of interpolation is where one tries to fit a function given some points. In this case, it's the other way around, there is a function but no points.
On
If you know how to take $d$th roots, you can use that
$$ b^d < 1 + b + b^2 + \cdots + b^d < (1+b)^d $$
to get
$$ \sqrt[d]{N} < (1+b) < 1 + \sqrt[d]{N} $$
which implies that
$$ \lfloor \sqrt[d]{N}\rfloor - 1 < b < \lceil \sqrt[d]{N}\rceil[d]{N} $$
(If you only care about integer parts of if integer arithmetic is faster) First compute $\lfloor\sqrt[d]{N}\rfloor = b'$. Check whether for this $b'$ the associated polynomial is bigger or less than $N$. If you underestimated, linearly interpolate between $b'$ and $b' + 1$. Else interpolate between $b'$ and $b'-1$.
If you can actually efficiently do floating point arithmetic and can take roots, then you can just linearly interpolate between $\sqrt[d]{N} - 1$ and $\sqrt[d]{N}$.
To do the example given by Ross: Say $N = 10^6$ and $d = 6$. Then $\sqrt[6]{N} = 10$. So we know that $9 < b < 10$.
For the value of 9, the polynomial yields 597871. And for the value of 10 the polynomial is 1,111,111. The linear interpolation gives
$$ 9 + \frac{10^6 - 597871}{1111111 - 597871} \sim 9.784 $$
with the correct value being around $9.822$.
A different way (again, assuming you know how to take $d$-th roots) is to use the estimate
$$ 1 + b + \cdots b^{d-1} + b^d - b^d \sim b^{d-1} $$
and
$$ (1+b)^d - (1 + b + \cdots b^{d-1} + b^d) \sim (d-1)b^{d-1} $$
which gives an estimate of roughly
$$ b = \sqrt[d]{N} - 1/d $$
(in fact this is an upper bound: see Remark 2 below)
Remark 1 In the demonstration case above this would give $9.833$. This estimate degenerates badly when $\sqrt[d]{N}$ decreases and gets closer to (or less than) $d$, because then the lower order corrections can be numerically larger. So we see that for $\sqrt[d]{N}$ sufficiently larger than $d$, this single estimate should perform better than linear interpolation.
Remark 2 We have also the identity
$$ (b+ 1/d)^d = b^d + b^{d-1} + \sum_{k = 1}^{d-2} \frac{1}{d^{d-k}}{d \choose k} b^k $$
which, appealing to the fact that $\frac{1}{d^{d-k}}{d \choose k} \leq 1$, you have
$$ (b+1/d)^d < 1 + b + \cdots + b^d < (b+1)^d $$
Unfortunately, this won't improve the results from the linear interpolation by much as the main difficulty is obtaining a better upperbound other than $(b+1)^d$. For example, we can improve the upperbound slightly by using the fact that
$$ \frac{1}{d^{(d-k)/(d-1)}} { d \choose k} \geq 1$$
whenever $k >0$. Which implies that
$$ \left( b + \frac{1}{d^{1/(d-1)}}\right)^d + 1 \geq b^d + b^{d-1} + \cdots + b + 1 $$
which implies that
$$ \sqrt[d]{N-1} - \frac{1}{\sqrt[d-1]{d}} < b < \sqrt[d]{N} - \frac{1}{d} $$
In the case $N = 10^6$ and $d = 6$. The upper and lower bounds are 9.83333 and 9.30117. Their corresponding polynomial evaluations are around 1006423 and 725477. Linear interpolation gives
$$ b \sim 9.83333 - \frac{6423}{1006423 - 725477} \sim 9.8104 $$
As Raskonkikov says, $1+b+b^2+\ldots+b^d = (b^{d+1}-1)/(b-1)$. You can now generate values of the RHS for various $b$ until they get greater than $N$-it won't take long. Say $N=1{,}000{,}000, d=6.\ \ $ You find that $b=9$ gives $N=597{,}871$, while $b=10$ gives $N=1{,}111{,}111$. A linear interpolation gives $b=9+\frac{1{,}000{,}000 - 597{,}871}{1{,}111{,}111-597{,}871}\approx 9.784$ For a more exact answer, you can submit this to a root finder. Wolfram Alpha gives 9.823.