Finding $x$ such that $y=x(x+1)(x+2)cdots(x+k-1)$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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).
binomial-coefficients
asked Aug 18 at 0:03
Zeda
214
add a comment |Â
up vote
1
down vote
favorite
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).
binomial-coefficients
asked Aug 18 at 0:03
Zeda
214
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0: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 at 1:37
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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).
binomial-coefficients
asked Aug 18 at 0:03
Zeda
214
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).
binomial-coefficients
asked Aug 18 at 0:03
Zeda
214
edited Aug 18 at 1:40
asked Aug 18 at 0:03
Zeda
214
asked Aug 18 at 0:03
Zeda
214
asked Aug 18 at 0:03
Zeda
214
214
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0: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 at 1:37
add a comment |Â
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0: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 at 1:37
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0:34
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0: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 at 1:37
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 at 1:37
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
1
down vote
Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $log y = sum_i=1^klog(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 frac1x+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 frac1x+i-1right)^-1left(sum_i=1^k log(x+i-1)-log yright).$$
For assistance finding an initial guess, note that for large $xgg k$
$$log y = sum_i=1^klog(x+i-1) approx klog(x+k-1)$$
so, solving for $x$,
$$
x approx y^1/k+1-ktext and we can take x_0 = max0, y^1/k + 1 - k.
$$
answered Aug 18 at 1:41
cdipaolo
677311
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 at 1: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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $log y = sum_i=1^klog(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 frac1x+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 frac1x+i-1right)^-1left(sum_i=1^k log(x+i-1)-log yright).$$
For assistance finding an initial guess, note that for large $xgg k$
$$log y = sum_i=1^klog(x+i-1) approx klog(x+k-1)$$
so, solving for $x$,
$$
x approx y^1/k+1-ktext and we can take x_0 = max0, y^1/k + 1 - k.
$$
answered Aug 18 at 1:41
cdipaolo
677311
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 at 1: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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
add a comment |Â
up vote
1
down vote
Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $log y = sum_i=1^klog(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 frac1x+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 frac1x+i-1right)^-1left(sum_i=1^k log(x+i-1)-log yright).$$
For assistance finding an initial guess, note that for large $xgg k$
$$log y = sum_i=1^klog(x+i-1) approx klog(x+k-1)$$
so, solving for $x$,
$$
x approx y^1/k+1-ktext and we can take x_0 = max0, y^1/k + 1 - k.
$$
answered Aug 18 at 1:41
cdipaolo
677311
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 at 1: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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $log y = sum_i=1^klog(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 frac1x+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 frac1x+i-1right)^-1left(sum_i=1^k log(x+i-1)-log yright).$$
For assistance finding an initial guess, note that for large $xgg k$
$$log y = sum_i=1^klog(x+i-1) approx klog(x+k-1)$$
so, solving for $x$,
$$
x approx y^1/k+1-ktext and we can take x_0 = max0, y^1/k + 1 - k.
$$
answered Aug 18 at 1:41
cdipaolo
677311
Assuming $x>0$ and taking logarithms this becomes finding $x$ such that $log y = sum_i=1^klog(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 frac1x+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 frac1x+i-1right)^-1left(sum_i=1^k log(x+i-1)-log yright).$$
For assistance finding an initial guess, note that for large $xgg k$
$$log y = sum_i=1^klog(x+i-1) approx klog(x+k-1)$$
so, solving for $x$,
$$
x approx y^1/k+1-ktext and we can take x_0 = max0, y^1/k + 1 - k.
$$
answered Aug 18 at 1:41
cdipaolo
677311
edited Aug 18 at 2:05
answered Aug 18 at 1:41
cdipaolo
677311
answered Aug 18 at 1:41
cdipaolo
677311
answered Aug 18 at 1:41
cdipaolo
677311
677311
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 at 1: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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
add a comment |Â
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 at 1: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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
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 at 1:49
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 at 1: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 at 1:50
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 at 1:50
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
@Zeda You could also use a better Stirling-flavor approximation $log y approx int_x^x+k-1log(t),dt = xlog 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 at 2:11
1
1
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
In my current case, $y=2nchoose n$, so my initial guess for the binary search was $x=k2^frac2n-k+.5k$ and that seems to be a pretty good initial guess.
– Zeda
Aug 18 at 2:22
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2886298%2ffinding-x-such-that-y-xx1x2-cdotsxk-1%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Would you not need to provide $y$ and $k$?
– mvw
Aug 18 at 0: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 at 1:37