Questions tagged [mathematical-programming]
Using a computer to implement mathematics. For questions about (mathematical) optimization, (also) use the optimization tag.
1
vote
0answers
51 views
Sum of long geometric progression [on hold]
Finding sum of a geometric progression is simple when we just need to report the sum,
but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me.
I have a ...
0
votes
0answers
16 views
How to generate evenly distributed random numbers from the tics of a Geiger Counter?
How can I generate random numbers from the tics of a Geiger Counter?
Say I have a file with the timestamps for every event.
0
325
456
920
....
The time spans ...
1
vote
0answers
28 views
How much of the x86 instruction set does blender use? [closed]
I'm trying to better understand benchmarks that are commonly used for computer hardware. I've been unable to find an answer to this question. Extra credit if you can provide a breakdown in ...
0
votes
0answers
23 views
Algorithm for placing objects inside a square from outside to inside
I have a map that is 300x300 units. I have to place squares of 20x20 units inside that map from outside to inside. There are 3 different types of square, the space available inside the map needs to be ...
0
votes
1answer
48 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
63 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
96 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
55 views
0
votes
0answers
42 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
34 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
20 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
25 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
40 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
116 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
101 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
52 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
17 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
58 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
21 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
156 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
424 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
36 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
101 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
99 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
80 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
84 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
203 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
243 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
49 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
86 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
295 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
54 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
54 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
111 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
56 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
322 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
442 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
724 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
262 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
192 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
113 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
512 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
115 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
46 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
549 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 ...
