math/mp-nthrt.c: Implement nth-root, and perfect-power detection.

[catacomb] / math / mp.h

diff --git a/math/mp.h b/math/mp.h
index 0434c28..23e71e3 100644 (file)
--- a/math/mp.h
+++ b/math/mp.h
@@ -923,6 +923,54 @@ extern mp *mp_leastcongruent(mp */*d*/, mp */*b*/, mp */*r*/, mp */*m*/);
 
 extern mp *mp_sqrt(mp */*d*/, mp */*a*/);
 
+/* --- @mp_nthrt@ --- *
+ *
+ * Arguments:  @mp *d@ = fake destination
+ *             @mp *a@ = an integer
+ *             @mp *n@ = a strictly positive integer
+ *             @int *exectp_out@ = set nonzero if an exact solution is found
+ *
+ * Returns:    The integer %$\bigl\lfloor \sqrt[n]{a} \bigr\rfloor$%.
+ *
+ * Use:                Return an approximation to the %$n$%th root of %$a$%.
+ *             Specifically, it returns the largest integer %$x$% such that
+ *             %$x^n \le a$%.  If %$x^n = a$% then @*exactp_out@ is set
+ *             nonzero; otherwise it is set zero.  (If @exactp_out@ is null
+ *             then this information is discarded.)
+ *
+ *             The exponent %$n$% must be strictly positive: it's not clear
+ *             to me what the right answer is for %$n \le 0$%.  If %$a$% is
+ *             negative then %$n$% must be odd; otherwise there is no real
+ *             solution.
+ */
+
+extern mp *mp_nthrt(mp */*d*/, mp */*a*/, mp */*n*/, int */*exactp_out*/);
+
+/* --- @mp_perfect_power_p@ --- *
+ *
+ * Arguments:  @mp **x@ = where to write the base
+ *             @mp **n@ = where to write the exponent
+ *             @mp *a@ = an integer
+ *
+ * Returns:    Nonzero if %$a$% is a perfect power.
+ *
+ * Use:                Returns whether an integer %$a$% is a perfect power, i.e.,
+ *             whether it can be written in the form %$a = x^n$% where
+ *             %$|x| > 1$% and %$n > 1$% are integers.  If this is possible,
+ *             then (a) store %$x$% and the largest such %$n$% in @*x@ and
+ *             @*n@, and return nonzero; otherwise, store %$x = a$% and
+ *             %$n = 1$% and return zero.  (Either @x@ or @n@, or both, may
+ *             be null to discard these outputs.)
+ *
+ *             Note that %$-1$%, %$0$% and %$1$% are not considered perfect
+ *             powers by this definition.  (The exponent is not well-defined
+ *             in these cases, but it seemed better to implement a function
+ *             which worked for all integers.)  Note also that %$-4$% is not
+ *             a perfect power since it has no real square root.
+ */
+
+extern int mp_perfect_power_p(mp **/*x*/, mp **/*n*/, mp */*a*/);
+
 /* --- @mp_gcd@ --- *
  *
  * Arguments:  @mp **gcd, **xx, **yy@ = where to write the results