I was wondering whether there is a way to find intermediate digits of an algebraic equation. For example, if I have


And I want to find the $10^9$th decimal digit after the decimal place of a particular solution. (Note that I chose this example simply to demonstrate the lack of a simple closed-form solution, I am not looking for a specific solution to this particular equation.)

I was wondering if there is any time-efficient way to do this or do I have to calculate every digit before the targeted one?

  • $\begingroup$ There is a famous instance of the partial computation of the digits of a number with the BBP formula for $\pi$ (en.wikipedia.org/wiki/…). If you can express your number as a power series with small rational coefficients and evaluated at $1/10$, you can use the same working principle. $\endgroup$ – Yves Daoust Jan 23 '15 at 16:53
  • $\begingroup$ @YvesDaoust I think continued fractions might be more appropriate, given his equation and their good approximation properties. $\endgroup$ – cactus314 Jan 23 '15 at 17:13
  • $\begingroup$ @johnmangual: how do you evaluate a continued fraction without computing the digits from the beginning ? $\endgroup$ – Yves Daoust Jan 23 '15 at 17:20
  • $\begingroup$ @YvesDaoust that's the beautify of it. using the equation itself as information we deduce more and more continued fraction digits of our number. see Enrico Bombieri's continued fractions and algebraic numbers. our number is definitely algebric, e.g. let $x = z^{12345 \times 3456}$. $\endgroup$ – cactus314 Jan 23 '15 at 21:32
  • $\begingroup$ @johnmangual: is there an algorithm to compute the $n^{th}$ decimal in time linlogarithmic with respect to $n$ by continued fractions ? $\endgroup$ – Yves Daoust Jan 25 '15 at 17:54

In your particular case, I can't say very much, but notice this looks very much like Bezout's identity for the greatest common divisor.

$$ \mathrm{gcd}(a,b) = 1 \longleftrightarrow \exists \; x,y \in \mathbb{Z} : ax + by =1$$

We can clear denominators:

$$ \frac{234}{24621} - x^{\frac{1}{3456}- \frac{1}{12345}} = \frac{1}{24621 \times x^{\frac{1}{12345}}}$$

To simplify things let $y = x^{\frac{1}{12345}}$ and notice that $\frac{12345}{3456} \approx 3.5$ then

$$ \frac{1}{105} = y^{2.5} + \frac{1}{24621 \times y} $$

Then we get an upper and lower bound for $y$:

$$ y < \bigg(\frac{1}{105}\bigg)^{\frac{1}{2.5}}< 0.16 \hspace{0.25in}\text{and}\hspace{0.25in} y > \frac{105}{24621} = \frac{1}{234} > 0.004$$

Going back to our original equation:

$$ \bigg| \frac{1}{105} - y^{2.5}\bigg| = \frac{1}{24621 \times y} < \frac{1}{24621 \times \frac{1}{234}} = \frac{1}{105}$$

It may be very difficult to get the billion digit of $x$ this way, but we have much more to go on than we started.

This style of computation loosely resembles Halley's method for solving equations. It states if we want to solve $f(x) = 0$

$$x_{n+1} = x_n - \frac{2f(x_n)f'(x_n)}{2[f'(x_n)^2 - f(x_n)f''(x_n)} $$

incorporating idea of Newton's method of fluxions... We can also try to solve just using Newton-Raphson method:

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

In either case we use our work to start with the value $\boxed{y = \frac{1}{10}}$ (since I changed variables) and try to iterate either Newton or Halley's procedures. See On the geometry of Halley’s method

One of the original motivating examples of Sir Edmund Halley's method was to demonstrate the example of Thomas Fautet de Lagny:

$$ a + \frac{ab}{3a^3 + b} < (a^3 + b)^{1/3} < \frac{a}{2} + \sqrt{\frac{a^2}{4} + \frac{b}{3a}} $$

As long as $b \ll a^3$. This tells us for example that $3 + \frac{3}{82} < \sqrt[3]{28} < \frac{3}{2} + \sqrt{ \frac{9}{4} + \frac{1}{9}}$ which is decent.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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