StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Without knowing the implementation of <code>pow</code> in your stdlib exactly, you cannot be absolutely sure that</p> <pre><code>floor(pow(n,1.0/k)) or (long long)pow(n,1.0/k) </code></pre> <p>returns the correct result. <code>1.0/k</code> introduces a small inaccuracy and that plus the inaccuracy of <code>pow</code> (unavoidable due to the representation of <code>double</code>s) may just move the result of <code>pow()</code> past the integer threshold if <code>n</code> is a <code>k</code><sup>th</sup> power or very close to one.</p> <p>An example using Haskell's <code>(**)</code>, which does the same thing as <code>pow()</code> from <code>math.h</code>, but it might have a different implementation:</p> <pre><code>Prelude> 3^37-1 :: Int 450283905890997362 Prelude> fromIntegral it ** (1.0/37) 3.0000000000000004 </code></pre> <p>It will however always be at least very close to the correct result, so you can use it as the starting point for a quick correction if necessary.</p> <pre><code>// assumes k > 2 long long r = (long long)pow(n,1.0/k); while (n/power(r+1,k-k/2) >= power(r+1,k/2)) ++r; while (n/power(r,k-k/2) < power(r,k/2)) --r; </code></pre> <p>where <code>power(a,b)</code> is an integer power function (could be <code>round(pow(a,b))</code> for example, or exponentiation by repeated squaring). By raising <code>r</code> resp <code>r+1</code> only to the <code>k-1</code><sup>th</sup> power, overflow is avoided (except possibly if <code>r</code> is 1, you can deal with that special case easily if necessary by testing <code>k < 64 && n < (1ull << k)</code>).</p> <p>Of course the tests for the special cases and the fixup cost time and in almost all cases do nothing above <code>floor(pow(n,1.0/k))</code>, so it may not be worth it.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload