Questions tagged [mathematical-programming]
Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.
0
votes
1answer
44 views
Counting the number of multiples of number A that perfectly divides the number B
What is the best way of counting the number of multiples of number A that perfectly divides the number B.
This is the sub problem for one of the questions I am solving on codechef.
This is the best I ...
1
vote
1answer
49 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 ...
4
votes
0answers
92 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 ...
0
votes
1answer
52 views
0
votes
0answers
38 views
What is the time complexity of MATLAB's ode solvers?
Say I have a system that is $n$ differential equations that are all coupled together, over a time interval $[a,b]$ with timestep $t$. Is there a straightforward time complexity for MATLAB's built in ...
2
votes
1answer
32 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, ...
1
vote
1answer
19 views
What is the equation for a spiral path in 3D? [closed]
I am developing games in Unity 3D. Currently, I am trying to place 3D objects in 3D space in a spiral pattern that looks like one of 2 the strands in a pair of the DNA (helix) spiral pattern.
Would ...
0
votes
0answers
23 views
Classify manifolds with neural networks
Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
1answer
35 views
Balance groups based on average, element constraints and size
It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.
Let me explain ...
2
votes
1answer
97 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 ...
1
vote
1answer
67 views
Efficient streaming sort
Consider following task: we have an input of N+1 lines, where first line contains N - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id &...
2
votes
1answer
51 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 ...
1
vote
1answer
16 views
PCA with Bishop's book
I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?
Your help is ...
0
votes
1answer
56 views
Compute e^x given starting approximation
I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits). The best way I know is to use Taylor polynomials. However, the Taylor polynomial algorithm seems ...
1
vote
1answer
20 views
Sum of distances between points on one-dimensional axis
We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given ...
3
votes
3answers
154 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 ...
0
votes
2answers
298 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 ...
0
votes
1answer
30 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
1answer
91 views
Algorithm for weighted elliptic curve fit
Background:
I was trying to detect a face solely on the bases of features and the confidence of the features found.
I am using a method to identify the features along with the response (confidence). ...
0
votes
1answer
78 views
Is there a poly-time algorithm for expanding out polynomials
so I've been looking around and haven't seen this before. Basically I'm working with a problem in which I need to expand/FOIL out. Something in the form of
$$
z = (x+y)(x-y) \implies x^2+xy-xy+y^2
$$
...
1
vote
1answer
75 views
Is it possible to evaluate $n!$ in $O(1)$?
I'm working on a formula that'll evaluate the partial sum of the harmonic series from $t_1$ to $t_n$. The problem is that I'm almost certain the final formula will include factorials. But if the ...
1
vote
2answers
71 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
0answers
182 views
Understanding Sliding Window Algorithm
I am trying to implement sliding window algorithm for rainfall forecasting. The algorithm is follows:
This algorithm is from An enhancement of sliding window algorithm for
rainfall forecasting in ...
4
votes
2answers
239 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 ...
0
votes
0answers
46 views
Math behind path tracing
I seem to remember seeing somewhere (many years ago) a writeup of the math behind calculating the outline of Metafont glyphs. The basic idea is you have a "pen" that is a circle or oval, that you ...
1
vote
1answer
69 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 ...
0
votes
0answers
249 views
Derivatives involved in Bilinear interpolation
If we choose a unit square in which the four points where the function $f$ is known are as shown in the diagram the interpolation formula for $f$ is:
\begin{equation}
\begin{split}
f(x+u, y+v)\approx (...
1
vote
1answer
52 views
Algorithm which finds the maxmal solution that satisfies the following constraints
I have $a_1, a_2,\dots,a_n$ and $b_1,b_2,\dots,b_n$ and an upper bound $U$ and $n$ linear equations of the form:
$k_1 * a_1 + b_1 = x$
$k_2 * a_2 + b_2 = x$
$\dots$
$k_n * a_n + b_n = x$
...
1
vote
0answers
39 views
How to model the constraint of a circle placement problem mathematically?
I have a circle with radius $R$ and $N$ points on a 2D plane with known locations $(x_i,y_i), i=1,2,..N$. I want to place the circle such that it maximizes the number of covered points.
Let $d_i=(x_i-...
0
votes
1answer
50 views
How can I calculate the new quotient if I came to know divisor is increased by one?
If I have two number consider a and b and let their division quotient is c.
I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is ...
2
votes
1answer
131 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
0answers
109 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
0answers
55 views
Column Generation - Worst dual bound when adding various columns per iteration
I'm implementing a Column Generation algorithm. The pricing problem, in general, find more than one column with negative reduced costs(the master is a min problem). If i add only the most negative ...
4
votes
1answer
271 views
How did the Logic Theorist proved the Pons Asinorum
I was reading about the Logic Theorist solving many of Whitehead and Russell's Principia's theorems. I cannot however find any technical explanation on how the program proved those theorems and ...
1
vote
1answer
413 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?
1
vote
0answers
44 views
Program that solves mechanics diagram problems
There is a program, BEATRIX, that can understand textbook physics problems specified by a combination of English text and a diagram. The result of the understanding process is a unified internal model ...
5
votes
1answer
676 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 ...
1
vote
1answer
255 views
Stroke Width Transform: Gradient Direction Computation
I've been trying to implement this paper from Boris Epshtein, Eyal Ofek, and Yonatan Wexler, the pioneers of Stroke Width Transform .
Having a simple image with random texts, that underwent gray ...
4
votes
2answers
189 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 ...
0
votes
1answer
103 views
Formulating a recursion using mathematical notation [closed]
So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, ...
3
votes
2answers
491 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 ...
-4
votes
1answer
52 views
How do i get the inputted number,but repeat the same integers twice? [closed]
Imagine i get an input 123 my goal is to return 112233.How can i get that?I can't use strings because i have to multiply that ...
3
votes
0answers
105 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 ...
1
vote
0answers
44 views
Fastest way to Add and Subtract multiple parts of a List
I am doing some research where I have a List containing numbers. For example
{5,10,98,22,13,15}
What is a fast algorithm to calculate all possible sums and ...
0
votes
1answer
68 views
Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?
I just found out by luck that
Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min()
For example,
Consider a sorted array, {1 43 65 97 ...
-2
votes
2answers
511 views
Count all numbers up to X that are divisible by at least two of their digits
I want to count how may numbers are there in range [1,X] which are divisible by at least two of their digits, different and >1. I found a sequence on OEIS, but this will take lot of time to generate ...
3
votes
0answers
131 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 ...
3
votes
1answer
49 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 ...
-1
votes
1answer
75 views
ordered uniform distribution
We are given $n$ objects with individual weights $w_1 , w_2 , \ldots , w_n$ and $m$ buckets in which these objects are to be inserted but in order. Here order means if object $i$ goes in bucket $m_i$ ...
2
votes
1answer
40 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 ...
