# Questions tagged [mathematical-programming]

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

113 questions
Filter by
Sorted by
Tagged with
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!
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 ...
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, ...
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 ...
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 ...
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 ...
1answer
970 views

### Euclidean Algorithm in Coq

Question How do I write more intuitive proofs of the two following results in Coq? ...
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
1answer
32 views