Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
$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

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
    
+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 $$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.