Questions tagged [computer-algebra]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Matt Samuel's user avatar
1 vote
1 answer
54 views

Binary subsets for a given set

Lets take an example of the range of N=32 bits ...
Dave's user avatar
  • 11
0 votes
0 answers
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 ...
Ahsan Ali's user avatar
1 vote
1 answer
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$. ...
Lluís Alemany-Puig's user avatar
2 votes
0 answers
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 ...
Logan R. Kearsley's user avatar
-2 votes
2 answers
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 ...
Miss Mulan's user avatar
1 vote
0 answers
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 ...
Foxy's user avatar
  • 255
-1 votes
2 answers
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 ...
James William Jacobs's user avatar
2 votes
0 answers
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 ...
Fizz's user avatar
  • 1,240
1 vote
1 answer
70 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+...
Hardware  Gaming's user avatar
2 votes
1 answer
167 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 ...
user37344's user avatar
  • 125
1 vote
0 answers
67 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^...
D.W.'s user avatar
  • 154k
15 votes
7 answers
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 ...
Robert's user avatar
  • 185
1 vote
1 answer
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 ...
prash's user avatar
  • 111
4 votes
0 answers
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 ...
Bruno Kim's user avatar
  • 141
1 vote
0 answers
32 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 $...
Joannes Vermorel's user avatar
0 votes
0 answers
158 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 ...
R Mcgowan's user avatar
-2 votes
1 answer
64 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. ...
Ahsan Shabbir's user avatar
3 votes
3 answers
2k 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 ...
Team B.I's user avatar
2 votes
3 answers
445 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?
Brandon Casas's user avatar
3 votes
2 answers
60 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 ...
Crassus's user avatar
  • 31
2 votes
1 answer
304 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}. ...
Mark's user avatar
  • 21
2 votes
1 answer
63 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....
Major Despard's user avatar
2 votes
2 answers
29 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}...
Dimitri Koshelev's user avatar
2 votes
0 answers
56 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}...
Dimitri Koshelev's user avatar
0 votes
1 answer
437 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 ...
user99140's user avatar
2 votes
0 answers
245 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 ...
glS's user avatar
  • 286
2 votes
0 answers
34 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 $...
MrX's user avatar
  • 41
3 votes
1 answer
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$...
sssa's user avatar
  • 424
2 votes
0 answers
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. ...
RoyPJ's user avatar
  • 156
6 votes
1 answer
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: ...
zero_coding's user avatar
1 vote
0 answers
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 ...
hawkeye's user avatar
  • 1,199
4 votes
2 answers
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 ...
ShadowViper's user avatar
5 votes
1 answer
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 ...
srd091's user avatar
  • 61
5 votes
2 answers
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, ...
Elliot Gorokhovsky's user avatar
0 votes
1 answer
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 ...
kristianp's user avatar
  • 101
11 votes
2 answers
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, ...
templatetypedef's user avatar
1 vote
1 answer
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 ...
rioforman's user avatar
2 votes
0 answers
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). ...
Lucas's user avatar
  • 201
3 votes
1 answer
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 ...
Nathaniel M. Beaver's user avatar
5 votes
1 answer
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, ...
zpavlinovic's user avatar
  • 1,644
1 vote
1 answer
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 ...
tony9099's user avatar
  • 151
2 votes
1 answer
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 ...
Shahed al mamun's user avatar
3 votes
4 answers
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? ...
Rai Ammad Khan's user avatar
1 vote
1 answer
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?
Quora Feans's user avatar
4 votes
1 answer
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?
张 源's user avatar
  • 159
1 vote
1 answer
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 ...
HaloKiller's user avatar
4 votes
1 answer
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? ...
user avatar
11 votes
0 answers
2k 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 ...
user avatar
2 votes
2 answers
158 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 ...
Erb's user avatar
  • 373