bendns' repos / cinter
[no description]
Diffstat
-rw-r--r--.gitignore2
-rw-r--r--Cargo.toml13
-rw-r--r--LICENSE21
-rw-r--r--README.md22
-rw-r--r--rustfmt.toml7
-rw-r--r--src/ap.rs555
-rw-r--r--src/ap/test.rs94
-rw-r--r--src/array_ap.rs496
-rw-r--r--src/array_ap/test.rs92
-rw-r--r--src/lib.rs28
-rw-r--r--src/xp.rs462
-rw-r--r--src/xp/test.rs114
12 files changed, 1906 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..056781b
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+fail.png
+Cargo.lock
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..7358f09
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,13 @@
+[package]
+name = "cinter"
+version = "0.1.0"
+license = "MIT"
+edition = "2024"
+authors = ["bend-n <[email protected]>"]
+description = "const usable bigints"
+repository = "https://git.bendn.org/cinter"
+keywords = ["mathematics", "numerics", "bignum", "const"]
+categories = ["algorithms", "data-structures", "science"]
+
+[dev-dependencies]
+rand = { version = "0.10.0", default-features = false, features = ["std", "thread_rng"] }
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..8c33164
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2026 bendn
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..6f32d7c
--- /dev/null
+++ b/README.md
@@ -0,0 +1,22 @@
+# cinter
+
+const usable Arbitrary Precision (big) integers.
+
+```rust
+const fn fib(n: usize) -> (AP, AP) {
+ if n == 0 {
+ return (AP::new(0), AP::new(1));
+ };
+
+ let (α, β) = fib(n >> 1);
+ let γ = &α * ((&β << 1) - &α);
+ let δ = &α * &α + &β * &β;
+ if n & 1 == 0 {
+ return (γ, δ);
+ }
+ let t = γ + &δ;
+ (δ, t)
+}
+#[allow(long_running_const_eval)]
+pub const 1_MILLIONTH_FIBONACCI_NUMBER: AP = fib(1_000_000).0.globalize();
+```
diff --git a/rustfmt.toml b/rustfmt.toml
new file mode 100644
index 0000000..c39da03
--- /dev/null
+++ b/rustfmt.toml
@@ -0,0 +1,7 @@
+max_width = 75
+format_strings = true
+group_imports = "StdExternalCrate"
+imports_granularity = "Module"
+match_arm_blocks = false
+style_edition = "2024"
+use_small_heuristics = "Max"
diff --git a/src/ap.rs b/src/ap.rs
new file mode 100644
index 0000000..8379fb3
--- /dev/null
+++ b/src/ap.rs
@@ -0,0 +1,555 @@
+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,
+};
+#[cfg(test)]
+mod test;
+
+use crate::xp::{self, XP};
+#[repr(C)]
+/// Arbitratry precision integer, usable in const
+pub struct AP {
+ // -1 | +1
+ sign: i8,
+ ndigits: u32,
+ digits: MD<Storage>,
+}
+impl const Eq for AP {}
+impl const PartialEq for AP {
+ 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 Drop for Storage {
+ fn drop(&mut self) {
+ const fn drop_c(x: &mut MD<Vec<u8>>) {
+ unsafe { const_deallocate(x.as_mut_ptr(), x.capacity(), 0) };
+ }
+ fn drop_r(x: &mut MD<Vec<u8>>) {
+ unsafe { MD::drop(x) };
+ }
+
+ match self {
+ Self::V(x) => {
+ const_eval_select((x,), drop_c, drop_r);
+ }
+ _ => {}
+ }
+ }
+}
+
+impl const DerefMut for Storage {
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ match self {
+ Self::V(x) => x.as_mut_slice(),
+ Self::Leaked(items) => {
+ let mut v = Vec::new();
+ let mut i = 0;
+ while i < items.len() {
+ v.push(items[i]);
+ }
+ *self = Storage::V(MD::new(v));
+ &mut *self
+ }
+ }
+ }
+}
+
+impl const Deref for Storage {
+ type Target = [u8];
+ fn deref(&self) -> &Self::Target {
+ match self {
+ Self::V(x) => x.as_slice(),
+ Self::Leaked(items) => *items,
+ }
+ }
+}
+
+impl const Clone for AP {
+ fn clone(&self) -> Self {
+ Self {
+ sign: self.sign.clone(),
+ ndigits: self.ndigits.clone(),
+ digits: MD::new((&*self.digits).clone()),
+ }
+ }
+}
+
+#[derive(Debug)]
+pub enum Storage {
+ V(MD<Vec<u8>>),
+ Leaked(&'static [u8]),
+}
+impl const Clone for Storage {
+ fn clone(&self) -> Self {
+ match self {
+ Self::V(x) => {
+ let mut i = 0;
+ let mut v = Vec::with_capacity(x.len());
+ while i < x.len() {
+ v.push(x.as_slice()[i]);
+ i += 1;
+ }
+ Self::V(MD::new(v))
+ }
+ Self::Leaked(x) => Self::Leaked(x),
+ }
+ }
+}
+impl const Default for AP {
+ fn default() -> Self {
+ Self {
+ sign: 1,
+ ndigits: 1,
+ digits: MD::new(Storage::Leaked(&[0])),
+ }
+ }
+}
+
+impl Debug for AP {
+ 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 Display for AP {
+ 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 AP {
+ 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(8);
+ 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());
+ }
+ 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(size: u32) -> Self {
+ assert!(size > 0);
+ let mut v = Vec::with_capacity(size as _);
+ let mut i = 0;
+ while i < size {
+ v.push(0);
+ i += 1;
+ }
+
+ Self {
+ sign: 1,
+ ndigits: 1,
+ digits: MD::new(Storage::V(MD::new(v))),
+ }
+ }
+ const fn add(z: &mut Self, x: &Self, y: &Self) {
+ 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(z: &mut Self, x: &Self, y: &Self) {
+ 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(x: &Self, y: &Self) -> Ordering {
+ if x.ndigits != y.ndigits {
+ x.ndigits.cmp(&y.ndigits)
+ } else {
+ xp::cmp(x.ndigits, x.dgr(), y.dgr())
+ }
+ }
+ const fn smsn(x: &Self, y: &Self) -> bool {
+ (x.sign ^ y.sign) == 0
+ }
+ pub const fn divmod(x: &Self, y: &Self) -> (AP, AP) {
+ assert!(!y.iszero());
+ let mut q = AP::alloc(x.ndigits);
+ let mut r = AP::alloc(y.ndigits);
+ xp::div(
+ x.ndigits,
+ q.dg(),
+ x.dgr(),
+ y.ndigits,
+ y.dgr(),
+ r.dg(),
+ AP::alloc(x.ndigits + y.ndigits + 2).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
+ }
+ const fn mulmod(x: &Self, y: &Self, p: &Self) -> AP {
+ let xy = x * y;
+ &xy % p
+ }
+ pub const fn pow(&self, y: &Self) -> AP {
+ 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 >> 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_(x: &Self, y: &Self) -> Ordering {
+ if x.ndigits != y.ndigits {
+ x.ndigits.cmp(&y.ndigits)
+ } else {
+ xp::cmp(x.ndigits, x.dgr(), y.dgr())
+ }
+ }
+ /// call before storing.
+ pub const fn globalize(mut self) -> Self {
+ match &mut *self.digits {
+ Storage::V(x) =>
+ self.digits = MD::new(Storage::Leaked(
+ unsafe { MD::take(x) }.const_make_global(),
+ )),
+ _ => {}
+ };
+ self
+ }
+}
+
+impl const Drop for AP {
+ fn drop(&mut self) {
+ unsafe { MD::drop(&mut self.digits) };
+ }
+}
+
+impl const Neg for AP {
+ type Output = AP;
+
+ fn neg(mut self) -> Self::Output {
+ self.sign = if self.iszero() { 1 } else { -self.sign };
+ self
+ }
+}
+
+impl const Mul for &AP {
+ type Output = AP;
+
+ fn mul(self, rhs: Self) -> Self::Output {
+ let mut z = AP::alloc(self.ndigits + rhs.ndigits);
+ 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 MulAssign<&AP> for AP {
+ fn mul_assign(&mut self, rhs: &Self) {
+ *self = &*self * rhs;
+ }
+}
+impl const Add for &AP {
+ type Output = AP;
+
+ fn add(self, rhs: Self) -> Self::Output {
+ let mut z;
+ if AP::smsn(&self, &rhs) {
+ z = AP::alloc(self.ndigits.max(rhs.ndigits) + 1);
+ AP::add(&mut z, &self, &rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else if AP::cmp(self, rhs).is_gt() {
+ z = AP::alloc(self.ndigits);
+ AP::sub(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else {
+ // lesser ?
+ z = AP::alloc(rhs.ndigits);
+ AP::sub(&mut z, rhs, self);
+ z.sign = if z.iszero() { 1 } else { -self.sign };
+ }
+ z
+ }
+}
+impl const Sub for &AP {
+ type Output = AP;
+
+ fn sub(self, rhs: Self) -> Self::Output {
+ let mut z;
+ if !AP::smsn(self, rhs) {
+ z = AP::alloc(self.ndigits.max(rhs.ndigits) + 1);
+
+ AP::add(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else if AP::cmp(self, rhs).is_gt() {
+ z = AP::alloc(self.ndigits);
+ AP::sub(&mut z, self, rhs);
+ z.sign = if z.iszero() { 1 } else { self.sign };
+ } else {
+ z = AP::alloc(rhs.ndigits);
+ AP::sub(&mut z, rhs, self);
+ z.sign = if z.iszero() { 1 } else { -self.sign };
+ }
+ z
+ }
+}
+impl const SubAssign<&AP> for AP {
+ fn sub_assign(&mut self, rhs: &AP) {
+ *self = &*self - rhs;
+ }
+}
+impl const AddAssign<&AP> for AP {
+ fn add_assign(&mut self, rhs: &AP) {
+ *self = &*self + rhs;
+ }
+}
+impl const Div for &AP {
+ type Output = AP;
+
+ fn div(self, rhs: Self) -> Self::Output {
+ AP::divmod(self, rhs).0
+ }
+}
+impl const DivAssign<&AP> for AP {
+ fn div_assign(&mut self, rhs: &AP) {
+ *self = &*self / rhs;
+ }
+}
+impl const Rem for &AP {
+ type Output = AP;
+
+ fn rem(self, rhs: Self) -> Self::Output {
+ AP::divmod(self, rhs).1
+ }
+}
+
+impl const Shl<u32> for &AP {
+ type Output = AP;
+
+ 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 Shr<u32> for &AP {
+ 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, $fname:ident => $($for:ident)+) => {
+ impl const $t<&AP> for AP {
+ type Output = AP;
+ fn $fname(self, other: &AP) -> AP {
+ <&AP as $t<&AP>>::$fname(&self, other)
+ }
+ }
+ impl const $t<AP> for AP {
+ type Output = AP;
+ fn $fname(self, other: AP) -> AP {
+ <&AP as $t<&AP>>::$fname(&self, &other)
+ }
+ }
+
+ impl const $t<AP> for &AP {
+ type Output = AP;
+ fn $fname(self, other: AP) -> AP {
+ <&AP as $t<&AP>>::$fname(self, &other)
+ }
+ }
+
+ $(impl const $t<$for> for &AP {
+ type Output = AP;
+ fn $fname(self, other: $for) -> AP {
+ let other = AP::new(other as _);
+ <&AP as $t<&AP>>::$fname(self, &other)
+ }
+ })+
+ $(impl const $t<$for> for AP {
+ type Output = AP;
+ fn $fname(self, other: $for) -> AP {
+ let other = AP::new(other as _);
+ <&AP as $t<&AP>>::$fname(&self, &other)
+ }
+ })+
+ };
+}
+fni!(Add, add => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Mul, mul => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Div, div => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Sub, sub => u64 u32 u16 u8 i128 i64 i32 i16 i8);
+fni!(Rem, 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)
+ }
+ }
+}
diff --git a/src/ap/test.rs b/src/ap/test.rs
new file mode 100644
index 0000000..d26507e
--- /dev/null
+++ b/src/ap/test.rs
@@ -0,0 +1,94 @@
+use std::io::Write;
+
+use rand::Rng;
+
+use super::*;
+
+fn coerce<T, U>(f: impl FnMut(T, T) -> U) -> impl FnMut(T, T) -> U {
+ f
+}
+macro_rules! with {
+ (fn $ident:ident = $f:expr => $f2:expr) => {
+ #[test]
+ fn $ident() {
+ let mut r = rand::rng();
+
+ for n in 0..5000 {
+ let a_ = r.next_u64() as i64 as _;
+ let b_ = r.next_u64() as i64 as _;
+ let Some(ought) =
+ coerce::<i128, Option<i128>>($f2)(a_, b_)
+ else {
+ continue;
+ };
+
+ let mut o = coerce::<i128, String>($f)(a_, b_);
+
+ // let x = to_int(63, &o);s
+ assert_eq!(
+ o,
+ ought.to_string(),
+ "should be {ought}, instead was {o}"
+ );
+ }
+ }
+ };
+}
+with! {fn roundtrip = |a, b| {
+ AP::new(a).to_int().to_string()
+} => |a, b| Some(a) }
+with!(fn test_add = |a, b| {
+ (AP::new(a) + b).to_string()
+} => |a, b| a.checked_add(b));
+with!(fn test_sub = |a, b| {
+ (AP::new(a) - b).to_string()
+} => |a, b| a.checked_sub(b));
+with!(fn test_mul = |a, b| {
+ (AP::new(a) * b).to_string()
+} => |a, b| a.checked_mul(b));
+// with!(fn test_div = |a, b|{
+// (AP::new(a) / b).to_string()
+// }=>|a, b| a.checked_div(b));
+with!(fn test_shl = |a, b| {
+ (&AP::new(a) << b as u8 as u32 / 4).to_string()
+}=>|a, b| a.checked_shl(dbg!(b as u8 as u32 /4)));
+with!(fn test_shr = |a, b| {
+ (&AP::new(a.abs()) >> (b as u8 as u32 / 2)).to_string()
+}=>|a, b| a.abs().checked_shr(b as u8 as u32 / 2));
+with!(fn test_cmp = |a, b| (AP::new(a).cmp(&AP::new(b)) as i128).to_string()
+ =>|a, b| Some((a.cmp(&b)) as i128));
+
+const fn fib(n: usize) -> (AP, AP) {
+ if n == 0 {
+ return (AP::new(0), AP::new(1));
+ };
+
+ let (α, β) = fib(n >> 1);
+ let γ = &α * ((&β << 1) - &α);
+ let δ = &α * &α + &β * &β;
+ if n & 1 == 0 {
+ return (γ, δ);
+ }
+ let t = γ + &δ;
+ (δ, t)
+}
+// #[allow(long_running_const_eval)]
+const X: AP = fib(5000).0.globalize();
+#[test]
+#[cfg(not(miri))]
+fn fibtest() {
+ fn naive(n: usize) -> AP {
+ let mut α = AP::new(1);
+ let mut β = AP::new(1);
+
+ for _ in 2..n {
+ let temp = β.clone();
+ β += &α;
+ α = temp;
+ }
+
+ β
+ }
+
+ assert_eq!(naive(5000), fib(5000).0);
+}
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)
+ }
+ }
+}
diff --git a/src/array_ap/test.rs b/src/array_ap/test.rs
new file mode 100644
index 0000000..609df66
--- /dev/null
+++ b/src/array_ap/test.rs
@@ -0,0 +1,92 @@
+use std::io::Write;
+
+use rand::Rng;
+
+use super::*;
+
+fn coerce<T, U>(f: impl FnMut(T, T) -> U) -> impl FnMut(T, T) -> U {
+ f
+}
+macro_rules! with {
+ (fn $ident:ident = $f:expr => $f2:expr) => {
+ #[test]
+ fn $ident() {
+ let mut r = rand::rng();
+
+ for n in 0..50000 {
+ let a_ = r.next_u64() as i64 as _;
+ let b_ = r.next_u64() as i64 as _;
+ let Some(ought) =
+ coerce::<i128, Option<i128>>($f2)(a_, b_)
+ else {
+ continue;
+ };
+
+ let mut o = coerce::<i128, String>($f)(a_, b_);
+
+ // let x = to_int(63, &o);s
+ assert_eq!(
+ o,
+ ought.to_string(),
+ "should be {ought}, instead was {o}"
+ );
+ }
+ }
+ };
+}
+with! {fn roundtrip = |a, b| {
+ AP::<8>::new(a).to_int().to_string()
+} => |a, b| Some(a) }
+with!(fn test_add = |a, b| {
+ (AP::<8>::new(a) + b).to_string()
+} => |a, b| a.checked_add(b));
+with!(fn test_sub = |a, b| {
+ (AP::<8>::new(a) - b).to_string()
+} => |a, b| a.checked_sub(b));
+with!(fn test_mul = |a, b| {
+ (AP::<8>::new(a) * b).to_string()
+} => |a, b| a.checked_mul(b));
+// with!(fn test_div = |a, b|{
+// (AP::new(a) / b).to_string()
+// }=>|a, b| a.checked_div(b));
+// with!(fn test_shl = |a, b| {
+// (&AP::<8>::new(a) << b as u8 as u32 / 4).to_string()
+// }=>|a, b| a.checked_shl(dbg!(b as u8 as u32 /4)));
+// with!(fn test_shr = |a, b| {
+// (&AP::new(a.abs()) >> (b as u8 as u32 / 2)).to_string()
+// }=>|a, b| a.abs().checked_shr(b as u8 as u32 / 2));
+with!(fn test_cmp = |a, b| (AP::new(a).cmp(&AP::new(b)) as i128).to_string()
+ =>|a, b| Some((a.cmp(&b)) as i128));
+
+// #[test]
+// fn fibtest() {
+// fn fib(n: usize) -> (AP, AP) {
+// if n == 0 {
+// return (AP::new(0), AP::new(1));
+// };
+// let (α, β) = fib(n >> 1);
+// let γ = &α * &((&β.shl::<1>()) - &α);
+// let δ = &(&α * &α) + &(&β * &β);
+// if n & 1 == 0 {
+// return (γ, δ);
+// }
+// let t = &γ + &δ;
+// (δ, t)
+// }
+
+// fn naive(n: usize) -> AP {
+// let mut α = AP::new(1);
+// let mut β = AP::new(1);
+
+// for _ in 2..n {
+// let temp = β.clone();
+// β += &α;
+// α = temp;
+// }
+
+// β
+// }
+
+// assert_eq!(naive(5000), fib(5000).0);
+// let x = fib(1_000_000).0;
+// }
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..1595c63
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,28 @@
+//! provides bigints, but const.
+#![feature(
+ const_drop_in_place,
+ generic_const_exprs,
+ const_eval_select,
+ const_manually_drop_take,
+ exact_div,
+ exact_bitshifts,
+ const_default,
+ core_intrinsics,
+ const_destruct,
+ const_heap,
+ const_ops,
+ const_cmp,
+ const_trait_impl,
+ const_index,
+ const_convert,
+ const_result_trait_fn,
+ derive_const,
+ const_clone
+)]
+#![allow(warnings)]
+
+pub mod ap;
+pub mod array_ap;
+pub mod xp;
+#[doc(inline)]
+pub use ap::*;
diff --git a/src/xp.rs b/src/xp.rs
new file mode 100644
index 0000000..10759f3
--- /dev/null
+++ b/src/xp.rs
@@ -0,0 +1,462 @@
+//! C Interfaces and Implementations: Techniques for Creating Reusable Software [Hanson 1996-08-30]
+//!
+
+use std::cmp::Ordering;
+#[cfg(test)]
+mod test;
+/// An extended-iprecision unsigned integer is represented in base by an
+/// array of n digits, least significant digit first. Most XP functions take n as
+/// an argument along with source and destination Ts; it is SAD for n<1 or
+/// for n not to be the length of the corresponding Ts. It is SAD to pass a
+/// null T or a T that is too small to any XP function.
+pub type XP = [u8];
+
+macro_rules! base {
+ () => {
+ 256
+ };
+}
+/// sets z[0..n-1] to u mod 2⁸ⁿ and returns u/2⁸ⁿ.
+pub const fn from_int(n: u32, z: &mut XP, mut u: u128) -> u128 {
+ let mut i = 0;
+ let n = n as usize;
+ while {
+ z[i] = (u % base!()) as u8;
+ i += 1;
+
+ u /= base!();
+ u > 0 && i < n
+ } {}
+ while i < n {
+ z[i] = 0;
+ i += 1;
+ }
+ u
+}
+/// returns x mod (ULONG_MAX+1).
+pub const fn to_int(n: u32, x: &XP) -> u128 {
+ let mut u = 0;
+ let mut i = size_of::<u128>().min(n as usize);
+
+ while i > 0 {
+ i -= 1;
+ u = base!() * u + x[i] as u128;
+ }
+ u
+}
+/// returns the length of x; that is, the index plus one of the most signifi-
+/// cant nonzero digit in x[0..n-1].
+pub const fn len(mut n: u32, x: &XP) -> u32 {
+ while (n > 1 && x[n as usize - 1] == 0) {
+ n -= 1;
+ }
+ n
+}
+macro_rules! u1 {
+ ($x:expr) => {
+ match $x {
+ 0 => false,
+ 1 => true,
+ _ => panic!("not u1"),
+ }
+ };
+}
+
+/// sets z[0..n-1] to x + y + carry and returns the carry out of z[n-1].
+pub const fn add(n: u32, z: &mut XP, x: &XP, y: &XP, carry: bool) -> bool {
+ let mut carry = carry as usize;
+ let mut i = 0;
+ while i < n as usize {
+ carry += x[i] as usize + y[i] as usize;
+ z[i] = (carry % base!()) as u8;
+ carry /= base!();
+
+ i += 1;
+ }
+ u1!(carry)
+}
+/// sets z[0..n-1] to x − y − borrow and returns the borrow into z[n-1].
+pub const fn sub(
+ n: u32,
+ z: &mut XP,
+ x: &XP,
+ y: &XP,
+ borrow: bool,
+) -> bool {
+ let mut i = 0;
+ let mut borrow = borrow as u32;
+ while i < n as usize {
+ let mut d = (x[i] as u32 + base!()) - borrow - y[i] as u32;
+ z[i] = (d % base!()) as u8;
+ borrow = 1 - (d / base!());
+ i += 1;
+ }
+ u1!(borrow)
+}
+#[doc(hidden)]
+pub const unsafe fn subp(
+ n: u32,
+ z: *mut u8,
+ x: *const u8,
+ y: *const u8,
+ borrow: bool,
+) -> bool {
+ let mut i = 0;
+ let mut borrow = borrow as u32;
+ while i < n as usize {
+ let mut d =
+ (*x.add(i) as u32 + base!()) - borrow - *y.add(i) as u32;
+ *z.add(i) = (d % base!()) as u8;
+ borrow = 1 - (d / base!());
+ i += 1;
+ }
+ u1!(borrow)
+}
+/// sets z[0..n-1] to x + y, where y is a single digit, and returns the carry-out of z[n-1].
+pub const fn sum(n: u32, z: &mut XP, x: &XP, mut y: u8) -> u8 {
+ unsafe { sum_p(n, z.as_mut_ptr(), x.as_ptr(), y) }
+}
+#[doc(hidden)]
+pub const unsafe fn sum_p(
+ n: u32,
+ z: *mut u8,
+ x: *const u8,
+ mut y: u8,
+) -> u8 {
+ let mut i = 0;
+ let mut y = y as u32;
+ while i < n as usize {
+ y += *x.add(i) as u32;
+ *z.add(i) = (y % base!()) as u8;
+ y /= base!();
+ i += 1;
+ }
+ y as u8
+}
+/// sets z[0..n-1] to x − y, where y is a single digit, and returns the borrow into z[n-1].
+pub const fn diff(n: u32, z: &mut XP, x: &XP, y: u8) -> u8 {
+ let mut y = y as u32;
+ let mut i = 0;
+ while i < n as usize {
+ let d = (x[i] as u32 + base!()) - y;
+ z[i] = (d % base!()) as u8;
+ y = 1 - d / base!();
+ i += 1;
+ }
+ y as u8
+}
+/// sets z[0..n-1] to !x + carry, where carry is zero or one, and returns
+/// the carry-out of z[n-1].
+pub const fn neg(n: u32, z: &mut XP, x: &XP, carry: bool) -> bool {
+ let mut carry = carry as u32;
+ let mut i = 0;
+ while i < n as usize {
+ carry += (!x[i]) as u32;
+ z[i] = (carry % base!()) as u8;
+ carry /= base!();
+ i += 1;
+ }
+ u1!(carry)
+}
+/// adds x[0..n-1]•y[0..m-1] to z[0..n+m-1] and returns the carry-out of
+/// z[n+m-1]. If z=0, Xmul computes x•y. It is SAD for z to be the same T as x or y.
+pub const fn mul(z: &mut XP, n: u32, x: &XP, m: u32, y: &XP) -> u32 {
+ let (mut i, mut carryout) = (0, 0);
+ while i < n as usize {
+ let mut carry = 0;
+ let mut j = 0;
+ while j < m as usize {
+ carry += x[i as usize] as u32 * y[j as usize] as u32
+ + z[i + j] as u32;
+ z[i + j] = (carry % base!()) as u8;
+ carry /= base!();
+ j += 1;
+ }
+ while j < (n as usize + m as usize - i) {
+ carry += z[i + j] as u32;
+ z[i + j] = (carry % base!()) as u8;
+ carry /= base!();
+ j += 1;
+ }
+ assert!(carry == 0 || carry == 1);
+ carryout |= carry;
+ i += 1;
+ }
+ carryout
+}
+
+const unsafe fn quot_p(n: u32, z: *mut u8, x: *const u8, y: u8) -> u8 {
+ let mut i = n as isize - 1;
+ let mut carry = 0;
+
+ while i >= 0 {
+ carry = carry * base!() + (*x.add(i as _)) as u32;
+ *z.add(i as _) = (carry / y as u32) as _;
+ carry %= y as u32;
+ i -= 1;
+ }
+ carry as u8
+}
+/// sets z[0..n-1] to x/y, where y is a single digit, and returns x mod y. It
+/// is SAD for y=0
+pub const fn quot(n: u32, z: &mut XP, x: &XP, y: u8) -> u8 {
+ unsafe { quot_p(n, z.as_mut_ptr(), x.as_ptr(), y) }
+}
+/// XP_product sets z[0..n-1] to x•y and returns the carry-out of the
+/// most significant digit; the carry can be as large as 2^8- XP_quotient
+/// sets z[0..n-1] to x/y and returns the remainder, x mod y; the remainder
+/// can be as large as . For XP_product and XP_quotient, y must not
+/// exceed − 1.
+pub const fn product(n: u32, z: &mut XP, x: &XP, y: u8) -> u8 {
+ unsafe { product_p(n, z.as_mut_ptr(), x.as_ptr(), y) }
+}
+const unsafe fn product_p(n: u32, z: *mut u8, x: *const u8, y: u8) -> u8 {
+ let mut i = 0;
+ let mut carry = 0;
+ while i < n as usize {
+ carry += *x.add(i) as u32 * y as u32;
+ *z.add(i) = (carry % base!()) as u8;
+ carry /= base!();
+ i += 1;
+ }
+ carry.try_into().ok().unwrap()
+}
+/// sets q[0..n-1] to x[0..n-1]/y[0..m-1], r[0..m-1] to x[0..n-1] mod
+/// y[0..m-1]. If y=0, panics.
+/// tmp must hold at least n+m+2 digits. It is unexpected
+/// for q or r to be one of x or y, for q and r to be the same T, or for
+/// tmp to be too small
+pub const fn div(
+ mut n: u32,
+ q: &mut XP,
+ x: &XP,
+ mut m: u32,
+ y: &XP,
+ r: &mut XP,
+ tmp: &mut XP,
+) {
+ let nx = n;
+ let my = m;
+ n = len(n, x);
+ m = len(m, y);
+ if m == 1 {
+ if (y[0] == 0) {
+ panic!()
+ }
+ r[0] = quot(nx, q, x, y[0] as _);
+ let mut i = 0;
+ while i < my as usize - 1 {
+ r[1 + i] = 0;
+ i += 1;
+ }
+ } else if m > n {
+ let mut i = 0;
+ while i < nx as usize {
+ q[i] = 0;
+ i += 1;
+ }
+ r[..n as usize].copy_from_slice(&x[..n as usize]);
+ let mut i = 0;
+ while i < my - n {
+ r[(n + i) as usize] = 0;
+ i += 1;
+ }
+ } else {
+ let (rem, dq) = tmp.split_at_mut(n as usize + 1);
+ // let rem = &mut tmp[..n as usize];
+ // let dq = &mut tmp[n as usize + 1..];
+ assert!(2 <= m && m <= n);
+ rem[..n as usize].copy_from_slice(&x[..n as usize]);
+ rem[n as usize] = 0;
+ let mut k = (n - m) as i32;
+ while k >= 0 {
+ let k_ = k as u32;
+ let qk = {
+ let i = 0;
+ assert!(2 <= m && m <= k_ + m && k_ + m <= n);
+
+ let mut qk = {
+ let km = (k_ + m) as usize;
+ let y2 = y[m as usize - 1] as u64 * base!() as u64
+ + y[m as usize - 2] as u64;
+ let r3 = rem[km] as u64 * (base!() * base!())
+ + rem[km - 1] as u64 * base!()
+ + rem[km - 2] as u64;
+ let mut qk = r3 / y2;
+ if (qk >= base!()) {
+ qk = base!() - 1
+ };
+ qk as u8
+ };
+ // qk y[m-2..m-1]/rem[k+m-2..k+m] 314
+ dq[m as usize] = product(m, dq, y, qk) as _;
+ let mut i = m as i32;
+ // ch
+ while i > 0 && rem[(i + k) as usize] == dq[i as usize] {
+ i -= 1;
+ }
+
+ if (rem[(i + k) as usize] < dq[i as usize]) {
+ qk -= 1;
+ dq[m as usize] = product(m, dq, y, qk) as _;
+ }
+ qk
+ };
+ q[k as usize] = qk;
+ {
+ assert!(0 <= k && k <= k + m as i32);
+ let borrow = unsafe {
+ subp(
+ m + 1,
+ rem.as_mut_ptr().add(k as _),
+ rem.as_ptr().add(k as _),
+ dq.as_ptr(),
+ false,
+ )
+ };
+ assert!(!borrow);
+ }
+ k -= 1;
+ }
+ r[..m as usize].copy_from_slice(&rem[..m as usize]);
+ let mut i = n - m + 1;
+ while i < nx {
+ q[i as usize] = 0;
+ i += 1;
+ }
+ let mut i = m;
+ while i < my {
+ r[i as usize] = 0;
+ i += 1;
+ }
+ r[..m as usize].copy_from_slice(&rem[..m as usize]);
+ // memcpy(r, rem, m);
+ }
+}
+
+/// sets z[0..n-1] to x[0..m-1] shifted left by s bits, and fills the vacated
+/// bits with fill, which must be zero or one. It is SADk for s<0.
+pub const fn shl(
+ n: u32,
+ z: &mut XP,
+ m: u32,
+ x: &XP,
+ mut s: u32,
+ fill: u8,
+) {
+ assert!(matches!(fill, 0 | 0xff));
+ let mut j = n as i32 - 1;
+ let mut i = (if (n > m) { m - 1 } else { n - s / 8 - 1 }) as i32;
+ while j >= (m + s / 8) as _ {
+ z[j as usize] = 0;
+ j -= 1;
+ }
+ //const fill when
+ while i >= 0 {
+ z[j as usize] = x[i as usize];
+ j -= 1;
+ i -= 1;
+ }
+ while j >= 0 {
+ z[j as usize] = fill;
+ j -= 1;
+ }
+ s %= 8;
+ if s > 0 {
+ unsafe { product_p(n, z.as_mut_ptr(), z.as_ptr(), 1 << s) };
+ z[0] |= fill >> (8 - s);
+ }
+}
+//// shifts right; see [`shl`]. If n>m, the excess bits are treated as if
+/// they were equal to fill
+pub const fn shr(
+ n: u32,
+ z: &mut XP,
+ m: u32,
+ x: &XP,
+ s: u32,
+ fill: u8,
+) -> u8 {
+ assert!(matches!(fill, 0 | 0xff));
+ let mut i = s / 8;
+ let mut j = 0;
+ while i < m && j < n {
+ z[j as usize] = x[i as usize];
+ j += 1;
+ i += 1;
+ }
+ while j < n {
+ z[j as usize] = fill;
+ j += 1;
+ }
+ let s = s % 8;
+ if s > 0 {
+ let r = unsafe { quot_p(n, z.as_mut_ptr(), z.as_ptr(), 1 << s) };
+ z[n as usize - 1] |= fill << (8 - s);
+ r
+ } else {
+ 0
+ }
+}
+/// interprets str as an unsigned integer in base using z[0..n-1] as the
+/// initial value in the conversion, and returns the first nonzero carry-out
+/// of the conversion step. If end≠null, *end points to the character in
+/// str that terminated the scan or produced a nonzero carry.
+fn from_str(n: u32, z: &mut XP, base: u8, str: &[u8]) -> u8 {
+ assert!(base < 36);
+ let mut i = 0;
+ while i < str.len() {
+ let b = str[i];
+ let b = match b {
+ b'0'..=b'9' => b - b'0',
+ b'a'..=b'z' => b - b'a',
+ _ => return 255,
+ };
+ if b > base {
+ return 255;
+ }
+ let c = unsafe { product_p(n, z.as_mut_ptr(), z.as_ptr(), base) };
+ unsafe { sum_p(n, z.as_mut_ptr(), z.as_ptr(), b as _) };
+
+ if c != 0 {
+ return c;
+ }
+
+ i += 1;
+ }
+ 0
+}
+/// fills str[0..size-1] with the character representation of x in base,
+/// sets x to zero, and returns str. It is a panic for size to be
+/// too small, or for base<2 or base>36.
+pub const fn to_str<'a>(
+ put_in: &'a mut Vec<u8>,
+ base: u8,
+ mut n: u32,
+ x: &mut XP,
+) -> &'a [u8] {
+ let mut i = 0;
+ assert!(base >= 2 && base <= 36);
+ while {
+ let r = unsafe { quot_p(n, x.as_mut_ptr(), x.as_ptr(), base) };
+ put_in.push(b"0123456789abcdefghijklmnopqrstuvxyz"[r as usize]);
+ i += 1;
+ // str[i] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[r];
+ while n > 1 && x[n as usize - 1] == 0 {
+ n -= 1;
+ }
+ n > 1 || x[0] != 0
+ } {}
+
+ put_in.as_mut_slice().reverse();
+ put_in.as_slice()
+}
+
+/// x[..n] <=> y[..n]
+pub const fn cmp(n: u32, x: &XP, y: &XP) -> Ordering {
+ let mut i = n as i32 - 1;
+ while (i > 0 && x[i as usize] == y[i as usize]) {
+ i -= 1
+ }
+ x[i as usize].cmp(&y[i as usize])
+}
diff --git a/src/xp/test.rs b/src/xp/test.rs
new file mode 100644
index 0000000..1f60bfc
--- /dev/null
+++ b/src/xp/test.rs
@@ -0,0 +1,114 @@
+use rand::Rng;
+
+use super::*;
+
+#[test]
+fn test_len() {
+ let mut z = [0u8; 16];
+ from_int(15, &mut z, 254);
+ assert_eq!(len(15, &z), 1);
+
+ let mut z2 = [0u8; 16];
+ from_int(15, &mut z2, 256);
+ assert_eq!(len(15, &z2), 2);
+}
+fn coerce<T, U>(f: impl FnMut(T, T) -> U) -> impl FnMut(T, T) -> U {
+ f
+}
+macro_rules! with {
+ (fn $ident:ident = $f:expr => $f2:expr) => {
+ #[test]
+ fn $ident() {
+ let mut r = rand::rng();
+
+ for n in 0..500 {
+ let mut b = [0; 64];
+ let mut a = [0; 64];
+ let a_ = r.next_u64() as _;
+ let b_ = r.next_u64() as _;
+ let Some(ought) =
+ coerce::<u128, Option<u128>>($f2)(a_, b_)
+ else {
+ continue;
+ };
+ // dbg!(a_, b_);
+ from_int(63, &mut a, a_);
+ from_int(63, &mut b, b_);
+
+ let mut o = coerce::<[u8; 64], u128>($f)(a, b);
+
+ // let x = to_int(63, &o);s
+ assert_eq!(o, ought);
+ }
+ }
+ };
+}
+with! {fn roundtrip = |a, b| {
+ to_int(63, &a)
+} => |a, b| Some(a) }
+with!(fn test_add = |a, b| {
+ let mut o = [0;64];
+ add(63, &mut o, &a, &b, false);
+ to_int(63, &o)
+} => |a, b| a.checked_add(b));
+with!(fn test_sub = |a, b| {
+ let mut o = [0;64];
+ sub(63, &mut o, &a, &b, false);
+ to_int(63, &o)
+} => |a: u128, b:u128| a.checked_sub(b));
+with!(fn test_mul = |a, b| {
+ let mut o = [0;126];
+ mul(&mut o,63, &a,63,&b);
+ to_int(126, &o)
+} => |a: u128, b:u128| a.checked_mul(b));
+with!(fn test_div = |a, b|{
+ let mut q = [0;63];
+ let mut r = [0;63];
+ let mut tmp = [0;63+63+2];
+ div(63, &mut q, &a, 63,&b,&mut r,&mut tmp);
+ to_int(63, &q)
+}=>|a, b| a.checked_div(b));
+with!(fn test_shl = |a, b| {
+ let mut o = [0;63];
+ shl(63,&mut o, 63, &a,to_int(63, &b) as u8 as _, 0);
+ to_int(63, &o)
+}=>|a, b| a.checked_shl(b as u8 as _));
+with!(fn test_shr = |a, b| {
+ let mut o = [0;63];
+ shr(63,&mut o, 63, &a,to_int(63, &b) as u8 as _, 0);
+ to_int(63, &o)
+}=>|a, b| a.checked_shr(b as u8 as _));
+with!(fn test_cmp = |a, b| cmp(63, &a, &b) as u128
+ =>|a, b| Some((a.cmp(&b)) as u128));
+#[test]
+fn test_tos() {
+ for n in 0..50000 {
+ let mut z = [0; 64];
+ from_int(63, &mut z, n);
+ let z = z;
+ let x = to_int(63, &z);
+ let mut str = vec![];
+
+ let str = to_str(&mut str, 10, 63, &mut { z });
+ assert_eq!(std::str::from_utf8(str), Ok(&*n.to_string()));
+ assert_eq!(x, n);
+ for b in 2..32 {
+ let mut y = vec![];
+ let mut a = [0; 64];
+
+ let str = to_str(&mut y, b, 63, &mut z.clone());
+
+ assert_eq!(from_str(63, &mut a, b, str), 0);
+ let mut t1 = [0; 33];
+ let mut t2 = [0; 33];
+ assert_eq!(
+ u64::from_str_radix(
+ std::str::from_utf8(str).unwrap(),
+ b as _
+ )
+ .unwrap() as u128,
+ n
+ );
+ }
+ }
+}