use crate::ring::*;
use crate::integer::*;
use crate::ordered::*;
pub fn bisect_floor<R, F>(ZZ: R, left: El<R>, right: El<R>, mut func: F) -> El<R>
where R: RingStore, R::Type: IntegerRing, F: FnMut(&El<R>) -> El<R>
{
assert!(ZZ.is_lt(&left, &right));
let mut l = left;
let mut r = right;
assert!(!ZZ.is_pos(&func(&l)));
assert!(ZZ.is_pos(&func(&r)));
loop {
let mut mid = ZZ.add_ref(&l, &r);
ZZ.euclidean_div_pow_2(&mut mid, 1);
if ZZ.eq_el(&mid, &l) || ZZ.eq_el(&mid, &r) {
return l;
} else if ZZ.is_pos(&func(&mid)) {
r = mid;
} else {
l = mid;
}
}
}
pub fn find_root_floor<R, F>(ZZ: R, approx: El<R>, mut func: F) -> El<R>
where R: RingStore, R::Type: IntegerRing, F: FnMut(&El<R>) -> El<R>
{
let mut left = ZZ.clone_el(&approx);
let mut step = ZZ.one();
while ZZ.is_pos(&func(&left)) {
ZZ.sub_assign_ref(&mut left, &step);
ZZ.mul_pow_2(&mut step, 1);
}
step = ZZ.one();
let mut right = approx;
while !ZZ.is_pos(&func(&right)) {
ZZ.add_assign_ref(&mut right, &step);
ZZ.mul_pow_2(&mut step, 1);
}
return bisect_floor(ZZ, left, right, func);
}
pub fn root_floor<R>(ZZ: R, n: El<R>, root: usize) -> El<R>
where R: RingStore, R::Type: IntegerRing
{
assert!(root > 0);
if root == 1 {
return n;
}
if ZZ.is_zero(&n) {
return ZZ.zero();
}
assert!(!ZZ.is_neg(&n));
let log2_ceil_n = ZZ.abs_log2_ceil(&n).unwrap();
return find_root_floor(
&ZZ,
ZZ.from_float_approx(ZZ.to_float_approx(&n).powf(1. / root as f64)).unwrap_or(ZZ.zero()),
|x| {
let x_pow_root_half = ZZ.pow(ZZ.clone_el(x), root / 2);
if ZZ.abs_log2_ceil(x).unwrap_or(0) >= 2 && (ZZ.abs_log2_ceil(&x_pow_root_half).unwrap() - 1) * 2 >= log2_ceil_n {
if ZZ.is_neg(x) {
return ZZ.negate(ZZ.clone_el(&n));
} else {
return ZZ.clone_el(&n);
}
} else {
let x_pow_root = if root % 2 == 0 {
ZZ.pow(x_pow_root_half, 2)
} else {
ZZ.mul_ref_snd(ZZ.pow(x_pow_root_half, 2), x)
};
return ZZ.sub_ref_snd(x_pow_root, &n);
}
}
);
}
#[cfg(test)]
use crate::primitive_int::StaticRing;
#[test]
fn test_bisect_floor() {
assert_eq!(0, bisect_floor(&StaticRing::<i64>::RING, 0, 10, |x| if *x == 0 { 0 } else { 1 }));
assert_eq!(9, bisect_floor(&StaticRing::<i64>::RING, 0, 10, |x| if *x == 10 { 1 } else { 0 }));
assert_eq!(-15, bisect_floor(&StaticRing::<i64>::RING, -20, -10, |x| *x + 15));
}
#[test]
fn test_root_floor() {
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, 16, 2));
assert_eq!(3, root_floor(&StaticRing::<i64>::RING, 27, 3));
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, 17, 2));
assert_eq!(3, root_floor(&StaticRing::<i64>::RING, 28, 3));
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, 24, 2));
assert_eq!(3, root_floor(&StaticRing::<i64>::RING, 63, 3));
assert_eq!(5, root_floor(&StaticRing::<i64>::RING, StaticRing::<i64>::RING.pow(5, 25), 25));
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, StaticRing::<i64>::RING.pow(5, 25), 26));
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, StaticRing::<i64>::RING.pow(5, 25), 27));
assert_eq!(4, root_floor(&StaticRing::<i64>::RING, StaticRing::<i64>::RING.pow(5, 25), 28));
}