# Questions tagged [computer-algebra]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
0answers
24 views

0answers
50 views

2answers
7k views

### Complexity of computing matrix powers

I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily ...
1answer
71 views

### How to compute quotient subgroup efficiently?

Let $G$ be a finite group given by the table representation and a normal subgroup $H$ of $G$ is given. I want to compute $G/H$ that is quotient group. Model of computation is RAM For all pair of $a$...
0answers
52 views

### Provably correct algorithm/CAS for checking term equalities

Within my research of term rewriting systems (TRS) I stumbled upon a paper (Siekmann, J., and P. SzabĆ³. āThe Undecidability of the DA-Unification Problem.ā The Journal of Symbolic Logic, vol. 54, no. ...
1answer
2k views

### cannot construct the infinite type [closed]

I am trying to learn haskell and could not configure it out, why following code snippet can not get compiled: ...
0answers
18 views

### Is there evidence to suggest Macsyma was directed at the Diophantine equations in the Entscheidungsproblem?

I'm reading the book The Annotated Turing by Charles Petzold. In it he mentions the Diophantine equations - which was a joy to read. This then lead to Hilbert's 10th problem - finding an algorithm ...
4answers
4k views

### Why do Computers use Hex Number System at assembly language?

Why do computer use Hex Number System at assembly language? Why don't they use any other number system like binary, octal, decimal? What thing forced computer designer to use hex system at assembly? ...
1answer
589 views

### How to calculate sum of binomial coefficients efficiently?

I want to compute the sum $$\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\binom{n}{6}+\dots+\binom{n}{k} \bmod 10^9+7$$ where $n$ and $k$ can be up to $10^{14}$ and $k\le n$. I found several links on ...
2answers
299 views

### Constant problem for discrete functions

Is there an algorithm to decide whether a closed-form expression over integer variables using, say, $\{+,-,\times,\div,\text{^},\lfloor\text{lg}\rfloor,!,()\}$, or some other useful set of operators, ...
1answer
53 views

### The symbolic differentiation of univariate expressions

I was reading "Doug McIlroy: McCarthy Presents Lisp" and the phrase "symbolic differentiation of univariate expressions" triggered a faint memory of a demonstration of differentiation done in haskell ...
2answers
174 views

### Decidability of checking an antiderivative?

Let's suppose I have two functions $F$ and $G$ and I'm interested in determining whether $$F(x) = \int G(x)dx.$$ Let's suppose that my functions are composed of elementary functions (polynomials, ...
1answer
785 views

### Difficult Question to Understand (Computer Artitechture) [closed]

You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no ...
0answers
26 views

### How to simplify a rational function with floating point real coefficients (GCF)

How does one compute the simplified form of a rational function where the coefficients of the polynomial are floating point numbers (real, though I expect using complex numbers would be the same). ...
1answer
331 views

### Abstract algebra and programming languages

Quite often, I stumble upon abstract algebra concepts like initial algebra, free algebra, and similar while reading papers on programming languages. For instance, in papers on algebraic data types, ...
1answer
127 views

### Introduction to number theory [closed]

What is the best book for a beginner in Introduction to number theory? I am new to this field and getting deeper into cryptography, so I think reading some intro books about number theory can be of ...
1answer
69 views

### Multiplication of two or more algebraic quantities [closed]

Recently, I was facing the problem how to multiply to two or more algebraic quantities in c++. For example, if the two algebraic quantities are $$x^2-2x+3, \text{and } x-5$$ then the result of ...
1answer
52 views

### Is everything in CS either a numeric method or a symbolic method?

Or maybe also a combination of the two, but not something else, whether numeric, nor symbolic. Do they cover the whole field?
1answer
54 views

### How does mathematical software evaluate symbolic sums?

Wolfram alpha is able to compute this sum: $$\sum_{j=1}^n \binom{j}{2} = \frac{1}{6}(n-1)n(n+1).$$ How can Wolfram alpha do it? What kind of algorithm does it use?
1answer
75 views

### An algorithm for making 2 carts meet [closed]

Say I have 2 carts on an infinite railroad, each cart is initially under a lamp. There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between ...
1answer
623 views

### How does automatic differentiation work?

What is the intuitive idea behind automatic differentiation? If I have a program which computes $f(x, y)=x^2+yx$, which steps lead to the program which computes the derivative $df/dx$ of f? ...
0answers
920 views

### Does Automatic Differentiation handle conditional branches, if yes how?

I'm trying to understand how Automatic Differentiation (AD) works. For simple algebraic operation, I get the chain rule thing. But, when the code contains conditional statement like ...
4answers
614 views

### Using a computer algebra system to optimize mathematical expressions

This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, ...
2answers
97 views

### Solve modulus with constraints for multiple equations

I'm trying write a program to solve equations from the following form: \begin{align} a \bmod x &= t_1 \\ b \bmod x &= t_2 \\ \end{align} where $a$, $b$, $t_1$ and $t_2$ are known ...
2answers
266 views

### Computer Algebra: Algorithms for solving equations symbolically

As a hobby, I have written a basic computer algebra system. My CAS handles expressions as trees. I have advanced it to the point where it can simplify expressions symbolically (i.e., sin(pi/2) returns ...
2answers
281 views

### Decidability of a problem concerning polynomials

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite ...
3answers
1k views

### Constructing a data structure for a computer algebra system

In thinking about how to approach this problem I think several things will be required, some tivial: An expression tree where non-leaf node is an operation (not sure if that part is redundant), but ...
0answers
228 views

### Complexity of computer algebra for systems of trigonometric equations

As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence: \$\qquad f_{p_0} = 0\\ \...