1

My motivation is that I am looking for some given number $y$ in Pascal's triangle by searching the diagonals (essentially iterating through $k$, omitting division by $k!$. Currently, I am taking advantage of the fact that the diagonals are monotonic, so I can take an upper and lower bound, evaluate at the middle and readjust the bounds as needed (binary search).

This works fine, but if I can directly computer the function inverse, that would be a lot faster.

I tried applying Newton's method as well, which would be much faster than binary search, but it seems like computing the derivatives is non-trivial (given arbitrary $k$).

So my question is, is there an easy way to find $x$, given $y=x(x+1)(x+2)\cdots (x+k-1)$?

(Sorry for any errors, on mobile).

Zeda
  • 151
  • Would you not need to provide $y$ and $k$? – mvw Aug 18 '18 at 00:34
  • Yes, $y$ and $k$ are known and I want to solve for $x$. For example, in one instance I have $y=210$ and $k=3$, so then I would determine $x$ to be 5. – Zeda Aug 18 '18 at 01:37

1 Answers1

1

Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $\log y = \sum_{i=1}^{k}\log(x+i-1)$ or $$f(x) = \sum_{i=1}^k \log(x+i-1)-\log y=0.$$The derivative $$f'(x) = \sum_{i=1}^k \frac{1}{x+i-1}$$ so we can find such an $x$ by iterating Newton's method with an initial guess $x_0>0$: $$x_{n+1} = x_n - \left(\sum_{i=1}^k \frac{1}{x+i-1}\right)^{-1}\left(\sum_{i=1}^k \log(x+i-1)-\log y\right).$$

For assistance finding an initial guess, note that for large $x\gg k$ $$\log y = \sum_{i=1}^k\log(x+i-1) \approx k\log(x+k-1)$$ so, solving for $x$, $$ x \approx y^{1/k}+1-k\text{ and we can take }x_0 = \max\{0, y^{1/k} + 1 - k\}. $$

cdipaolo
  • 1,146
  • While this isn't quite the easy approach I was hoping for, this is very clever; thanks! I know that AGM or Carlson's improvement on the Borchardt-Gauss algorithm can provide very fast computation of log, so this will help my speed bounds. – Zeda Aug 18 '18 at 01:49
  • No problem :) give me a second and I can try and come up with a decent initial guess using Stirling’s formula – cdipaolo Aug 18 '18 at 01:50
  • @Zeda You could also use a better Stirling-flavor approximation $\log y \approx \int_x^{x+k-1}\log(t),dt = x\log x - (x+k-1)\log(x+k-1) + 1- k$ as the initial guess but I couldn't invert this (don't have Mathematica access right now). – cdipaolo Aug 18 '18 at 02:11
  • 1
    In my current case, $y={2n\choose n}$, so my initial guess for the binary search was $x=k2^{\frac{2n-k+.5}{k}}$ and that seems to be a pretty good initial guess. – Zeda Aug 18 '18 at 02:22