# Questions tagged [computer-algebra]

The tag has no usage guidance.

56 questions
Filter by
Sorted by
Tagged with
54 views

### Algorithm for determining an algebraic positivity property of a multivariate polynomial

I am considering multivariate polynomials with integer coefficients that can be expressed as sums of products of terms of the form $y_i-z_j$ for positive integers $i$ and $j$. I am trying to find an ...
1 vote
54 views

### Binary subsets for a given set

Lets take an example of the range of N=32 bits ...
31 views

### Encoding and Decoding

I am trying to find an encoding function e:{0,1}^20→{0,1}^10 and a decoding function d:{0,1}^10→{0,1}^20. Goal is to find d and e so that maxBdH(d(e(B)),B) is as small as possible. Here, dH denotes ...
1 vote
32 views

### Can equations be simplified with the help of a given set of equations?

There are many posts here and elsewhere asking for algorithms to simplify simple arithmetic expressions. For example, this question asks how to simplify the expression $axc + byc + ayc + bxc$. ...
52 views

### Algorithm for nth roots of unity in symbolic radical form?

Roots of unity are trivial to find numerically--just evaluate $sin$ and $cos$ to whatever precision you require. But suppose (because it's true) that I want exact algebraic representations for ...
81 views

### DNA sequence and algebra

DNA is made of a string of different proteins.There are 4 different proteins which make up the human DNA.We can represent each protein as a 2 bit sequence of '0' and '1'.However wouldnt it be much ...
1 vote
43 views

### What are the interesting data structures to work with to manipulate mathematical expressions?

For learning purposes only, I would like to make a small, fairly basic computer algebra system (CAS) manipulating mathematical expressions, such as polynomials, logarithmic or trigonometric ...
39 views

### Numerical "Biases" Computation Issue

I discovered this issue last night & can't make sense of it. Numerical biases programming sounds ridiculous but the code is the same, only changing the denominator from 4 to 5 and changing the ...
23 views

### What's an efficient algorithm to check if a binary operator is residuated?

Assume the binary operator is given as a table/matrix, so constant time to compute $xy$. And likewise, assume the (relation giving rise to the) partially ordered set is also given as a table, or in ...
1 vote
70 views

6k views

### How can a computer deal with real numbers

Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in ...
1 vote
136 views

### Non-trivial difference(s) between Computer Algebra System and Proof Assistant

Disclaimer: I am not even an expert user of these two kinds of software. I understand that the trivial difference between proof assistants and CAS is that in proof assistants, the goal is to show that ...
62 views

### Efficient algorithm for factorizing symbolic sum of products

Given a sum of flat symbolic products like $axc + byc + ayc + bxc$, how can I efficiently factorize it as a product of sums like $(a+x)(b+y)c$? For my problem, the products are not commutative -- it's ...
1 vote
32 views

56 views

128 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$...
55 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. ...
3k 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: ...
1 vote
22 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 ...
619 views

### Using Brzozowski's derivatives method to construct a minimal DFA

so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language ...
676 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 ...
303 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, ...
65 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 ...
373 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, ...
1 vote
1k 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 ...
31 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). ...
335 views

### Properties of Reverse Polish Notation expressions that are algebraically invariant

The RPN expressions a b + c * and f d e + * are algebraically equivalent, though the names of the variables are different ...
409 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, ...
1 vote
154 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 ...
105 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 ...
7k 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? ...
1 vote
56 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?
64 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?
1 vote
77 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 ...
823 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? ...  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 ...