Questions tagged [mathematical-programming]

Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.

Filter by
Sorted by
Tagged with
21
votes
2answers
12k views

What is the fastest algorithm for multiplication of two n-digit numbers?

I want to know which algorithm is fastest for multiplication of two n-digit numbers? Space complexity can be relaxed here!
11
votes
4answers
4k views

Are there any compression algorithms based on PI?

What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence). I've seen recently some prototype of πfs which assume that every file ...
10
votes
2answers
2k views

Theorem Proofs in Coq

Background I am learning assistance, Coq, on my own. So far, I have completed reading Yves Bertot's Coq in a Hurry. Now, my goal is to prove some basic results concerning the natural numbers, ...
8
votes
2answers
1k views

Known facets of the Travelling Salesman Problem polytope

For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of ...
6
votes
2answers
155 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
5
votes
1answer
509 views

How did the Logic Theorist prove the Pons Asinorum?

I was reading about the Logic Theorist proving many of the Whitehead and Russell's Principia's theorems. However, I cannot find any technical explanation on how the program proved those theorems and ...
5
votes
1answer
970 views

Euclidean Algorithm in Coq

Question How do I write more intuitive proofs of the two following results in Coq? ...
5
votes
1answer
1k views

n! mod p Fast Factorial

I need to find N! (mod 232-5) such that 0 ≤ N ≤ 264 for i cases, 0 ≤ i ≤ 1000 in 1 sec. Credits: https://dmoj.ca/problem/factorial2 I am aware that I only have to handle 0 ≤ N ≤ 2 ≤ 232-6 because ...
5
votes
0answers
156 views

Why did the Mathematica Language choose term rewriting instead of the Lambda Calculus as its basis? [closed]

Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda ...
4
votes
2answers
199 views

Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing ...
4
votes
2answers
260 views

Is the $x$ in $\frac{\mathrm{d}}{\mathrm{d}x}$ a symbol in the sense of Harper's PFPL?

The role of $x$ in $\frac{\mathrm{d}}{\mathrm{d}x} y$ not only confuses my calculus students, it has also puzzled some well known mathematicians. Questions one might ask are: Does the $x$ in the ...
4
votes
1answer
689 views

How to find a subset of numbers such that its average is close to the average of the full set?

I have a set of n numbers whose average (arithmetic mean) is x. I have to choose a subset of k numbers from n such that its average is closest to x. Please note that k is the upper bound. If the ...
4
votes
1answer
679 views

Fastest nth root algorithm to a lot of digits?

What is that fastest algorithm that can calculate a lot of digits of a decimal root? For example: 10,000 digits of the 3.56th root of 60.1?
4
votes
0answers
108 views

Count number of pairs $(a,b)$ in an array such that $(a + b)$ divides $(a * b)$

We are given an array of size $N$ with integer entries $> 0$. We have to count the number of all such pairs $(a,b)$ with $a \leq b$ such that $a*b$ is divisible by $a + b$. The obvious naive way ...
3
votes
2answers
1k views

How does a computer interpret real numbers?

I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to rational numbers. But I want to know how does ...
3
votes
3answers
171 views

Is it possible to make a language that can build upon itself perfectly?

First of all, note that I'll have to explain my thoughts in a layman's terms. There are so many high-level programming languages out there that compete with each other. This means we have to build ...
3
votes
3answers
122 views

Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
3
votes
2answers
67 views
+50

Fermat's last theorem: How to (partially) solve by programs

No three distinct positive integers $a, b, c$ can satisfy the equation : $a^n + b^n=c^n$, if $n$ is an integer greater than two. The above statement, known as the Fermat's last theorem is proven ...
3
votes
2answers
681 views

How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?

I am trying to solve this recurrence relation for a while but not getting anywhere. Actually, the sequence is given as, F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2) where, F(0) and F(1) will be given. I ...
3
votes
2answers
379 views

Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?

On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the software application of that concept. I'd like ...
3
votes
1answer
105 views

Can this equation be solved in polynomial time?

I came across a more general form of this question. Can we find the value of variables in polynomial time ? Let $m = n^{2}$, there are $m$ variables ($x,y,z\ldots$) in the equation and these $m$ ...
3
votes
1answer
60 views

Good resources for understanding semidefinite relaxation for combinatorial problems

I am looking for good, complete and understandable resources in the field of semidefinite programming and combinatorial optimization. Especially I have a combinatorial problem which I want to relax as ...
3
votes
0answers
166 views

Enumeration of corner points of a polytope [closed]

Given a linear program, is there any library or available code to enumerate all the corner points of a polytope ?. PS: Simplex method finds one corner point depending on the objective, but I need to ...
3
votes
0answers
91 views

Representing Computations on Transcendental Numbers

Consider the set of transcendental numbers that are not compressible to a finite base-2 representation. How can I compute multiples (more generally, any algebraic computation) of one of these numbers,...
3
votes
0answers
166 views

Drawing Zonotopes from an Adjacency Matrix

I'm conflicted whether to post this here or in either math.stackexchange or mathematica.stackexchange. Define a "simple zonotope" to be a regular $2n$-gon which is tiled by the following rule: all ...
2
votes
1answer
55 views

Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$

Given array $A$ of size $n$, we want to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$. Is there way to speed this up rather than the standard $O(n^3) $ calculation with 3 for loops. I ...
2
votes
3answers
160 views

Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$

Let $f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n$, where $a_i\ge0$ and $a_i$ is integer. Given $f(1)=p$ and $f(f(1))=q$, we have to find $a_0$, $a_1$, $a_2$, $a_3$, $\dots$, $a_n$, where such $f(x)$ exists. Or ...
2
votes
1answer
648 views

Why does radix sort work?

I understand how radix sort works and how to implement it, but I don't understand why it works. Are there any underlying mathematical or logical principles that it relies on?
2
votes
1answer
144 views

Approximate a float using a minimal fraction

This sounds like it's probably a well-known problem, but I haven't been able to find references to it by searching. Given a floating point value $x$ and an error range $\varepsilon$, how can I ...
2
votes
1answer
1k views

Calculating Binet's formula for Fibonacci numbers with arbitrary precision

Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite ...
2
votes
1answer
2k views

Matrix Multiplication Algorithms for Non-Square Matrices

I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such ...
2
votes
1answer
41 views

Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

Having large matrices, $W$ (the unknown) and $M$ (known), is it possible to solve for $W$ in this equation $$W \cdot W^{T} = M,$$ where $M$ can have negative entries.
2
votes
2answers
213 views

Implications of Integral linear program

Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$ Let $(P^*)$ be ...
2
votes
1answer
41 views

Algorithm to convert rendered number back into symbolic form

If you have a number such as $3.14626437$ and you need to know what symbols create it, as far as I know, there are two tools: 1- ISC 2- wolframalpha and the answer is $\sqrt2+\sqrt3$ I am ...
2
votes
1answer
83 views

Finding number of numbers dividing n^m exactly p times

Suppose I am given a number $n$ (less than $10^8$) and $m$ (less than $10^7$) and $p$ (less than $10^4$), I have to write a program to find number of numbers that divide $n^m$ exactly $p$ times. ...
2
votes
1answer
314 views

Permuting natural numbers

We have two integers $z, k$ We form a sequence now of first z natural numbers. i.e. $1, 2, 3, 4, \ldots z$. Now we have to find total number of permutations of this sequence such that the sum of ...
2
votes
1answer
40 views

Estimation of the number of solutions by Counting

This is a question from a quantum computation textbook. Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times ...
2
votes
1answer
30 views

Interpolate on a cylic x axes

Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y ...
2
votes
1answer
104 views

Mathematically calculating time complexity

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject. Also I ...
2
votes
1answer
50 views

Implementing Gauss–Legendre algorithm using arbitrary-length rationals

I am trying to re-implement SuperPI myself in Rust, but the results I get are not very accurate. SuperPI computes pi using the Gauss-Legendre algorithm. The Gauss–Legendre algorithm is quite simple, ...
2
votes
1answer
149 views

How to find the most unique vectors in a set?

A question bridging math and computer science, I have on the order of 10000 vectors each of a equal but high dimension, say 6 or 7 dimensions. I want to find a given number of 'unique' vectors in the ...
2
votes
1answer
32 views

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming? Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is $y=...
2
votes
0answers
53 views

Maximizing the product of a set of dot products

So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following: $\prod_{x \in X} b \cdot x$ where the components of $b$ sum to $1$ If it matters the components of ...
2
votes
0answers
130 views

Can cognitive architectures (CLARION, SOAR, ACT-R) be used for creative mathematical reasoning?

Can cognitive architectures (CLARION, SOAR, ACT-R, others) be used for creative mathematical reasoning? As far as I understand, then it is the best to encode formal mathematical knowledge in the ...
1
vote
2answers
1k views

Is global non-convex optimization NP-complete?

Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision ...
1
vote
1answer
42 views

Min-plus matrix multiplication implementation

I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication: One method for doing this is to ...
1
vote
1answer
37 views

How do you implement a language with greater capabilities using subordinate languages?

I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects? I've read in the book "Math You Can`t Use - ...
1
vote
2answers
526 views

Algorithm for packing various shapes inside of a rectangle

Say I am given a rectangle of width $W$ and length $L$. I now have to fit as many regular shapes of area $A$ into this rectangle as possible. For example, if the shape is a circle, I need to fit as ...
1
vote
1answer
116 views

What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?

I'm talking about functions such as Python's math.frexp() : math.frexp(x) Return the mantissa and exponent of x as the pair (m, e). m is a float and e is an integer such that x == m * 2**e ...
1
vote
2answers
109 views

Find lines segment portions close together

I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A_1$, $B_1$ and $A_2$, $B_2$ (see left part in the below schema). I would a like to find an algorithm to detect ...