0
$\begingroup$

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.

  • 0
    Ah, I should have figured, given it was an artificial intelligence class and all...2011-08-01

2 Answers 2

9

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.

  • 0
    @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.2011-08-01
8

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 $

  • 0
    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$.2011-08-01