Questions tagged [computer-algebra]
The computer-algebra tag has no usage guidance.
49
questions
2
votes
0answers
22 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
1answer
55 views
solve a rational equation as fast as possible
I would like to find the first positive solution(if there is one) to this equation:
$$\frac{ax^2+bx+c}{dx^2+ex+f} = gx+h$$
The simplest way I fond would be to do the following:
$$ax^2+bx+c = (dx^2+ex+...
2
votes
1answer
119 views
Why aren't Grobner bases more common?
I have only heard of / seen Grobner bases in passing, but my understanding is that they are much like vector bases but for polynomials instead of linear systems. I know polynomials are used in CAD and ...
0
votes
0answers
20 views
Newbie 2s complement to binary circuits help
I'm creating a circuit with in3, in2, in1, and in0, and outputs F11-F0. The circuit has to take the input in 2s complement and output the number in binary with the sign. F11 represents the sign bit (...
1
vote
0answers
51 views
Express polynomial as sum of two lower-degree polynomials, modulo another
Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$. I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that
$$p(x) \equiv r_1(x) x^...
14
votes
7answers
5k 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
1answer
49 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 ...
4
votes
0answers
45 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
0answers
29 views
Numerically stable reverse automatic differentiation of power(x, y)?
I would like to compute the adjoints $\bar x$ and $\bar y$, from a reverse automatic differentiation perspective, of the expression $x^y$. The adjoint $\bar{x^y}$ is already known; and we can assume $...
0
votes
0answers
77 views
Floating point binary number to a 7 segment decimal display
I have covered floating point (32 bit) conversion from float to decimal and decimal to float. I am happy with the theory and I have created a conversion tool in Excel VBA which works just fine ...
-2
votes
1answer
51 views
What is the time complexity of the following triple nested loop? Kindly solve in term of n
I want to ask that what is the time complexity of this function (triple nested loop)
.Kindly analysis completely so that I can understand.
...
4
votes
3answers
663 views
Do we need to check for mantissa overflow in floating point multiplication?
We do check for the mantisas overflow in floating point addition
e.g.
If we are adding $8.02 \times 10^3 + 9.01 \times 10^3 =17.03 \times 10^3$ i.e we get an overflow, so we shift the number right ...
2
votes
3answers
262 views
Is the constant pi (not Raspberry) ever used in general computer science?
Is the constant pi (not Raspberry) ever used in general computer science? If so, how so or when is it applicable?
3
votes
2answers
55 views
Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0?
What is the standard way for VMs to deal with 0 *= computationallyHeavyFunction()? Given that once the VM sees that left hand factor is 0, it would know that the result of ...
2
votes
1answer
75 views
Basic Set Theory problem
So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it.
The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. ...
2
votes
1answer
36 views
When an algorithm says Summation this, and Integral that, what does it mean in coding terms?
I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me.
I'm currently reading GPU Gems by nvidia and I have a question....
2
votes
2answers
28 views
An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$
Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}...
2
votes
0answers
51 views
An efficient algorithm to find a linear transformation between two ternary quadratic forms
Let $\mathbb{F}_p$ be a prime finite field for $p > 2$. Consider two ternary quadratic forms
$$Q_1\!: x^2 - a_1(t)y^2 - b_1(t)z^2,\\
Q_2\!: x^2 - a_2(t)y^2 - b_2(t)z^2$$
over the field $\mathbb{F}...
0
votes
1answer
252 views
Simplifying SOP: implementing OR with NAND
I am learning how to implement basic logic gates using NAND. I have learnt that you can use De Morgan's theorem as such:
$a+b = \bar{\bar a} + \bar{\bar b} = \overline{(\bar a *\bar b)}$
In other ...
2
votes
0answers
140 views
What is the computational cost of automatic differentiation compared to symbolic and numerical differentiation?
Automatic differentiation is a set of techniques to numerically evaluate the derivative of a function.
Quoting from Wikipedia (emphasis mine):
These classical methods run into problems: symbolic ...
2
votes
0answers
31 views
Nearest codeword in a translation-invariant code over $\mathbb{Z}^d$
Let $c_1,...,c_n,c':\mathbb{Z^d}\rightarrow \{0,1\}$ all have finite support.
Let $C$ be the linear, shift-invariant code generated by $c_1,..,c_n$.
It is possible to calculate the nearest codeword $...
3
votes
1answer
94 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$...
1
vote
0answers
53 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. ...
6
votes
1answer
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
0answers
19 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 ...
4
votes
2answers
455 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 ...
5
votes
1answer
623 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 ...
5
votes
2answers
300 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, ...
0
votes
1answer
59 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 ...
10
votes
2answers
223 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
1answer
908 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 ...
2
votes
0answers
30 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).
...
3
votes
1answer
267 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 ...
5
votes
1answer
367 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
1answer
138 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 ...
2
votes
1answer
88 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 ...
3
votes
4answers
5k 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
1answer
54 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?
4
votes
1answer
58 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
1answer
76 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 ...
4
votes
1answer
709 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?
...
9
votes
0answers
1k 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
...
2
votes
2answers
135 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 ...
4
votes
4answers
660 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, ...
4
votes
2answers
288 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 ...
11
votes
3answers
337 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 ...
5
votes
3answers
2k 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 ...
8
votes
0answers
231 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\\
\...
14
votes
2answers
8k 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 ...
