Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
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 ...