saxbophone / arby

Arbitrary precision arithmetic in C++, even at compile-time
https://saxbophone.com/arby/
Mozilla Public License 2.0
8 stars 1 forks source link

Math support: Integer root function #98

Closed saxbophone closed 1 year ago

saxbophone commented 2 years ago
// floor(), ceil() of the n-th root of x
constexpr std::pair<Nat, Nat> iroot(const Nat& n, const Nat& x);

Note: if calculating $\sqrt[n]{x}$ proves too difficult, consider changing the spec to provide functions for $\sqrt{x}$ and $\sqrt[3]{x}$ instead.

Like arby::ilog(), this should also return a pair of $floor(g)$,$ceil(g)$ of $g$, the real-value answer.

saxbophone commented 1 year ago

Possible algorithm:

  1. Calculate $w = \frac{log_2 x}{n}$
  2. Apply binary search over the range $2^{floor(w)}..2^{ceil(w)}$

Note: We can't do it exactly this way using arby, because of the way our $log$ operator works.

We'd have to do $w = [floor(\frac{floor(log_2 x)}{n}), ceil(\frac{ceil(log_2 x)}{n})]$

This should still be functional, mind, just the interval may be wider than ideal, I'm not entirely sure to be honest.

We might need to prove that the interval is not too narrow...

I feel like the performance of this should be reasonable without being very complicated

This algorithm has been verified to work for $\sqrt{344}$ and $\sqrt[3]{228}$

Using this Python implementation on a wider range of inputs seems to show it is indeed correct:

from math import e, log

def root(n, x):
    return e ** (log(x) / n)

Note that $e$ was used here as that's the default base that Python's log() runs to, but we will use base-2 for ours, as that's the smallest base we can compute a log for, so will hence be the most fine-grained in terms of getting as close to the result with the first estimate as possible.

saxbophone commented 1 year ago

Notes RE testing this: C++ has square root and cube root functions in the stdlib but not others. We can of course use the $log{1\over n}$ trick, but this may not be that accurate.

Then again, it's an integer log for the love of Ken! How accurate does it need to be?