1

For a positive real number $x$, and an integer $n$, i'd like to compute $\lfloor x^n \rfloor$. The $n$ here will be quite large, so I want to know how precise my approximation of $x$ needs to be to guarantee $\lfloor x^n \rfloor$ takes on the correct value. I've come up an equation that solves for this:

$$\min_m \quad x^n - (x-\frac{1}{10^m})^n < 1$$

This guarantees $\lfloor (x-\frac{1}{10^m})^n\rfloor$ to be either $\lfloor x^n \rfloor$ or $\lfloor x^n \rfloor - 1$ (to prove this just re-arrange the above expression, and note $x^n$ is strictly larger than the approximation.) Is there an efficent way to calculate the minimum $m$ here? Or is there a better method altogether that guarantees $\lfloor x^n \rfloor$? I've noticed that lowering the value of the RHS increases the probability that the approximation will be correct given random $x$.

eeegnu
  • 115
  • 3

1 Answers1

1

Consider the equation $$ x^n - (x-\epsilon)^n = 1\implies \epsilon=x-\left(x^n-1\right)^{\frac{1}{n}}=\frac 1 {10^m}$$ $$m=-\frac{\log \left(\left|x-\left(x^n-1\right)^{\frac{1}{n}}\right|\right)}{\log (10)}$$

Claude Leibovici
  • 260,315
  • You seem to be an expert on efficient numerical algorithms for constructing workable solutions. Your answers are always an interesting read. – K.defaoite Oct 03 '20 at 09:39
  • @K.defaoite. Thanks for the nice words. I started in applied mathematics and computing ... 60+ years ago and I have still fun (I do not consider that I am a mathematician). By the way, I like your answers (the proof : I quoted five of yours in mine). Cheers :-) – Claude Leibovici Oct 03 '20 at 09:43
  • Wow, quite a long stretch. I am still only a young student of 20 years. – K.defaoite Oct 03 '20 at 09:50
  • @K.defaoite. Lucky man ! You could be my grand grand son/daughter !! Cheers :-) – Claude Leibovici Oct 03 '20 at 13:34