atmos/os_lib/aura/
number.rs

1// BigInt / Ratio / Complex の数値整形メソッド。Display 化せず inherent to_string を温存する。
2#![allow(clippy::inherent_to_string)]
3
4use alloc::string::String;
5use alloc::vec::Vec;
6use core::cmp::Ordering;
7
8#[derive(Clone, Debug, Eq)]
9pub struct BigInt {
10    pub sign: bool,      // true if positive or zero, false if negative
11    pub digits: Vec<u8>, // base 10, little endian (digits[0] is the ones place)
12}
13
14impl PartialEq for BigInt {
15    fn eq(&self, other: &Self) -> bool {
16        self.cmp(other) == Ordering::Equal
17    }
18}
19
20impl PartialOrd for BigInt {
21    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
22        Some(self.cmp(other))
23    }
24}
25
26impl Ord for BigInt {
27    fn cmp(&self, other: &Self) -> Ordering {
28        if self.digits.is_empty() && other.digits.is_empty() {
29            return Ordering::Equal;
30        }
31        let is_zero = |b: &BigInt| b.digits.is_empty() || (b.digits.len() == 1 && b.digits[0] == 0);
32        if is_zero(self) && is_zero(other) {
33            return Ordering::Equal;
34        }
35
36        if self.sign != other.sign {
37            return if self.sign {
38                Ordering::Greater
39            } else {
40                Ordering::Less
41            };
42        }
43
44        let abs_cmp = Self::cmp_abs(&self.digits, &other.digits);
45        if self.sign {
46            abs_cmp
47        } else {
48            abs_cmp.reverse()
49        }
50    }
51}
52
53impl BigInt {
54    pub fn zero() -> Self {
55        Self {
56            sign: true,
57            digits: alloc::vec![0],
58        }
59    }
60
61    pub fn one() -> Self {
62        Self {
63            sign: true,
64            digits: alloc::vec![1],
65        }
66    }
67
68    pub fn from_i64(mut val: i64) -> Self {
69        if val == 0 {
70            return Self::zero();
71        }
72        let sign = val >= 0;
73        if !sign {
74            val = -val;
75        }
76        let mut digits = Vec::new();
77        let mut n = val as u64;
78        while n > 0 {
79            digits.push((n % 10) as u8);
80            n /= 10;
81        }
82        Self { sign, digits }
83    }
84
85    pub fn to_i64(&self) -> Option<i64> {
86        let mut res: i64 = 0;
87        let mut mult: i64 = 1;
88        for &d in &self.digits {
89            if let Some(m) = (d as i64).checked_mul(mult) {
90                if let Some(r) = res.checked_add(m) {
91                    res = r;
92                } else {
93                    return None;
94                }
95            } else {
96                return None;
97            }
98            if let Some(next_mult) = mult.checked_mul(10) {
99                mult = next_mult;
100            } else if self.digits.last() != Some(&d) {
101                return None;
102            }
103        }
104        if !self.sign {
105            res = -res;
106        }
107        Some(res)
108    }
109
110    pub fn from_string(s: &str) -> Option<Self> {
111        let s = s.trim();
112        if s.is_empty() {
113            return None;
114        }
115        let mut sign = true;
116        let mut start = 0;
117        if s.starts_with('-') {
118            sign = false;
119            start = 1;
120        } else if s.starts_with('+') {
121            start = 1;
122        }
123
124        let mut digits = Vec::new();
125        for ch in s.get(start..).unwrap_or("").chars().rev() {
126            if let Some(d) = ch.to_digit(10) {
127                digits.push(d as u8);
128            } else {
129                return None;
130            }
131        }
132        let mut b = Self { sign, digits };
133        b.trim_leading_zeros();
134        Some(b)
135    }
136
137    pub fn from_str_radix(s: &str, radix: u32) -> Option<Self> {
138        let s = s.trim();
139        if s.is_empty() {
140            return None;
141        }
142
143        let mut res = BigInt::zero();
144        let big_radix = BigInt::from_i64(radix as i64);
145
146        for ch in s.chars() {
147            let digit = ch.to_digit(radix)?;
148            let big_digit = BigInt::from_i64(digit as i64);
149            res = res.mul(&big_radix).add(&big_digit);
150        }
151
152        Some(res)
153    }
154
155    pub fn is_zero(&self) -> bool {
156        self.digits.is_empty() || (self.digits.len() == 1 && self.digits[0] == 0)
157    }
158
159    fn trim_leading_zeros(&mut self) {
160        while self.digits.len() > 1 && self.digits.last() == Some(&0) {
161            self.digits.pop();
162        }
163        if self.is_zero() {
164            self.sign = true;
165        }
166    }
167
168    fn cmp_abs(a: &[u8], b: &[u8]) -> Ordering {
169        if a.len() != b.len() {
170            return a.len().cmp(&b.len());
171        }
172        for (da, db) in a.iter().rev().zip(b.iter().rev()) {
173            if da != db {
174                return da.cmp(db);
175            }
176        }
177        Ordering::Equal
178    }
179
180    pub fn add(&self, other: &Self) -> Self {
181        if self.sign == other.sign {
182            let mut res = Self {
183                sign: self.sign,
184                digits: Self::add_abs(&self.digits, &other.digits),
185            };
186            res.trim_leading_zeros();
187            res
188        } else {
189            // signs differ: a + (-b) == a - b
190            let cmp = Self::cmp_abs(&self.digits, &other.digits);
191            match cmp {
192                Ordering::Equal => Self::zero(),
193                Ordering::Greater => {
194                    let mut res = Self {
195                        sign: self.sign,
196                        digits: Self::sub_abs(&self.digits, &other.digits),
197                    };
198                    res.trim_leading_zeros();
199                    res
200                }
201                Ordering::Less => {
202                    let mut res = Self {
203                        sign: other.sign,
204                        digits: Self::sub_abs(&other.digits, &self.digits),
205                    };
206                    res.trim_leading_zeros();
207                    res
208                }
209            }
210        }
211    }
212
213    pub fn sub(&self, other: &Self) -> Self {
214        let mut neg_other = other.clone();
215        if !neg_other.is_zero() {
216            neg_other.sign = !neg_other.sign;
217        }
218        self.add(&neg_other)
219    }
220
221    fn add_abs(a: &[u8], b: &[u8]) -> Vec<u8> {
222        let max_len = core::cmp::max(a.len(), b.len());
223        let mut res = Vec::with_capacity(max_len + 1);
224        let mut carry = 0;
225        for i in 0..max_len {
226            let da = if i < a.len() { a[i] } else { 0 };
227            let db = if i < b.len() { b[i] } else { 0 };
228            let sum = da + db + carry;
229            res.push(sum % 10);
230            carry = sum / 10;
231        }
232        if carry > 0 {
233            res.push(carry);
234        }
235        res
236    }
237
238    fn sub_abs(a: &[u8], b: &[u8]) -> Vec<u8> {
239        // Assume a >= b
240        let mut res = Vec::with_capacity(a.len());
241        let mut borrow = 0;
242        for i in 0..a.len() {
243            let da = a[i] as i16;
244            let db = if i < b.len() { b[i] as i16 } else { 0 };
245            let mut diff = da - db - borrow;
246            if diff < 0 {
247                diff += 10;
248                borrow = 1;
249            } else {
250                borrow = 0;
251            }
252            res.push(diff as u8);
253        }
254        res
255    }
256
257    pub fn mul(&self, other: &Self) -> Self {
258        if self.is_zero() || other.is_zero() {
259            return Self::zero();
260        }
261        let mut res_digits = alloc::vec![0; self.digits.len() + other.digits.len()];
262        for (i, &da) in self.digits.iter().enumerate() {
263            let mut carry = 0;
264            for (j, &db) in other.digits.iter().enumerate() {
265                let prod = res_digits[i + j] as u16 + (da as u16 * db as u16) + carry;
266                res_digits[i + j] = (prod % 10) as u8;
267                carry = prod / 10;
268            }
269            if carry > 0 {
270                res_digits[i + other.digits.len()] += carry as u8;
271            }
272        }
273        let mut res = Self {
274            sign: self.sign == other.sign,
275            digits: res_digits,
276        };
277        res.trim_leading_zeros();
278        res
279    }
280
281    pub fn div_rem(&self, other: &Self) -> Option<(Self, Self)> {
282        if other.is_zero() {
283            return None;
284        } // Divide by zero
285        if Self::cmp_abs(&self.digits, &other.digits) == Ordering::Less {
286            return Some((Self::zero(), self.clone()));
287        }
288
289        let mut q_digits = alloc::vec![0; self.digits.len()];
290        let mut current = Vec::new();
291
292        for i in (0..self.digits.len()).rev() {
293            current.insert(0, self.digits[i]);
294            // trim current
295            while current.len() > 1 && current.last() == Some(&0) {
296                current.pop();
297            }
298
299            let mut count = 0;
300            while Self::cmp_abs(&current, &other.digits) != Ordering::Less {
301                current = Self::sub_abs(&current, &other.digits);
302                while current.len() > 1 && current.last() == Some(&0) {
303                    current.pop();
304                }
305                count += 1;
306            }
307            q_digits[i] = count;
308        }
309
310        let mut q = Self {
311            sign: self.sign == other.sign,
312            digits: q_digits,
313        };
314        q.trim_leading_zeros();
315
316        let mut r = Self {
317            sign: self.sign,
318            digits: current,
319        };
320        r.trim_leading_zeros();
321
322        Some((q, r))
323    }
324
325    pub fn gcd(&self, other: &Self) -> Self {
326        let mut a = self.clone();
327        a.sign = true;
328        let mut b = other.clone();
329        b.sign = true;
330
331        while !b.is_zero() {
332            if let Some((_, r)) = a.div_rem(&b) {
333                a = b;
334                b = r;
335            } else {
336                break;
337            }
338        }
339        a
340    }
341
342    pub fn lcm(&self, other: &Self) -> Self {
343        if self.is_zero() || other.is_zero() {
344            return Self::zero();
345        }
346        let gcd = self.gcd(other);
347        let mut prod = self.mul(other);
348        prod.sign = true;
349        // 両辺非ゼロを確認済みのため gcd は非ゼロで div_rem は必ず成功する
350        match prod.div_rem(&gcd) {
351            Some((lcm, _)) => lcm,
352            None => Self::zero(),
353        }
354    }
355
356    pub fn to_string(&self) -> String {
357        if self.is_zero() {
358            return String::from("0");
359        }
360        let mut s = String::new();
361        if !self.sign {
362            s.push('-');
363        }
364        for d in self.digits.iter().rev() {
365            s.push((b'0' + d) as char);
366        }
367        s
368    }
369}
370
371// ----------------------------------------------------
372// Ratio
373// ----------------------------------------------------
374
375#[derive(Clone, Debug, Eq, PartialEq)]
376pub struct Ratio {
377    pub num: BigInt,
378    pub den: BigInt,
379}
380
381impl Ratio {
382    pub fn new(mut num: BigInt, mut den: BigInt) -> Option<Self> {
383        if den.is_zero() {
384            return None;
385        }
386
387        if num.is_zero() {
388            return Some(Self {
389                num,
390                den: BigInt::one(),
391            });
392        }
393
394        if !den.sign {
395            num.sign = !num.sign;
396            den.sign = true;
397        }
398
399        let mut r = Self { num, den };
400        r.reduce();
401        Some(r)
402    }
403
404    pub fn from_bigint(num: BigInt) -> Self {
405        Self {
406            num,
407            den: BigInt::one(),
408        }
409    }
410
411    fn reduce(&mut self) {
412        let gcd = Self::gcd_abs(&self.num.digits, &self.den.digits);
413        if gcd.digits.len() == 1 && gcd.digits[0] == 1 {
414            return;
415        }
416        if let Some((n_num, _)) = self.num.div_rem(&gcd) {
417            self.num = n_num;
418        }
419        if let Some((n_den, _)) = self.den.div_rem(&gcd) {
420            self.den = n_den;
421        }
422    }
423
424    fn gcd_abs(a: &[u8], b: &[u8]) -> BigInt {
425        let mut x = BigInt {
426            sign: true,
427            digits: a.to_vec(),
428        };
429        x.trim_leading_zeros();
430
431        let mut y = BigInt {
432            sign: true,
433            digits: b.to_vec(),
434        };
435        y.trim_leading_zeros();
436
437        while !y.is_zero() {
438            if let Some((_, r)) = x.div_rem(&y) {
439                x = y;
440                y = r;
441            } else {
442                break;
443            }
444        }
445        x
446    }
447
448    /// `new` が失敗 (分母ゼロ) した場合に panic せず 0 を返すフォールバック付き生成。
449    /// 分母非ゼロは呼び出し側の不変条件であり、通常は `new` がそのまま成功する。
450    pub fn new_or_zero(num: BigInt, den: BigInt) -> Self {
451        Self::new(num, den).unwrap_or_else(|| Ratio {
452            num: BigInt::zero(),
453            den: BigInt::from_i64(1),
454        })
455    }
456
457    pub fn add(&self, other: &Self) -> Self {
458        let num1 = self.num.mul(&other.den);
459        let num2 = other.num.mul(&self.den);
460        let new_num = num1.add(&num2);
461        let new_den = self.den.mul(&other.den);
462        Self::new_or_zero(new_num, new_den)
463    }
464
465    pub fn sub(&self, other: &Self) -> Self {
466        let num1 = self.num.mul(&other.den);
467        let num2 = other.num.mul(&self.den);
468        let new_num = num1.sub(&num2);
469        let new_den = self.den.mul(&other.den);
470        Self::new_or_zero(new_num, new_den)
471    }
472
473    pub fn mul(&self, other: &Self) -> Self {
474        Self::new_or_zero(self.num.mul(&other.num), self.den.mul(&other.den))
475    }
476
477    pub fn div(&self, other: &Self) -> Option<Self> {
478        if other.num.is_zero() {
479            return None;
480        }
481        Self::new(self.num.mul(&other.den), self.den.mul(&other.num))
482    }
483
484    pub fn to_string(&self) -> String {
485        if self.den == BigInt::one() {
486            self.num.to_string()
487        } else {
488            alloc::format!("{}/{}", self.num.to_string(), self.den.to_string())
489        }
490    }
491
492    pub fn to_f64(&self) -> f64 {
493        let num_f64 = self.num.to_i64().unwrap_or(0) as f64; // Fallback to 0 if too large
494        let den_f64 = self.den.to_i64().unwrap_or(1) as f64;
495        num_f64 / den_f64
496    }
497
498    pub fn from_f64(val: f64) -> Option<Self> {
499        if val.is_nan() || val.is_infinite() {
500            return None;
501        }
502        let mult = 1_000_000_000_000.0;
503        let num_val = (val * mult) as i64;
504        let den_val = mult as i64;
505        Self::new(BigInt::from_i64(num_val), BigInt::from_i64(den_val))
506    }
507}
508
509// ----------------------------------------------------
510// Complex
511// ----------------------------------------------------
512
513#[derive(Clone, Debug, Eq, PartialEq)]
514pub struct Complex {
515    pub real: Ratio,
516    pub imag: Ratio,
517}
518
519impl Complex {
520    pub fn new(real: Ratio, imag: Ratio) -> Self {
521        Self { real, imag }
522    }
523
524    pub fn add(&self, other: &Self) -> Self {
525        Self {
526            real: self.real.add(&other.real),
527            imag: self.imag.add(&other.imag),
528        }
529    }
530
531    pub fn sub(&self, other: &Self) -> Self {
532        Self {
533            real: self.real.sub(&other.real),
534            imag: self.imag.sub(&other.imag),
535        }
536    }
537
538    pub fn mul(&self, other: &Self) -> Self {
539        // (a + bi)(c + di) = (ac - bd) + (ad + bc)i
540        let ac = self.real.mul(&other.real);
541        let bd = self.imag.mul(&other.imag);
542        let real = ac.sub(&bd);
543
544        let ad = self.real.mul(&other.imag);
545        let bc = self.imag.mul(&other.real);
546        let imag = ad.add(&bc);
547
548        Self { real, imag }
549    }
550
551    pub fn div(&self, other: &Self) -> Option<Self> {
552        // (a + bi) / (c + di) = ((ac + bd) + (bc - ad)i) / (c^2 + d^2)
553        let c2 = other.real.mul(&other.real);
554        let d2 = other.imag.mul(&other.imag);
555        let den = c2.add(&d2);
556
557        if den.num.is_zero() {
558            return None;
559        }
560
561        let ac = self.real.mul(&other.real);
562        let bd = self.imag.mul(&other.imag);
563        let real_num = ac.add(&bd);
564
565        let bc = self.imag.mul(&other.real);
566        let ad = self.real.mul(&other.imag);
567        let imag_num = bc.sub(&ad);
568
569        let real = real_num.div(&den)?;
570        let imag = imag_num.div(&den)?;
571
572        Some(Self { real, imag })
573    }
574
575    pub fn to_string(&self) -> String {
576        if self.imag.num.is_zero() {
577            return self.real.to_string();
578        }
579        let imag_str = self.imag.to_string();
580        if self.real.num.is_zero() {
581            return alloc::format!("{}i", imag_str);
582        }
583
584        if !self.imag.num.sign {
585            let mut pos_imag = self.imag.clone();
586            pos_imag.num.sign = true;
587            alloc::format!("{}-{}i", self.real.to_string(), pos_imag.to_string())
588        } else {
589            alloc::format!("{}+{}i", self.real.to_string(), imag_str)
590        }
591    }
592}
atmos/os_lib/aura/number.rs

atmos/os_lib/aura/
number.rs
