Computer Algebra System in Rust

help
22

Right now it only looks at the hash… that needs to be fixed.

23

I've found some tests that passes occasionally.

I've implemented some code with HashMaps and HashSets in personal projects.

Here error raises with the same behavior.

#[test]
fn sample_3() -> Result<(), Error> {
    /*
        (1 + x) / x == 1 + 1 / x
    */
    let b = Builder::new();
    let x = b.var("x");
    let one = b.int(1);

    let y = b.div(b.add(one.clone(), x.clone())?, x.clone())?;
    let z = b.add(one.clone(), b.div(one.clone(), x.clone())?)?;

    assert_eq!(y, z);

    Ok(())
}

#[test]
fn sample_4() -> Result<(), Error> {
    /*
        (1 + x + x * x) / x == 1 + x + 1 / x
    */
    let b = Builder::new();

    let x = b.var("x");
    let one = b.int(1);

    let x_square = b.mul(x.clone(), x.clone())?;
    let x_inv = b.div(one.clone(), x.clone())?;

    let y = b.div(
        b.add(b.add(one.clone(), x.clone())?, x_square.clone())?,
        x.clone(),
    )?;
    let z = b.add(b.add(one.clone(), x.clone())?, x_inv.clone())?;

    assert_eq!(y, z);

    Ok(())
}
24

Thanks. Should be fixed now.

25

The equality... (°-°)
Which algorithm it is based on?

I have in mind the tree abstraction I showed earlier. I'm scratching it. I have no idea how I'll implement equality for the general expression. I could just subtract one expression from the other and hope the expression to go null, or just match every two terms of the expression trees, after an expansion algorithm. Seems to be the only NP-hard way to go. Unless the structure fingerprint is known and kept in cache, during creation and manipulation.

In Bullet case, the Builder holds a HashMap which you called Cache. Then you match nodes of both structures. But the creation and manipulation history of the expressions can differ, then the Cache can differ too, can't they? How do you force them to be equal? I suspect that after any operation, a simplification algorithm is executed. Is that so? Does the Builder always work on a simplified structure?

26

Yes. A simplified and sorted structure.

The downside is that it will always rearrange your inputs.

27

I've been prototyping a symbolic library with the syntax I mentioned in the tests I proposed. But no big deal yet. It is not meant to be a CAS, but to provide an extensible symbolic framework to build greater stuff.

https://github.com/nelsonatgithub/ncas

#[test]
fn sample() {
    use crate::base::symbols::{number::Number, variable::Variable};

    assert_eq!(1 + Number::new(1.0), Number::new(1.0) + Number::new(1.0));
    assert_eq!(1.0 + Number::new(1.0), Number::new(1.0) + Number::new(1.0));
    assert_eq!(Number::new(1.0) + 1, Number::new(1.0) + Number::new(1.0));
    assert_eq!(Number::new(1.0) + 1.0, Number::new(1.0) + Number::new(1.0));

    assert_eq!(
        Number::new(1.0) + "a",
        Number::new(1.0) + Variable::new(String::from("a"))
    );

    let mut sum = Number::new(0.0);
    for _ in 0..10 {
        sum = sum + Number::new(1.0);
    }

    assert_eq!(sum.into_num(), Ok(10.0));
}

What have been done so far:

  • std::ops::{Neg, Add, Sub, Div, Mul, BitXor} overloading.
  • numerical evaluation
  • struct that generalizes the expression

@s3bk I substituted that binary Association idea for commutative operations like Addition and Multiplication by a CommutativeAssociation which holds a Vec<Expression> instead. This way it is easier to iterate over commutative parts of the expression.

I should implement std::cmp::Ordering to the Expression, so that it will easier to simplify commutative elements and even easier to compare expressions. Then I should replace Vec for BinaryHeap.

I've been focusing on:

  • basic arithmetics functionality for symbolics
  • TDD, Legibility, Scalability

I'm still not sure if the struct I chose was a good one. Sympy's is different as they use dictionaries. I have std::collections::* in hands and trust it strongly.

I've been searching for symbolic expansion and simplification in literature. I also searched for simplification in Sympy source code. Which is not a trivial subject. [1] [2] [3].

I shall implement:

  • basic identities simplification
  • trigonometrics
  • exponentials (powers & logarithmics)
  • derivation and integration
  • string interpreter [edit]

There are more advanced topics such as Polynomial Factorization, Equation Solvers, Numerical Differential Equation Solvers, Fourier and Laplace Transforms. Those topics, I do not intend to implement. Because those have specific concerns. But, if the necessity comes and this repository happens to become stable, I'd be interesting to have independent implementations of top of this one.

But I do intend to cover differentiation, integration, simplification, expansion and expression equality, with polynomials, exponential, logarithmic and trigonometric functions.

I'm still studying including algebraics or equivalent @programmerjake in order to provide precision to numerical results. Currently, I'm returning a default f64.

@XVilka I still haven't spent time to study how math_traits can be incorporated, but I shall do it in the future.

I'm also analyzing how to handle matrices. I should focus on including nalgebra, soon. [Edit]

References

  • [1] Cohen, Joel S. Computer Algebra and Symbolic Computation: Mathematical Methods. 2003 by A K Peters, Ltd.
  • [2] Cohen, Joel S. Computer Algebra and Symbolic Computation: Elementary Algorithms. 2002 by A K Peters, Ltd.
  • [3] Geddes, K.O., Czapor S.R., Labahn, G. Algorithms for Computer Algebra. 1992 by Kluwer Academic Publishers.
1 Like
28

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.