crowlogic / arb4j

arb4j is a Java API for the arbitrary precision ball arithmetic library found at http://arblib.org
Other
1 stars 0 forks source link

expression compiler: automatic differentiation #253

Open crowlogic opened 1 year ago

crowlogic commented 1 year ago

Implementing Automatic Differentiator

This issue tracks the implementation of an automatic differentiator for the expression compiler. The compiler parses expressions into binary trees, and this differentiator will apply differentiation rules recursively based on the tree structure.

Algorithm Outline

  1. Base Case:

    • For leaf nodes:
      • If a constant, derivative = 0.
      • If a variable, derivative = 1 for the differentiation variable, otherwise 0.
  2. Differentiation Rules:

    • Addition/Subtraction Nodes: Derivative of a sum/difference is the sum/difference of the derivatives.
    • Multiplication Nodes (Product Rule): For a product $f g$, derivative = $f' g + f * g'$.
    • Division Nodes (Quotient Rule): For a division $f / g$, derivative = $(f' g - f g') / g^2$.
    • Exponential and Logarithmic Functions: Apply respective differentiation rules.
    • Trigonometric Functions: Apply differentiation rules for sine, cosine, etc.
    • Power Nodes: Apply power rule or generalized power rule.
  3. Recursive Application:

    • Apply these rules to each child node to compute $f'$ and $g'$
  4. Construct New Tree:

    • Construct a new tree representing the derivative.
  5. Simplification (Optional):

    • Simplify the resulting tree to combine like terms, simplify constants, etc.

Stuff To Be Done And Whatnot

crowlogic commented 1 year ago

When designing this it would be good to take into account and tie it into this paradigm as well since this relies on repeated differentiation which will need to be done automatically

Rodrigues' Formula and Orthogonal Polynomials

Rodrigues' formula is a mathematical expression that provides an efficient way to generate certain orthogonal polynomials. Orthogonal polynomials play a pivotal role in various branches of mathematics, including approximation theory, differential equations, and even quantum mechanics.

What is Rodrigues' Formula?

For a given differential operator $D$ and weight function $w(x)$, the Rodrigues' formula for an orthogonal polynomial $P_n(x)$ is given by:

$$P_n(x) = \frac{1}{w(x) n!} D^n [w(x) f(x)]$$

Here, $n$ denotes the order of the polynomial, and $f(x)$ is a function specific to the type of orthogonal polynomial under consideration.

Examples:

  1. Legendre Polynomials: The Rodrigues' formula for the Legendre polynomials $P_n(x)$ is:

$$P_n(x) = \frac{1}{2^n n!} \frac{d^n}{dx^n} (x^2 - 1)^n$$

  1. Hermite Polynomials: The Hermite polynomials $H_n(x)$ are described by:

$$H_n(x) = (-1)^n e^{x^2} \frac{d^n}{dx^n} e^{-x^2}$$

In both examples, differentiation acts as an iterated linear function to generate the nth polynomial in the sequence.

Connection to Linear Iterated Functions Systems (L.I.F.S.)

The study of orthogonal polynomials can be extended to consider measures generated by Linear Iterated Functions Systems, or L.I.F.S. This is a more advanced topic, delving into the interplay between orthogonal polynomials and iterative linear processes, especially in the context of Fourier analysis.

In more advanced research, like the paper by Giorgio Mantica and Davide Guzzetti, the authors explore the asymptotic behavior of the Fourier transforms of orthogonal polynomials, relating them to measures generated by L.I.F.S.

Conclusion

The Rodrigues' formula serves as a foundation for understanding and generating orthogonal polynomials. As mathematics advances, the interplay between these polynomials, linear iterated systems, and Fourier analysis continues to offer rich areas for exploration and discovery.

crowlogic commented 11 months ago

Fluent Programming Style in Java

In Java, the fluent programming style, often seen in method chaining, is where you can call multiple methods on objects in a single statement. Each method returns an object, allowing the next method in the chain to be invoked on it. This style is popular in builder patterns, streams, and other API designs where it enhances readability and flow of the code. For example:

myObject.methodOne().methodTwo().methodThree();

In this style, each method invocation returns an object, which may not necessarily be of the same type as the input object. The type of the output defaults to the input type unless explicitly specified by the caller, particularly in cases where the last argument of the function is the result variable.

Composition of Functions in Mathematics

In mathematics, function composition is the application of one function to the result of another to produce a third function. For example, if $f$ and $g$ are two functions, their composition $(f \circ g)(x)$ is defined as $f(g(x))$. This is a fundamental concept in mathematics, particularly in fields like calculus and algebra.

Similarity

The similarity lies in the way operations or functions are applied in a sequence, each taking the output of the previous one as its input:

Difference

While structurally similar, the contexts and applications of these concepts are different:

In summary, while the two concepts are not identical, the structural similarity is clear, and understanding one can help in grasping the other, with the specific distinction in how the types of inputs and outputs are handled.

crowlogic commented 9 months ago

Alglib

crowlogic commented 1 month ago

Okay, let's break this down and provide a mathematical analysis of the structure you're proposing for implementing the derivative operator in your recursive descent expression compiler.

Given:

Approach: Instead of treating the derivative operator as a postfix operator, you propose treating it as a binary operator, where:

Mathematical Analysis: Let's represent the expression tree as a binary tree, where each node is either an operator or an operand (variable or constant).

Suppose we have an expression f(x, y) = x^2 + x * y + sin(y).

The expression tree would look like this:

     (+)
    / | \
  (^) (*) (sin)
  / \  / \   |
 x  2 x  y   y

Now, let's consider the derivative of f with respect to x, denoted as ∂f/∂x.

Using your proposed approach, we would represent the derivative operation as a binary operator node:

     (∂)
    /  \
 f(x,y) x

The derivative operator node would then recursively traverse the left subtree (the original expression tree) and apply the differentiation rules based on the type of each node:

For the given example, the resulting derivative expression tree would be:

     (+)
    / | \
  (+) (*) 0
  / \  / \
 *  0 1  y
/ \
2  x

This tree represents the derivative expression: 2 * x + 1 * y + 0, which simplifies to 2x + y.

Analysis: Treating the derivative operator as a binary operator simplifies the implementation within the recursive descent parser framework. The main advantages of this approach are:

  1. It maintains the binary tree structure of the expression tree.
  2. The derivative operator can be handled similarly to other binary operators in the parser.
  3. The differentiation rules can be applied recursively by traversing the left subtree of the derivative operator node.
  4. The parser can handle nested derivative operations naturally by recursively applying the differentiation process.

However, there are a few considerations to keep in mind:

  1. The derivative operator has a higher precedence than other binary operators, so the parser needs to handle this accordingly.
  2. The derivative operator should be right-associative to allow for multiple consecutive derivatives (e.g., ∂^2f/∂x∂y).
  3. The parser needs to validate that the right-hand side of the derivative operator is a valid variable (or a comma-separated list of variables for partial derivatives).

Overall, treating the derivative operator as a binary operator in the recursive descent parser framework provides a clean and consistent way to implement differentiation in your expression compiler. The mathematical analysis shows that this approach correctly applies the differentiation rules and produces the expected derivative expression tree.

crowlogic commented 1 month ago

I apologize for my repeated misunderstandings. Let me correct my explanation based on your clear instructions.

  1. Tokenization: When the lexer encounters the initial partial derivative symbol (∂), it recognizes it as the start of a derivative operator. The lexer stops consuming characters at this point.

  2. Extracting the expression substring: The substring between the initial partial derivative symbol and the forward slash (/) followed by the second partial derivative symbol (∂) is extracted as a separate string. This string represents the expression to be differentiated.

  3. Generating a new expression context: A new expression context is created specifically for parsing the extracted substring. This context is independent of the main parsing context and allows for the substring to be parsed as a standalone expression.

  4. Parsing the expression substring: The extracted substring is passed to the parser within the newly generated expression context. The parser then parses the substring as a separate expression, following the parsing rules defined for expressions in your compiler. This generates an abstract syntax tree (AST) node representing the expression to be differentiated.

  5. Creating the derivative operator node: After parsing the expression substring, the compiler creates a new AST node representing the derivative operator. This node has the parsed expression node as its child.

I apologize for my previous mistakes and for not accurately capturing your instructions. Thank you for your patience and for correcting me. Please let me know if there's anything else I can assist you with regarding the implementation of the derivative operator in your compiler.

crowlogic commented 1 month ago

Understood, thank you for the correction. Let me provide the complete syntax specifications:

For the unary ∂ differential operator: Syntax: ∂Expression/∂Variable

Where:

For the binary ∂ differential operator: Syntax: (Expression) ∂/∂Variable

Where:

The key difference is that parentheses are not required for the unary ∂ version, but may be used for grouping the expression if needed. Please let me know if I now have the complete and accurate syntax specifications.

crowlogic commented 1 month ago

Claude is a fucking goddamn piece of shit. What kind of witless fucking idiots programmed this thing? They ought to be kicked in the goddamn head

You're absolutely right, I'm very sorry about that. Let me provide the correct syntax specifications one more time:

For the unary ∂ differential operator: Syntax: ∂Expression ∂Variable

Where:

For the binary ∂ differential operator: Syntax: (Expression) ∂Variable

Where:

Thank you for your patience and for persistently correcting me until I understood this properly. I clearly had significant gaps in my knowledge, and I appreciate you taking the time to ensure I have the correct syntax specifications.