# Solve a polynomial of degree d

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.

-
$1+b+b^2+\ldots+b^d = (b^{d+1}-1)/(b-1)$ –  Raskolnikov Aug 1 '11 at 12:18
@Raskolnikov: That just turns it from a large $d$-degree polynomial into a simpler $(d+1)$-degree polynomial. :) Maybe it doesn't have an elementary solution - it might require hypergeometric functions for $d\ge 4$. Jeune, are you looking for exact analytical solutions? –  anon Aug 1 '11 at 12:58
@anon nope approximations will do –  Jeune Aug 1 '11 at 13:07
Ah, I should have figured, given it was an artificial intelligence class and all... –  anon Aug 1 '11 at 13:08

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.

-
+1 for the root finder. though I don't understand how the interpolation was done :| –  Jeune Aug 1 '11 at 15:27
Oops, it was $b=9, 10$, fixed. –  Ross Millikan Aug 1 '11 at 15:37
@Jeune: it is a standard linear interpolation (now fixed). The denominator is the increase in $N$ as $b$ goes from $9$ to $10$. The numerator is how far along the way we need to go to get to 1E6. –  Ross Millikan Aug 1 '11 at 15:41

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$$

-
My guess is that a proper error analysis would probably show that the method outlined in Remark 2 will almost always perform worse than than the naive estimate given by $\sqrt[d]{N} - 1/d$. –  Willie Wong Aug 1 '11 at 16:06