// Copyright © 2024 Mikhail Hogrefe
//
// This file is part of Malachite.
//
// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
// 3 of the License, or (at your option) any later version. See .
use malachite_base::num::arithmetic::root::{
cbrt_chebyshev_approx_u32, cbrt_chebyshev_approx_u64, fast_ceiling_root_u32,
fast_ceiling_root_u64, fast_checked_root_u32, fast_checked_root_u64, fast_floor_cbrt_u32,
fast_floor_cbrt_u64, fast_floor_root_u32, fast_floor_root_u64, fast_root_rem_u32,
fast_root_rem_u64, floor_root_approx_and_refine,
};
use malachite_base::num::arithmetic::root::{
ceiling_root_binary, checked_root_binary, floor_root_binary, root_rem_binary,
};
use malachite_base::num::arithmetic::traits::{
CeilingRoot, CheckedRoot, FloorRoot, Parity, RootRem,
};
use malachite_base::num::basic::signeds::PrimitiveSigned;
use malachite_base::num::basic::unsigneds::PrimitiveUnsigned;
use malachite_base::test_util::generators::{
signed_gen, signed_gen_var_2, signed_unsigned_pair_gen_var_18, unsigned_gen,
unsigned_gen_var_1, unsigned_pair_gen_var_32,
};
use std::ops::Neg;
use std::panic::catch_unwind;
#[test]
fn test_floor_root() {
fn test_u(n: T, exp: u64, out: T) {
assert_eq!(n.floor_root(exp), out);
assert_eq!(floor_root_binary(n, exp), out);
let mut n = n;
n.floor_root_assign(exp);
assert_eq!(n, out);
}
test_u::(0, 1, 0);
test_u::(1, 1, 1);
test_u::(2, 1, 2);
test_u::(100, 1, 100);
test_u::(0, 2, 0);
test_u::(1, 2, 1);
test_u::(2, 2, 1);
test_u::(3, 2, 1);
test_u::(4, 2, 2);
test_u::(5, 2, 2);
test_u::(0, 3, 0);
test_u::(1, 3, 1);
test_u::(2, 3, 1);
test_u::(7, 3, 1);
test_u::(8, 3, 2);
test_u::(9, 3, 2);
test_u::(10, 2, 3);
test_u::(100, 2, 10);
test_u::(100, 3, 4);
test_u::(1000000000, 2, 31622);
test_u::(1000000000, 3, 1000);
test_u::(1000000000, 4, 177);
test_u::(1000000000, 5, 63);
test_u::(1000000000, 6, 31);
test_u::(1000000000, 7, 19);
test_u::(1000000000, 8, 13);
test_u::(1000000000, 9, 10);
test_u::(1000000000, 10, 7);
fn test_i(n: T, exp: u64, out: T) {
assert_eq!(n.floor_root(exp), out);
let mut n = n;
n.floor_root_assign(exp);
assert_eq!(n, out);
}
test_i::(0, 1, 0);
test_i::(1, 1, 1);
test_i::(2, 1, 2);
test_i::(100, 1, 100);
test_i::(0, 2, 0);
test_i::(0, 2, 0);
test_i::(1, 2, 1);
test_i::(2, 2, 1);
test_i::(3, 2, 1);
test_i::(4, 2, 2);
test_i::(5, 2, 2);
test_i::(0, 3, 0);
test_i::(1, 3, 1);
test_i::(2, 3, 1);
test_i::(7, 3, 1);
test_i::(8, 3, 2);
test_i::(9, 3, 2);
test_i::(10, 2, 3);
test_i::(100, 2, 10);
test_i::(100, 3, 4);
test_i::(1000000000, 2, 31622);
test_i::(1000000000, 3, 1000);
test_i::(1000000000, 4, 177);
test_i::(1000000000, 5, 63);
test_i::(1000000000, 6, 31);
test_i::(1000000000, 7, 19);
test_i::(1000000000, 8, 13);
test_i::(1000000000, 9, 10);
test_i::(1000000000, 10, 7);
test_i::(-1, 1, -1);
test_i::(-2, 1, -2);
test_i::(-100, 1, -100);
test_i::(-1, 3, -1);
test_i::(-2, 3, -2);
test_i::(-7, 3, -2);
test_i::(-8, 3, -2);
test_i::(-9, 3, -3);
test_i::(-100, 3, -5);
test_i::(-1000000000, 3, -1000);
test_i::(-1000000000, 5, -64);
test_i::(-1000000000, 7, -20);
test_i::(-1000000000, 9, -10);
}
fn floor_root_fail_helper_unsigned() {
assert_panic!(T::ONE.floor_root(0));
}
fn floor_root_fail_helper_signed() {
assert_panic!(T::ONE.floor_root(0));
assert_panic!(T::NEGATIVE_ONE.floor_root(0));
assert_panic!(T::NEGATIVE_ONE.floor_root(2));
assert_panic!(T::NEGATIVE_ONE.floor_root(4));
assert_panic!(T::NEGATIVE_ONE.floor_root(100));
}
#[test]
pub fn floor_root_fail() {
apply_fn_to_unsigneds!(floor_root_fail_helper_unsigned);
apply_fn_to_signeds!(floor_root_fail_helper_signed);
}
#[test]
fn test_ceiling_root() {
fn test_u(n: T, exp: u64, out: T) {
assert_eq!(n.ceiling_root(exp), out);
assert_eq!(ceiling_root_binary(n, exp), out);
let mut n = n;
n.ceiling_root_assign(exp);
assert_eq!(n, out);
}
test_u::(0, 1, 0);
test_u::(1, 1, 1);
test_u::(2, 1, 2);
test_u::(100, 1, 100);
test_u::(0, 2, 0);
test_u::(1, 2, 1);
test_u::(2, 2, 2);
test_u::(3, 2, 2);
test_u::(4, 2, 2);
test_u::(5, 2, 3);
test_u::(0, 3, 0);
test_u::(1, 3, 1);
test_u::(2, 3, 2);
test_u::(7, 3, 2);
test_u::(8, 3, 2);
test_u::(9, 3, 3);
test_u::(10, 2, 4);
test_u::(100, 2, 10);
test_u::(100, 3, 5);
test_u::(1000000000, 2, 31623);
test_u::(1000000000, 3, 1000);
test_u::(1000000000, 4, 178);
test_u::(1000000000, 5, 64);
test_u::(1000000000, 6, 32);
test_u::(1000000000, 7, 20);
test_u::(1000000000, 8, 14);
test_u::(1000000000, 9, 10);
test_u::(1000000000, 10, 8);
fn test_i(n: T, exp: u64, out: T) {
assert_eq!(n.ceiling_root(exp), out);
let mut n = n;
n.ceiling_root_assign(exp);
assert_eq!(n, out);
}
test_i::(0, 1, 0);
test_i::(1, 1, 1);
test_i::(2, 1, 2);
test_i::(100, 1, 100);
test_i::(0, 2, 0);
test_i::(1, 2, 1);
test_i::(2, 2, 2);
test_i::(3, 2, 2);
test_i::(4, 2, 2);
test_i::(5, 2, 3);
test_i::(0, 3, 0);
test_i::(1, 3, 1);
test_i::(2, 3, 2);
test_i::(7, 3, 2);
test_i::(8, 3, 2);
test_i::(9, 3, 3);
test_i::(10, 2, 4);
test_i::(100, 2, 10);
test_i::(100, 3, 5);
test_i::(1000000000, 2, 31623);
test_i::(1000000000, 3, 1000);
test_i::(1000000000, 4, 178);
test_i::(1000000000, 5, 64);
test_i::(1000000000, 6, 32);
test_i::(1000000000, 7, 20);
test_i::(1000000000, 8, 14);
test_i::(1000000000, 9, 10);
test_i::(1000000000, 10, 8);
test_i::(-1, 1, -1);
test_i::(-2, 1, -2);
test_i::(-100, 1, -100);
test_i::(-1, 3, -1);
test_i::(-2, 3, -1);
test_i::(-7, 3, -1);
test_i::(-8, 3, -2);
test_i::(-9, 3, -2);
test_i::(-100, 3, -4);
test_i::(-1000000000, 3, -1000);
test_i::(-1000000000, 5, -63);
test_i::(-1000000000, 7, -19);
test_i::(-1000000000, 9, -10);
}
fn ceiling_root_fail_helper_unsigned() {
assert_panic!(T::ONE.ceiling_root(0));
}
fn ceiling_root_fail_helper_signed() {
assert_panic!(T::ONE.ceiling_root(0));
assert_panic!(T::NEGATIVE_ONE.ceiling_root(0));
assert_panic!(T::NEGATIVE_ONE.ceiling_root(2));
assert_panic!(T::NEGATIVE_ONE.ceiling_root(4));
assert_panic!(T::NEGATIVE_ONE.ceiling_root(100));
}
#[test]
pub fn ceiling_root_fail() {
apply_fn_to_unsigneds!(ceiling_root_fail_helper_unsigned);
apply_fn_to_signeds!(ceiling_root_fail_helper_signed);
}
#[test]
fn test_checked_root() {
fn test_u(n: T, exp: u64, out: Option) {
assert_eq!(n.checked_root(exp), out);
assert_eq!(checked_root_binary(n, exp), out);
}
test_u::(0, 1, Some(0));
test_u::(1, 1, Some(1));
test_u::(2, 1, Some(2));
test_u::(100, 1, Some(100));
test_u::(0, 2, Some(0));
test_u::(1, 2, Some(1));
test_u::(2, 2, None);
test_u::(3, 2, None);
test_u::(4, 2, Some(2));
test_u::(5, 2, None);
test_u::(0, 3, Some(0));
test_u::(1, 3, Some(1));
test_u::(2, 3, None);
test_u::(7, 3, None);
test_u::(8, 3, Some(2));
test_u::(9, 3, None);
test_u::(10, 2, None);
test_u::(100, 2, Some(10));
test_u::(100, 3, None);
test_u::(1000000000, 2, None);
test_u::(1000000000, 3, Some(1000));
test_u::(1000000000, 4, None);
test_u::(1000000000, 5, None);
test_u::(1000000000, 6, None);
test_u::(1000000000, 7, None);
test_u::(1000000000, 8, None);
test_u::(1000000000, 9, Some(10));
test_u::(1000000000, 10, None);
fn test_i(n: T, exp: u64, out: Option) {
assert_eq!(n.checked_root(exp), out);
}
test_i::(0, 1, Some(0));
test_i::(1, 1, Some(1));
test_i::(2, 1, Some(2));
test_i::(100, 1, Some(100));
test_i::(0, 2, Some(0));
test_i::(1, 2, Some(1));
test_i::(2, 2, None);
test_i::(3, 2, None);
test_i::(4, 2, Some(2));
test_i::(5, 2, None);
test_i::(0, 3, Some(0));
test_i::(1, 3, Some(1));
test_i::(2, 3, None);
test_i::(7, 3, None);
test_i::(8, 3, Some(2));
test_i::(9, 3, None);
test_i::(10, 2, None);
test_i::(100, 2, Some(10));
test_i::(100, 3, None);
test_i::(1000000000, 2, None);
test_i::(1000000000, 3, Some(1000));
test_i::(1000000000, 4, None);
test_i::(1000000000, 5, None);
test_i::(1000000000, 6, None);
test_i::(1000000000, 7, None);
test_i::(1000000000, 8, None);
test_i::(1000000000, 9, Some(10));
test_i::(1000000000, 10, None);
test_i::(-1, 1, Some(-1));
test_i::(-2, 1, Some(-2));
test_i::(-100, 1, Some(-100));
test_i::(-1, 3, Some(-1));
test_i::(-2, 3, None);
test_i::(-7, 3, None);
test_i::(-8, 3, Some(-2));
test_i::(-9, 3, None);
test_i::(-100, 3, None);
test_i::(-1000000000, 3, Some(-1000));
test_i::(-1000000000, 5, None);
test_i::(-1000000000, 7, None);
test_i::(-1000000000, 9, Some(-10));
}
fn checked_root_fail_helper_unsigned() {
assert_panic!(T::ONE.checked_root(0));
}
fn checked_root_fail_helper_signed() {
assert_panic!(T::ONE.checked_root(0));
assert_panic!(T::NEGATIVE_ONE.checked_root(0));
assert_panic!(T::NEGATIVE_ONE.checked_root(2));
assert_panic!(T::NEGATIVE_ONE.checked_root(4));
assert_panic!(T::NEGATIVE_ONE.checked_root(100));
}
#[test]
pub fn checked_root_fail() {
apply_fn_to_unsigneds!(checked_root_fail_helper_unsigned);
apply_fn_to_signeds!(checked_root_fail_helper_signed);
}
#[test]
fn test_root_rem() {
fn test(n: T, exp: u64, out_root: T, out_rem: T) {
assert_eq!(n.root_rem(exp), (out_root, out_rem));
assert_eq!(root_rem_binary(n, exp), (out_root, out_rem));
let mut n = n;
assert_eq!(n.root_assign_rem(exp), out_rem);
assert_eq!(n, out_root);
}
test::(0, 1, 0, 0);
test::(1, 1, 1, 0);
test::(2, 1, 2, 0);
test::(100, 1, 100, 0);
test::(0, 2, 0, 0);
test::(1, 2, 1, 0);
test::(2, 2, 1, 1);
test::(3, 2, 1, 2);
test::(4, 2, 2, 0);
test::(5, 2, 2, 1);
test::(0, 3, 0, 0);
test::(1, 3, 1, 0);
test::(2, 3, 1, 1);
test::(7, 3, 1, 6);
test::(8, 3, 2, 0);
test::(9, 3, 2, 1);
test::(10, 2, 3, 1);
test::(100, 2, 10, 0);
test::(100, 3, 4, 36);
test::(1000000000, 2, 31622, 49116);
test::(1000000000, 3, 1000, 0);
test::(1000000000, 4, 177, 18493759);
test::(1000000000, 5, 63, 7563457);
test::(1000000000, 6, 31, 112496319);
test::(1000000000, 7, 19, 106128261);
test::(1000000000, 8, 13, 184269279);
test::(1000000000, 9, 10, 0);
test::(1000000000, 10, 7, 717524751);
}
fn root_rem_fail_helper() {
assert_panic!(T::ONE.root_rem(0));
}
#[test]
pub fn root_rem_fail() {
apply_fn_to_unsigneds!(root_rem_fail_helper);
}
fn floor_root_properties_helper_unsigned() {
unsigned_pair_gen_var_32::().test_properties(|(n, exp)| {
let root = n.floor_root(exp);
let mut n_alt = n;
n_alt.floor_root_assign(exp);
assert_eq!(n_alt, root);
assert_eq!(floor_root_binary(n, exp), root);
let pow = root.pow(exp);
let ceiling_root = n.ceiling_root(exp);
if pow == n {
assert_eq!(ceiling_root, root);
} else {
assert_eq!(ceiling_root, root + T::ONE);
}
assert!(pow <= n);
if exp != 1 {
if let Some(next_pow) = (root + T::ONE).checked_pow(exp) {
assert!(next_pow > n);
}
}
});
unsigned_gen::