bendns' repos / cinter
[no description]
Diffstat (limited to 'src/array_ap.rs')
-rw-r--r--src/array_ap.rs496
1 files changed, 496 insertions, 0 deletions
diff --git a/src/array_ap.rs b/src/array_ap.rs
new file mode 100644
index 0000000..e06ccb7
--- /dev/null
+++ b/src/array_ap.rs
@@ -0,0 +1,496 @@
+#[cfg(test)]
+mod test;
+
+use std::borrow::Cow;
+use std::cmp::Ordering;
+use std::fmt::{Debug, Display, Write};
+use std::intrinsics::{const_deallocate, const_eval_select};
+use std::marker::Destruct;
+use std::mem::{ManuallyDrop as MD, forget, replace, transmute};
+use std::ops::{
+ Add, AddAssign, Deref, DerefMut, Div, DivAssign, Mul, MulAssign, Neg,
+ Rem, Shl, Shr, Sub, SubAssign,
+};
+trait Constructible {}
+impl<const N: usize> Constructible for [u8; N] {}
+use crate::xp::{self, XP};
+
+#[derive(Clone)]
+pub struct AP<const N: usize = 8> {
+ /// sign is either 1 or −1. size is the number of digits allocated and pointed
+ /// to by digits; it can exceed ndigits, which is the number of digits in
+ /// use. That is, an AP_T represents the number given by the XP_T in dig-
+ /// its[0..ndigits-1]. AP_Ts are always normalized: Their most signifi-
+ /// cant digit is nonzero, unless the value is zero. Thus, ndigits is often
+ /// less than size. Figure 18.1 shows the layout of an 11-digit AP_T that is
+ /// equal to 751,702,468,129 on a little endian computer with 32-bit words
+ /// and 8-bit characters..
+ sign: i8,
+ ndigits: u32,
+ /// ptr,len,cap
+ digits: [u8; N],
+}
+impl<const N: usize> const Eq for AP<N> {}
+impl<const N: usize> const PartialEq for AP<N> {
+ fn eq(&self, other: &Self) -> bool {
+ self.sign == other.sign
+ && self.ndigits == other.ndigits
+ && self.dgr()[..self.ndigits as usize]
+ == other.dgr()[..other.ndigits as usize]
+ }
+}
+
+impl<const N: usize> const Default for AP<N> {
+ fn default() -> Self {
+ Self { sign: 1, ndigits: 1, digits: [0; N] }
+ }
+}
+
+impl<const N: usize> Debug for AP<N> {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ if self.sign == -1 {
+ f.write_char('-')?;
+ }
+ let mut x = Vec::with_capacity(1024);
+ f.write_str(unsafe {
+ std::str::from_utf8_unchecked(xp::to_str(
+ &mut x,
+ 10,
+ self.ndigits,
+ self.clone().dg(),
+ ))
+ })
+ }
+}
+impl<const N: usize> Display for AP<N> {
+ fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+ if self.sign == -1 {
+ f.write_char('-')?;
+ }
+ let mut x = Vec::with_capacity(1024);
+ f.write_str(unsafe {
+ std::str::from_utf8_unchecked(xp::to_str(
+ &mut x,
+ 10,
+ self.ndigits,
+ self.clone().dg(),
+ ))
+ })
+ }
+}
+
+impl<const N: usize> AP<N> {
+ const fn sz(&self) -> u32 {
+ self.digits.len() as _
+ }
+ const fn dg(&mut self) -> &mut XP {
+ &mut self.digits
+ }
+ pub const fn new(n: i128) -> Self {
+ let mut x = Self::alloc();
+ x.set(n);
+ x
+ }
+ const fn dgr(&self) -> &XP {
+ &self.digits
+ }
+ pub const fn to_int(&self) -> i128 {
+ let u =
+ xp::to_int(self.ndigits, self.dgr()) % (i128::MAX as u128 + 1);
+ if self.sign == -1 { -(u as i128) } else { u as i128 }
+ }
+ pub const fn set(&mut self, n: i128) {
+ if (n == i128::MIN) {
+ xp::from_int(self.sz(), self.dg(), (i128::MAX as u128 + 1));
+ } else if (n < 0) {
+ xp::from_int(self.sz(), self.dg(), (-n) as _);
+ } else {
+ xp::from_int(self.sz(), self.dg(), (n) as _);
+ self.sign = if n < 0 { -1 } else { 1 };
+ }
+ self.sign = if n < 0 { -1 } else { 1 };
+ self.normalize(self.sz());
+ }
+ pub const fn normalize(&mut self, n: u32) {
+ self.ndigits = xp::len(n, self.dgr());
+ }
+ const fn iszero(&self) -> bool {
+ self.ndigits == 1 && self.dgr()[0] == 0
+ }
+ pub const fn alloc() -> Self {
+ Self { sign: 1, ndigits: 1, digits: [0; N] }
+ }
+ const fn add<const N2: usize, const N3: usize>(
+ z: &mut Self,
+ x: &AP<N2>,
+ y: &AP<N3>,
+ ) {
+ let mut n = y.ndigits;
+ if x.ndigits < n {
+ Self::add(z, y, x)
+ } else if (x.ndigits > n) {
+ let carry = xp::add(n, z.dg(), x.dgr(), y.dgr(), false);
+ let sz = z.sz() as usize;
+ z.dg()[sz - 1] = unsafe {
+ xp::sum(
+ x.ndigits - n,
+ &mut z.dg()[n as usize..],
+ &x.dgr()[n as usize..],
+ carry as _,
+ )
+ };
+ } else {
+ z.dg()[n as usize] =
+ xp::add(n, z.dg(), x.dgr(), y.dgr(), false) as _;
+ }
+ z.normalize(z.sz());
+ }
+ const fn sub<const N2: usize, const N3: usize>(
+ z: &mut Self,
+ x: &AP<N2>,
+ y: &AP<N3>,
+ ) {
+ let mut n = y.ndigits;
+ // int borrow, n = y->ndigits;
+ let mut borrow = xp::sub(n, z.dg(), x.dgr(), y.dgr(), false) as u8;
+ if (x.ndigits > n) {
+ borrow = xp::diff(
+ x.ndigits - n,
+ &mut z.dg()[n as usize..],
+ &x.dgr()[n as usize..],
+ borrow,
+ );
+ }
+ assert!(borrow == 0);
+ z.normalize(z.sz());
+ // assert(borrow == 0);
+ // return normalize(z, z->size);
+ }
+ const fn cmp<const N2: usize>(x: &Self, y: &AP<N2>) -> Ordering {
+ if x.ndigits != y.ndigits {
+ x.ndigits.cmp(&y.ndigits)
+ } else {
+ xp::cmp(x.ndigits, x.dgr(), y.dgr())
+ }
+ }
+ const fn smsn<const N2: usize>(x: &Self, y: &AP<N2>) -> bool {
+ // x.sign == y.sign
+ (x.sign ^ y.sign) == 0
+ }
+ pub const fn divmod<const N2: usize>(
+ x: &Self,
+ y: &AP<N2>,
+ ) -> (Self, AP<N2>)
+ where
+ [u8; N2 + N + 2]: Constructible,
+ {
+ assert!(!y.iszero());
+ let mut q = Self::alloc();
+ let mut r = AP::<N2>::alloc();
+ xp::div(
+ x.ndigits,
+ q.dg(),
+ x.dgr(),
+ y.ndigits,
+ y.dgr(),
+ r.dg(),
+ AP::<{ N2 + N + 2 }>::alloc().dg(),
+ );
+ q.normalize(q.sz());
+ r.normalize(r.sz());
+ q.sign = if q.iszero() || AP::smsn(x, y) { 1 } else { -1 };
+ if !AP::smsn(x, y) && !r.iszero() {
+ let carry = unsafe {
+ xp::sum_p(q.sz(), q.dg().as_mut_ptr(), q.dgr().as_ptr(), 1)
+ };
+ assert!(carry == 0);
+ q.normalize(q.sz());
+ assert!(unsafe {
+ !xp::subp(
+ r.sz(),
+ r.dg().as_mut_ptr(),
+ y.dgr().as_ptr(),
+ r.dgr().as_ptr(),
+ false,
+ )
+ });
+ r.normalize(r.sz());
+ };
+ (q, r)
+ }
+ const fn isone(&self) -> bool {
+ self.ndigits == 1 && self.dgr()[0] == 1
+ }
+ pub const fn is_even(&self) -> bool {
+ (self.dgr()[0] & 1) == 0
+ }
+ pub const fn mulmod<const N2: usize, const N3: usize>(
+ x: &Self,
+ y: &AP<N2>,
+ p: &AP<N3>,
+ ) -> AP<N3>
+ where
+ [(); N + N2]:,
+ [(); N3 + { N + N2 } + 2]:,
+ {
+ let xy: AP<{ N + N2 }> = x * y;
+ &xy % p
+ }
+ // pub const fn pow<const N2: usize>(&self, y: &AP<N2>) -> AP
+ // where
+ // [(); { N2 - (1 / 8) }]:,
+ // {
+ // assert!(y.sign == 1);
+ // if self.iszero() {
+ // return AP::new(0);
+ // }
+ // if y.iszero() {
+ // return AP::new(1);
+ // }
+ // if self.isone() {
+ // return AP::new(if y.is_even() { 1 } else { self.sign as _ });
+ // }
+ // if y.isone() {
+ // return self + 0;
+ // }
+ // let y2 = y.shr::<1>();
+ // let t = AP::pow(self, &y2);
+ // let mut z = &t * &t;
+ // if !y.is_even() {
+ // z = self * &z;
+ // }
+ // z
+ // }
+ // pub const fn pow_mod(&self, y: &Self, modulo: &Self) -> Self {
+ // assert!(y.sign == 1);
+ // assert!(modulo.sign == 1 && !modulo.iszero() && !modulo.isone());
+ // if self.iszero() {
+ // return AP::new(0);
+ // }
+ // if y.iszero() {
+ // return AP::new(1);
+ // }
+ // if self.isone() {
+ // return AP::new(if y.is_even() { 1 } else { self.sign as _ });
+ // }
+ // if y.isone() {
+ // return self + 0;
+ // }
+ // let y2 = y >> 1;
+ // let t = AP::pow_mod(self, &y2, modulo);
+ // let mut z = AP::mulmod(&t, &t, modulo);
+ // if !y.is_even() {
+ // z = AP::mulmod(&(self % modulo), &z, modulo);
+ // }
+ // z
+ // }
+ const fn cmp_<const N2: usize>(x: &Self, y: &AP<N2>) -> Ordering {
+ if x.ndigits != y.ndigits {
+ x.ndigits.cmp(&y.ndigits)
+ } else {
+ xp::cmp(x.ndigits, x.dgr(), y.dgr())
+ }
+ }
+}
+
+// impl const Drop for AP {
+// fn drop(&mut self) {}
+// }
+
+impl<const N: usize> const Neg for AP<N> {
+ type Output = AP<N>;
+
+ fn neg(mut self) -> Self::Output {
+ self.sign = if self.iszero() { 1 } else { -self.sign };
+ self
+ }
+}
+
+impl<const N: usize, const N2: usize> const Mul<&AP<N2>> for &AP<N>
+where
+ [u8; N + N2]: Constructible,
+{
+ type Output = AP<{ N + N2 }>;
+
+ fn mul(self, rhs: &AP<N2>) -> Self::Output {
+ let mut z = Self::Output::alloc();
+ xp::mul(z.dg(), self.ndigits, self.dgr(), rhs.ndigits, rhs.dgr());
+ z.normalize(z.sz());
+ z.sign = if z.iszero() || AP::smsn(self, rhs) { 1 } else { -1 };
+ z
+ }
+}
+impl<const N: usize, const N2: usize> const Add<&AP<N2>> for &AP<N>
+where
+ [u8; N.max(N2) + 1]: Constructible,
+{
+ type Output = AP<{ N.max(N2) + 1 }>;
+
+ fn add(self, rhs: &AP<N2>) -> Self::Output {
+ let mut z = AP::alloc();
+ if AP::smsn(&self, &rhs) {
+ AP::add(&mut z, &self, &rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else if AP::cmp(self, rhs).is_gt() {
+ AP::sub(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else {
+ AP::sub(&mut z, rhs, self);
+ z.sign = if z.iszero() { 1 } else { -self.sign };
+ }
+ z
+ }
+}
+impl<const N: usize, const N2: usize> const Sub<&AP<N2>> for &AP<N>
+where
+ [u8; N.max(N2) + 1]: Constructible,
+{
+ type Output = AP<{ N.max(N2) + 1 }>;
+
+ fn sub(self, rhs: &AP<N2>) -> Self::Output {
+ let mut z = AP::alloc();
+ if !AP::smsn(self, rhs) {
+ AP::add(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else if AP::cmp(self, rhs).is_gt() {
+ AP::sub(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else {
+ AP::sub(&mut z, rhs, self);
+ z.sign = if z.iszero() { 1 } else { -self.sign };
+ }
+ z
+ }
+}
+impl<const N: usize, const N2: usize> const Div<&AP<N2>> for &AP<N>
+where
+ [u8; N2 + N + 2]: Constructible,
+{
+ type Output = AP<N>;
+
+ fn div(self, rhs: &AP<N2>) -> Self::Output {
+ AP::divmod(self, rhs).0
+ }
+}
+
+impl<const N: usize, const N2: usize> const Rem<&AP<N2>> for &AP<N>
+where
+ [u8; N2 + N + 2]: Constructible,
+{
+ type Output = AP<N2>;
+
+ fn rem(self, rhs: &AP<N2>) -> Self::Output {
+ AP::divmod(self, rhs).1
+ }
+}
+impl<const N: usize> AP<N> {
+ pub const fn shl<const S: usize>(
+ &self,
+ ) -> AP<{ N + (((S + 7) & !7) / 8) }> {
+ let mut z = AP::alloc();
+ xp::shl(z.sz(), z.dg(), self.ndigits, self.dgr(), S as _, 0);
+ z.sign = self.sign;
+ z.normalize(z.sz());
+ z
+ }
+}
+
+// impl<const N: usize> Shl<u32> for AP<N>
+// where
+// [u8; 8 + N]: Constructible,
+// {
+// type Output = AP<{ 8 + N }>;
+
+// fn shl(self, s: u32) -> Self::Output {
+// let mut z = AP::alloc(self.ndigits + ((s + 7) & !7) / 8);
+// xp::shl(z.sz(), z.dg(), self.ndigits, self.dgr(), s, 0);
+// z.sign = self.sign;
+// z.normalize(z.sz());
+// z
+// }
+// }
+
+impl<const N: usize> AP<N> {
+ pub const fn shr<const S: usize>(&self) -> AP<{ N - (S / 8) }> {
+ if S >= 8 * self.ndigits as usize {
+ return AP::new(0);
+ }
+
+ let mut z = AP::alloc();
+ let c =
+ xp::shr(z.sz(), z.dg(), self.ndigits, self.dgr(), S as _, 0);
+
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ z.normalize(z.sz());
+ z
+ }
+}
+
+// impl<const N: usize> Shr<u32> for AP<N> {
+// type Output = AP;
+
+/// this is a truncating, not flooring, shr.
+// fn shr(self, s: u32) -> Self::Output {
+// if s >= 8 * self.ndigits {
+// return AP::new(0);
+// }
+
+// let mut z = AP::alloc(self.ndigits - (s / 8));
+// let c = xp::shr(z.sz(), z.dg(), self.ndigits, self.dgr(), s, 0);
+
+// z.sign = if z.iszero() { 1 } else { self.sign };
+// z.normalize(z.sz());
+// z
+// }
+// }
+macro_rules! fni {
+ ($t:ident $what:expr => &$and:expr => $fname:ident => $($for:ident)+) => {
+ $(impl<const N:usize> const $t<$for> for &AP<N>
+ where [u8; $what]: Constructible,[u8; $and]: Constructible,
+ {
+ type Output = AP<$what>;
+ fn $fname(self, other: $for) -> Self::Output {
+ let other = AP::<8>::new(other as _);
+ self.$fname(&other)
+ }
+ })+
+ $(impl<const N:usize> const $t<$for> for AP<N>
+ where [u8; $what]: Constructible,[u8; $and]: Constructible,
+ {
+ type Output = AP<$what>;
+ fn $fname(self, other: $for) -> Self::Output {
+ let other = AP::<8>::new(other as _);
+ (&self).$fname(&other)
+ }
+ })+
+ // $(impl const $t<$for> for AP {
+ // type Output = AP;
+ // fn $fname(self, other: $for) -> AP {
+ // let other = AP::new(other as _);
+ // (&self).$fname(&other)
+ // }
+ // })+
+ };
+}
+fni!(Add { N.max(8)+1 } => &0 => add => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Mul { N + 8 } => &0 => mul => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Div N => &{ 8 + N + 2} => div => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Sub { N.max(8)+1} => &0 => sub => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Rem { 8 } => &{ 8 + N + 2} => rem => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+
+impl const PartialOrd for AP {
+ fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+ Some(self.cmp(other))
+ }
+}
+impl const Ord for AP {
+ fn cmp(&self, other: &Self) -> Ordering {
+ if !AP::smsn(self, other) {
+ unsafe { transmute(self.sign) }
+ } else if self.sign == 1 {
+ AP::cmp_(self, other)
+ } else {
+ AP::cmp_(other, self)
+ }
+ }
+}