2

I need to narrow the range (minimum/maximum) to search for a root given the base and the power, the values are all integers, the base can be very large relative to an always positive power. Is there a quick way to determine the order of the root using the relative sizes and values of the base and the power?

E.g.: what would the order of the 11th root of 34567887654323456780987634567895 be?

This answer is a bit too complex for my needs:

What is the proper way to determine the order of a root?

dantopa
  • 10,342
slashmais
  • 223

1 Answers1

4

Use the number of digits. For your example

$\sqrt[11]{34567887654323456780987634567895}$

I would count that there are $32$ digits, so the radicand can be bounded as follows: $$\left(10^2\right)^{11} = 10^{22} < 34567887654323456780987634567895 < 10^{33}=\left(10^3\right)^{11}$$

That means

$$ 100 < \sqrt[11]{34567887654323456780987634567895} < 1000$$

In general, if your index is $n$ and the radicand is $k$, and the number of digits of $k$ is $d(k)$, then the following are bounds on the "order" of the $n^\text{th}$ root of $k$:

$$\left\lfloor \frac{d(k)-1}{n} \right\rfloor \leq \log_{10}\left(\sqrt[n]{k}\right) \leq \left\lfloor\frac{d(k)-1}{n}\right\rfloor + 1 $$

This uses the floor and ceiling functions, and the logarithm base $10$.

Zubin Mukerjee
  • 17,832
  • I'm battling to create a formula using your answer, can you suggest one? (I'm trying: min = (base-size + 1) / power, and max = min + 1, but it works only in some cases - the base can be anything from 1 to very large) – slashmais Jun 05 '16 at 08:24
  • I edited the answer to add a general formula which I think works to find the "order" of your number. As for terminology, the number $n$ in the symbol $\sqrt[n]{k}$ is called the index, and $k$ is the radicand. – Zubin Mukerjee Jun 05 '16 at 08:41
  • I assume in the ceiling you mean d(k)+1 ? How would a different radix affect this formula (The application I wrote, and is now optimizing, uses radix 256 by default - I can convert the numbers to radix 10, do the calculation and convert that to radix 256, but it won't be optimal (my app currently brute-forces determining the range: starting max=10 (=256 radix 10), then multiplying by radix until max to the power is greater than the base, bumping min up as it goes along - which for a large base is not optimal)) – slashmais Jun 05 '16 at 09:05
  • You are right about the upper bound - I changed it from ceiling to floor and added $1$. The formula works the same with a different base $b$ (or "radix" ... I am avoiding using that word because it can also refer to the radical sign $\sqrt{,}$ ). Just make sure your function $d(k)$ returns the number of digits of $k$ in the base $b$ representation of $k$ (and not the decimal representation). Then replace the $\log_{10}$ in the formula with $\log_b$ ... Good luck! :) – Zubin Mukerjee Jun 05 '16 at 09:35
  • Thank you - got it working (seems) reliably, now to testing ... – slashmais Jun 05 '16 at 11:04