reals/
property.rs

1use crate::util;
2
3use num::{BigInt, BigRational, One, Signed, ToPrimitive, Zero};
4
5// Reduces sin(pi*n) and tan(pi*n) to the [-1/2, 3/2) interval.
6fn reduce_trig_arg(arg: BigRational) -> BigRational {
7    if arg < BigRational::new((-1).into(), 2.into()) || arg >= BigRational::new(3.into(), 2.into())
8    {
9        let floor = (arg.clone() + BigRational::one()).floor().to_integer();
10        // round down to the nearest even number
11        let offset = floor & !BigInt::one();
12        return arg - BigRational::from_integer(offset);
13    }
14    arg
15}
16
17/// A symbolic tag for the underlying computable real.
18///
19/// Effectively determines an `f(arg)`, where the range of arg is carefully
20/// restricted such that `f(arg)` is irrational and monotonic, unless Kind is
21/// [`Kind::One`].
22#[derive(Debug, Clone, PartialEq, PartialOrd)]
23pub enum Kind {
24    One,
25    Pi,
26    /// `sqrt(arg)`, where `arg > 0` and `arg != 1`
27    Sqrt,
28    /// `exp(arg)`, where `arg != 0`
29    Exp,
30    /// `ln(arg)`, where `arg > 1`
31    Ln,
32    /// `log(arg)`, where `arg > 1` and `arg` is not a power of 10
33    Log,
34    /// `sin(pi*arg)`, where `arg in (0, 1/2)` and `arg != 1/6, 1/4, 1/3`
35    SinPi,
36    /// `tan(pi*arg)`, where `arg in (0, 1/2)` and `arg != 1/6, 1/4, 1/3`
37    TanPi,
38    /// `asin(arg)`, where `arg in (-1, 1)` and `arg != -1/2, 1/2`
39    Asin,
40    /// `atan(arg)`, where `arg in (-1, 1)` and `arg != 0`
41    Atan,
42    Irrational,
43}
44
45/// A symbolic representation of a computable real number.
46#[derive(Debug, Clone, PartialEq)]
47pub struct Property {
48    pub kind: Kind,
49    pub arg: Option<BigRational>,
50}
51
52impl Property {
53    pub(crate) fn one() -> Self {
54        Self {
55            kind: Kind::One,
56            arg: None,
57        }
58    }
59
60    pub(crate) fn pi() -> Self {
61        Self {
62            kind: Kind::Pi,
63            arg: None,
64        }
65    }
66
67    pub(crate) fn irrational() -> Self {
68        Self {
69            kind: Kind::Irrational,
70            arg: None,
71        }
72    }
73
74    pub(crate) fn clone_raw_with_arg(&self, arg: BigRational) -> RawProperty {
75        RawProperty::new(self.kind.clone(), Some(arg))
76    }
77
78    pub(crate) fn clone_with_arg(&self, arg: BigRational) -> Option<Self> {
79        self.clone_raw_with_arg(arg).validate()
80    }
81
82    /// Checks whether a SQRT property's argument is minimal.
83    pub(crate) fn irreducible_sqrt(&self) -> bool {
84        match &self.arg {
85            Some(arg) => match self.kind {
86                Kind::Sqrt => {
87                    // `int_extract_square` can correctly extract from inputs
88                    // up to 3179.
89                    // We test primes until 13, and small integers until 10,
90                    // so giving it 17^2 * 11 = 3179 will break it.
91                    const EXTRACT_SQUARE_MAX: u64 = 3179;
92                    // TODO - why 30?
93                    arg.numer().bits() <= 30
94                        && arg.denom().bits() <= 30
95                        && arg.numer().abs() < EXTRACT_SQUARE_MAX.into()
96                        && arg.denom().abs() < EXTRACT_SQUARE_MAX.into()
97                }
98                _ => false,
99            },
100            None => true,
101        }
102    }
103
104    /// Returns a unicode symbloc representation of the property if possible.
105    pub(crate) fn symbolic(&self) -> Option<String> {
106        fn pi_multiple(r: &BigRational) -> String {
107            if r.is_zero() {
108                "".to_string()
109            } else if r.is_one() {
110                "π".to_string()
111            } else {
112                format!("{}π", r)
113            }
114        }
115
116        match self.kind {
117            Kind::One => Some("".to_string()),
118            Kind::Pi => Some("π".to_string()),
119            Kind::Exp => match &self.arg {
120                None => None,
121                Some(r) if r.is_one() => Some("e".to_string()),
122                Some(r) => Some(format!("exp({})", r)),
123            },
124            Kind::Sqrt => match &self.arg {
125                None => None,
126                Some(r) if r.is_integer() => Some(format!("√{}", r)),
127                Some(r) => Some(format!("√({})", r)),
128            },
129            Kind::Ln => self.arg.as_ref().map(|r| format!("ln({})", r)),
130            Kind::Log => self.arg.as_ref().map(|r| format!("log({})", r)),
131            Kind::SinPi => self
132                .arg
133                .as_ref()
134                .map(|r| format!("sin({})", pi_multiple(r))),
135            Kind::TanPi => self
136                .arg
137                .as_ref()
138                .map(|r| format!("tan({})", pi_multiple(r))),
139            Kind::Asin => self.arg.as_ref().map(|r| format!("asin({})", r)),
140            Kind::Atan => self.arg.as_ref().map(|r| format!("atan({})", r)),
141            Kind::Irrational => None,
142        }
143    }
144
145    /// Returns an n such that x >= 2^n, where x is the associated computable
146    /// real.
147    pub(crate) fn msb_bound(&self) -> Option<i32> {
148        match self.kind {
149            Kind::One => Some(0),
150            Kind::Pi => Some(1),
151            Kind::Sqrt => match &self.arg {
152                Some(r) => {
153                    let bits = util::rational::estimate_whole_bits(r)?;
154                    Some((bits >> 1) - 2)
155                }
156                None => None,
157            },
158            Kind::Ln | Kind::Log => match &self.arg {
159                Some(r) => {
160                    if r >= &BigRational::from_integer(2.into()) {
161                        // ln(2) > log(2) > 1/4
162                        Some(-2)
163                    } else {
164                        None
165                    }
166                }
167                None => None,
168            },
169            Kind::Exp => match &self.arg {
170                Some(r) => {
171                    let floor = r.floor().to_integer();
172                    if floor.bits() <= 30 {
173                        let floor = floor.to_i32().unwrap();
174                        if floor < 0 {
175                            // Multiple by a bit more than 1/ln(2)
176                            Some((floor / 2 - 1) * 3)
177                        } else {
178                            // Mulitple by a bit less than 1/ln(2)
179                            Some(floor * 7 / 5)
180                        }
181                    } else if floor.is_positive() {
182                        Some(100_000_000)
183                    } else {
184                        None
185                    }
186                }
187                None => None,
188            },
189            Kind::SinPi | Kind::TanPi | Kind::Asin | Kind::Atan => match &self.arg {
190                Some(r) => {
191                    if r >= &BigRational::new(1.into(), 1024.into()) {
192                        Some(-11)
193                    } else {
194                        None
195                    }
196                }
197                None => None,
198            },
199            Kind::Irrational => None,
200        }
201    }
202
203    /// Technically a property is always non zero as long as the argument
204    /// passes the validation.
205    /// We intentionally do not guarantee this for exp(arg) where arg is
206    /// very negative, as it is expensive to distinguish it from zero.
207    pub(crate) fn is_non_zero(&self) -> bool {
208        match self.kind {
209            Kind::Exp => match &self.arg {
210                Some(r) => *r >= BigRational::from_integer((-10000).into()),
211                None => false,
212            },
213            _ => true,
214        }
215    }
216}
217
218pub struct RawProperty {
219    pub kind: Kind,
220    pub arg: Option<BigRational>,
221}
222
223impl RawProperty {
224    pub fn new(kind: Kind, arg: Option<BigRational>) -> Self {
225        RawProperty { kind, arg }
226    }
227
228    pub fn clone_with_arg(&self, arg: BigRational) -> Self {
229        Self::new(self.kind.clone(), Some(arg))
230    }
231
232    pub fn sqrt(arg: BigRational) -> Self {
233        Self::new(Kind::Sqrt, Some(arg))
234    }
235
236    pub fn exp(arg: BigRational) -> Self {
237        Self::new(Kind::Exp, Some(arg))
238    }
239
240    pub fn log(arg: BigRational) -> Self {
241        Self::new(Kind::Log, Some(arg))
242    }
243
244    pub fn ln(arg: BigRational) -> Self {
245        Self::new(Kind::Ln, Some(arg))
246    }
247
248    pub fn sin(arg: BigRational) -> Self {
249        Self::new(Kind::SinPi, Some(reduce_trig_arg(arg)))
250    }
251
252    pub fn tan(arg: BigRational) -> Self {
253        Self::new(Kind::TanPi, Some(reduce_trig_arg(arg)))
254    }
255
256    pub fn asin(arg: BigRational) -> Self {
257        Self::new(Kind::Asin, Some(arg))
258    }
259
260    pub fn atan(arg: BigRational) -> Self {
261        Self::new(Kind::Atan, Some(arg))
262    }
263
264    pub fn validate(&self) -> Option<Property> {
265        use Kind::*;
266
267        let validated = match self.kind {
268            One | Pi | Irrational => true,
269            _ => match &self.arg {
270                None => false,
271                Some(r) => match self.kind {
272                    Sqrt => r.is_positive() && *r != BigRational::one(),
273                    Exp => !r.is_zero(),
274                    Log => {
275                        *r > BigRational::one()
276                            && (!r.is_integer()
277                                || util::int::exact_log(&r.to_integer(), 10).is_none())
278                    }
279                    Ln => *r > BigRational::one(),
280                    SinPi | TanPi => {
281                        r.is_positive()
282                            && r < &BigRational::new(1.into(), 2.into())
283                            && r != &BigRational::new(1.into(), 3.into())
284                            && r != &BigRational::new(1.into(), 4.into())
285                            && r != &BigRational::new(1.into(), 6.into())
286                    }
287                    Asin => {
288                        *r > -BigRational::one()
289                            && *r < BigRational::one()
290                            && *r != BigRational::new(1.into(), 2.into())
291                            && *r != BigRational::new((-1).into(), 2.into())
292                            && *r != BigRational::zero()
293                    }
294                    Atan => {
295                        *r != BigRational::one()
296                            && *r != -BigRational::one()
297                            && *r != BigRational::zero()
298                    }
299                    _ => false,
300                },
301            },
302        };
303
304        if validated {
305            Some(Property {
306                kind: self.kind.clone(),
307                arg: self.arg.clone(),
308            })
309        } else {
310            None
311        }
312    }
313}
reals/property.rs

reals/
property.rs
