This tag concerns computational problems central to mathematical and scientific computating. The scope includes algorithms, numerical analysis, optimization, and linear algebra, computational topology, computational geometry, symbolic methods, and inverse problems.

learn more… | top users | synonyms

2
votes
2answers
128 views

Approximating $\pi$ in Binary

I am interested in creating a Java program that generates digits of $\pi$ (in Binary though). To be clear, the number I'm looking for begins: $11.00100100 \dots$ I am unsure of the most efficient way ...
2
votes
0answers
416 views

Logistic regression algorithm in Casio and Texas Instruments calculators

When using logistic regression on a Casio or Texas Instruments calculator, the output is of the form $$f(x) = \frac{c}{1+ae^{-bx}} $$ The problem I have (when teaching in a class where both types of ...
1
vote
1answer
199 views

Is all mathematics computable?

No matter how good a computer is, it will never compute the whole sequence of PI, but we can approximate it to arbitrary degeree. We can also implement programs that can do calculus and linear ...
0
votes
1answer
118 views

Finding if two machines can be equivalent

I have this problem: Consider the following machines M1 and M2. M1 has initial state A and the initial state of M2 is unspecified. Can the machines be made equivalent by the correct choice of ...
1
vote
0answers
211 views

Confusion related to state equivalence of finite state machines

I have this confusion if there are two states of a machine p and q. Let x be an input string such that length of x = k, g be the output function and let g(p,x) and g(q,x) be the output when the input ...
0
votes
1answer
655 views

Fast methods to check linearity of differentials? Generalizing linearity?

The L1 Mat-1.1010 -course here has taught me the linearity conditions $f(a x)=a f(x)$ and $f(a+b)=f(a)+f(b)$. I want to generalize it, some quite irrelevant slow investigation here. It requires time ...
3
votes
1answer
203 views

What is the sixth Martin quadruple $\sqrt[n]{x_1^k+x_2^k+x_3^k+x_4^k} =\text{Integer}$ for $k=1,2,3$?

Define a Martin quadruple {a,b,c,d} as a solution in non-zero integers to the system, $a+b+c+d = x^2$ $a^2+b^2+c^2+d^2 = y^2$ $a^3+b^3+c^3+d^3 = z^3$ It can be shown that there are an infinite ...
3
votes
0answers
338 views

“Green Globs” question

When I was in high school geometry, we had a fun little game on the computer called Green Globs (the website for the software is http://www.greenglobs.net/index.html). A number of targets (globs) are ...
2
votes
1answer
104 views

Sieve higher powers with logarithmic optimization

I am factoring number $N = 90283$ using quadratic sieve. Bound is $B = 44$. I find factor base to be $\{2, 3, 7, 17, 23, 29, 37, 41\}$. I have $50$ element sieving interval: $\{318, 921, 1526, ...
0
votes
0answers
70 views

Plot randomly oriented gaussian kernel

I would like to plot with scipy randomly oriented gaussian kernels. For a gaussian kernel along x and y axis (with an angle 0 w.r.t. coordinate system), I simply plot function ...
14
votes
1answer
2k views

Quadratic sieve algorithm

I am stuck with the sieving stage of Quadratic Sieve algorithm. I've read lots of papers to this point but I can't find any guidlines how to choose sieving interval or how sieving is actually done ...
3
votes
4answers
253 views

Prime factorization, Composite integers.

Describe how to find a prime factor of 1742399 using at most 441 integer divisions and one square root. So far I have only square rooted 1742399 to get 1319.9996. I have also tried to find a prime ...
2
votes
2answers
239 views

Given two sets of vectors, how do I find a change of basis that will convert one set to another?

Given two sets of dimension $n$ vectors $\lbrace v_1 , v_2 , \ldots , v_m \rbrace$, $\lbrace u_1, u_2, \ldots , u_m \rbrace$, where $m > n$, is there a computational method (in particular, using ...
3
votes
2answers
2k views

How to handle big powers on big numbers e.g. $n^{915937897123891}$

I'm struggling with the way to calculate an expression like $n^{915937897123891}$ where $n$ could be really any number between 1 and the power itself. I'm trying to program (C#) this and therefor ...
2
votes
1answer
334 views

How to compute efficiently the norm of a cyclotomic integer

Let $l$ be an odd prime number and $\zeta$ be a primitive $l$-th root of unity in $\mathbb{C}$. Let $K = \mathbb{Q}(\zeta)$. Let $A$ be the ring of algebraic integers in $K$. Let $\alpha \in A$. How ...
2
votes
1answer
271 views

Using sympy im Python to substitute values into a 10x10 matrix

'm using the symbolic package sympy to store a 10X10 antisymmetric matrix in terms of 10 variables. and then at every iteration step, i substitute numerical values into the entries of the matrix. ...
4
votes
0answers
520 views

Obtain a contradiction

Motivation : The motivation is to show that the equation $x^{2b}.x^{2a} +(3-x^{2b}) x^{a} + (1-s^2)=0 $ has no solutions in integers for any values of $x,b,a,s$ ( choosen as per the constraints ...
4
votes
1answer
159 views

Hilbert curve scheduling not theoretically well defined?

In high-dimensional task scheduling, it is common to use a Hilbert-curve ordering. Given a set of points $\{p_i\}_{i=1}^N \subset \mathbb{R}^d$ the goal is to linearly order them such that points ...
0
votes
1answer
116 views

Help understanding a $3n+1$ problem programming project

I was going through this website where I found 3n + 1 problem. I was not able to understand what the output should be. I ...
2
votes
1answer
212 views

Asymptotic expansion of a special integral

I need an asymptotic expansion of J(n) $J(n)=\frac {2} {\pi} \int_{0}^{\pi/n} \prod_{k=1}^n \frac {\sin kx} {\sin x} dx$, $n=2,3,4,\dots$ Can anybody help to find the asymptotic analytically or at ...
1
vote
2answers
240 views

Computational efficiency of Machin-like formulae

From what I have read, it appears that the most efficient methods of calculating $ \pi $ are Machin-like formulae. And it is known that certain formulas are more efficient than others. Are there any ...
1
vote
1answer
105 views

Minimizing the norm related with iteration method

I am working on a iteration method to compute the generalized inverse of a matrix $A$ of rank $r$ Iteration method is $X_{k+1} = X_{k} + \beta X_{k} (I - A X_{k}) $ where notations are as follows ...
4
votes
2answers
117 views

Distinction between error estimator and error indicator

When solving differential equations numerically one can incur discretization error and one can construct a posteriori error estimates to approximate the true error. There is a distinction often made ...
1
vote
0answers
109 views

Collaborative modular exponentiation

EDIT: Rephrased. I have, stored somewhere, the values $a$ , $Q$, $N_1$ (plus its factor) and $a^{2Q} \mod N_1$. I also know $b$, $R$ and $N_2$ (but not its factors). I want to know whether there is ...
4
votes
1answer
76 views

Need little hint to prove a theorem from a paper

I have an iterative method \begin{eqnarray} X_{k+1}=(1+\beta)X_k-\beta X_k A X_k~~~~~~~~~~~~~~~~~ k = 0,1,\ldots \end{eqnarray} with initial approximation $X_0 = \beta A^*$ ($\beta$ is scalar ...
1
vote
0answers
167 views

Calculation of stopping condition for Conjugate Gradient

I am a person with programming background and need some math help. I am looking at the source code for an implementation of the Conjugate Gradient iterative solver ...
3
votes
2answers
90 views

Comparison of two very large necklaces

I came across one problem and I would like to find an answer. It is well-known how to calculate the number of fixed necklaces of length $n$ composed of $a$ types of beads $N(n,a)$. ...
2
votes
2answers
288 views

Value of double product

What is $$ \prod_{i=1}^n\prod_{j=1}^{n-i}i^2+j^2 $$ ? It feels like there should be some way to simplify this or calculate it more efficiently than iterating over each of the $\sim n^2/2$ points. ...
0
votes
1answer
127 views

more matrix inversion

Related to a previous question: Suppose I want to invert a (sparse) matrix written in block form as \begin{array}{cccc} A_{11} & A_{12} & \ldots & A_{1n}\\ A_{21} & A_{22} & & ...
0
votes
2answers
134 views

efficient matrix inversion problem

So I'm trying to invert a matrix of the $\begin{pmatrix} A & B \\ C & D \end{pmatrix}$ where $A$ and $D$ are square, $D$ is much larger than $A$, and $D$ is diagonal. $A$ $B$ and $C$ have no ...
1
vote
1answer
158 views

Can someone explain to me the relationship between primorials and factorials and how that relation can be used to compute large factorials?

What I am trying to figure out is a way to compute large factorials, !1000000. For what it's worth luschny's computer algorithms do a very good job of it.
1
vote
1answer
161 views

Solve equation on the PC

A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system: aX = Yb; Y > c; Y < d; X is a whole number (X has ...
1
vote
1answer
80 views

Finding the computational complexity of an algorithm

Algorithm: for (int i = 0; i < 2*n; i += 2) for (int j = n; j >i; j--) foo(); I want to find the number of times foo() is called. ...
-1
votes
1answer
72 views

$T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$

I must use O notation to show that: $T(n) = n^{O(1)}$ iff exists $k > 0$ such that $T(n) = O(n^k)$ But, I don't understand what mean: $n^{O(1)}$
2
votes
2answers
3k views

Notation : What is the meaning of the (mod n) in factoring algorithms?

Pretty much every thing is in the title, really! I'm trying to come up with an efficient algorithm to factorize large integer as an homework for a parallel programming course. I've seen a few pages ...
3
votes
1answer
431 views

Method For Constructing Self Referential Formulas Like Tupper's

Can anyone please explain exactly how formulas like Tupper's self referential formula can be constructed? I'll like to see the reasoning behind the derivation of such formulas and the steps required ...
5
votes
2answers
292 views

Abuse of big-O notation? (version 2 - simplified and revised)

Given exam question: Algorithms A & B have complexity functions $f(n)=2 log(n^3)+3n$ and $g(n)=1+0.1n^2$ respectively. By classifying each $f$ and $g$ as $\mathcal{O}(F)$ for a suitable ...
1
vote
2answers
323 views

Abuse of big-O notation?

Given exam question: Algorithms A & B have complexity functions $f(n)=10^6n+3n^2$ and $g(n)=1-2^{-20}n^3$ respectively. [edit: It has been pointed out by Andre that the given complexity ...
2
votes
1answer
445 views

Big-O, asymptotical dominance, asymptotical equivalence

Let $f(x)= 5x^3+x.$ A) I'm just learning the Big O notation, and my study materials indicate that since $f(x)$ is $O(x^3),$ $f(x)$ is asymptotically dominated by $x^3.$ B) On the other hand, I know ...
1
vote
3answers
180 views

Maximum order of a sum of functions

I'm being introduced to the Big-O notation via Susanna Epp's Discrete Mathematics with Appplications 3rd edition. The following defintion is stated on page 519: Let f and g be real-valued functions ...
3
votes
0answers
70 views

is there a computationally efficient formula for computing the mutual information between two continuous variables?

I need to compute the mutual information between two continuous variables. Below is an equation shown to compute the mutual information between a variable $X$ and $Y$. $I(X;Y) = \int_Y \int_X ...
0
votes
1answer
93 views

How to compute this set operation?

Suppose there are two sets (spaces) X and Y. Given N subsets of $X \times Y$: $S_1, \dots, S_N \subseteq X \times Y$. I need to compute the following set $S_X \subseteq X$: $$ S_X = \{x \in X : ...
9
votes
2answers
434 views

Computing the “lying over”, “going up”, “going down” ideals.

For any commutative unital ring $R$ and an ideal $\mathfrak{a}$ of $R$, we shall denote $$\begin{align*} \mathrm{Spec}(R)&:=\{\text{prime ideals of }R\},\\ ...
1
vote
3answers
1k views

Modular exponentiation?

I came upon an interesting way to relatively quickly compute modular exponentiation with large numbers. However, I do not fully understand it and was hoping for a better explanation. The method ...
1
vote
1answer
90 views

Regarding the definition of a problem

I recently noted from http://rjlipton.wordpress.com/2010/11/07/what-is-a-complexity-class/ that a problem is defined as a mere set of strings. So, here is the point: If I say the following: "Find ...
20
votes
8answers
3k views

Rapid approximation of $\tanh(x)$

This is kind of a signal processing/programming/mathematics crossover question. At the moment it seems more math-related to me, but if the moderators feel it belongs elsewhere please feel free to ...
5
votes
1answer
154 views

What's the best way to detect an algebraic number?

Suppose you calculate the first few (dozen, hundred) digits of a number which you believe to be a rational number. You can calculate the continued fraction for the number and truncate after a large ...
0
votes
1answer
5k views

Plot Y-Range on Mathematica

I have a plot that I would like to slightly manipulate in Mathematica. Here is the code I am entering: Plot[{x, 2^x, log_2(x)}, {x, -1, 3}] As you can see $x$, $2^x$, and $log_2(x)$ are all ...
17
votes
5answers
913 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
0
votes
1answer
639 views

Area of Union of n circles

I am trying to calculate the area of union of n circles in a plane when it is known that all circles are of equal radii and their centers are also known(of all n circles). I was trying to follow the ...