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

36
votes
4answers
15k views

What algorithm is used by computers to calculate logarithms?

I would like to know how are logarithms calculated by computers. The GNU C library, for example, uses a call to the fyl2x() assembler instruction, which means that ...
4
votes
3answers
223 views

Fast way to get a position of combination (without repetitions)

This question has an inverse: (Fast way to) Get a combination given its position in (reverse-)lexicographic order What would be the most efficient way to ...
5
votes
5answers
549 views

A valid floor function trick?

Given $x\in\mathbb R_+$ and $m,n\in\mathbb Z_+$, is it true that $$\bigg\lfloor\frac{\lfloor \frac{x}{m}\rfloor}{n}\bigg\rfloor=\bigg\lfloor \frac{x}{mn}\bigg\rfloor?$$ Thanks for at least three ...
2
votes
2answers
146 views

(Fast way to) Get a combination given its position in (reverse-)lexicographic order

This question is the inverse of the Fast way to get a position of combination (without repetitions). Given all $\left(\!\!\binom{n}{k}\!\!\right)$ combinations without repetitions (in either ...
1
vote
2answers
113 views

How can I solve this problem without having to do it by hand?

I'm dealing with the following problem in computational programming. I'm trying to find a way to build an algorithm that can quickly resolve the following problem statement without forcing me to do it ...
20
votes
8answers
5k 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 ...
18
votes
4answers
410 views

How could I improve this approximation?

In a computer application, I need to solve trillions of times an equation which can be reduced to $$f(x)=\sin(x)-a x=0$$ Newton methods (quadratic and higher orders) are used for the solution. ...
7
votes
2answers
517 views

Accelerating Convergence of a Sequence

Suppose I had a monotonically increasing sequence $\{d_{n}\}$ which is also bounded above. The $d_{n}$'s satisfy a given recurrence, however computationally they tend very slowly to the limit. What ...
47
votes
4answers
4k views

Is “A New Kind of Science” a new kind of science?

A couple of years ago I was reading "New Kind of Science" (NKS) by S. Wolfram, and it presented lot of interesting ideas for a young Physics undergraduate. Now that I am studying Mathematics however, ...
17
votes
5answers
962 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 ...
8
votes
9answers
13k views

Fastest Square Root Algorithm

What is the fastest algorithm for finding the square root of a number? I created one that can find the square root of "987654321" to 16 decimal places in just 20 iterations (I'm not ready to release ...
11
votes
0answers
106 views

On the prime-generating polynomial $m^2+m+234505015943235329417$

In 2009, J. Waldvogel and Peter Leikauf found the remarkable Euler-like polynomial, $$F(m)=m^2+m+234505015943235329417$$ which is prime for $m=0\to20$, but composite for $m=21$. Define, ...
11
votes
2answers
269 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...
15
votes
1answer
3k 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 ...
9
votes
2answers
2k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...
2
votes
5answers
379 views

Proving $\pi^3 \gt 31$

$$\large \pi^3 \gt 31$$ Using a calculator, $\pi^3/31 \approx 1.0002$, so I thought this may be challenging to do by hand. It is extremely easy with the use of any calculator, so I was wondering ...
11
votes
1answer
415 views

Constructing a finite field

I'm looking for constructive ways to obtain finite fields, for any given size $q=p^n$. For example, I know it suffices to find an irreducible polynomial of degree $n$ over $\mathbb{Z}_p$ (and then ...
1
vote
0answers
70 views

What are the next few “tetranacci-like” pseudoprimes?

Starting with $n=0$: $k=2$ Given the roots $x_i$ of $x^2-x-1=0$. Then, we have the Lucas numbers, $$A_n = x_1^n+x_2^n = 2, 1, 3, 4, 7, 11, 18,\dots$$ The $n$ that divides $A_n-1$ are all the ...
1
vote
1answer
197 views

How to find the order of accuracy of this implicit RK method (using Taylor series)?

I want to get the order of accuracy (local truncation error - LTE) of this implicit 2-step method. The first step is Backward Euler to determine an approximation to the value at the midpoint in time, ...
1
vote
2answers
851 views

Minimum number of iterations in Newton's method to find a square root

I am writing an algorithm that evaluates the square root of a positive real number $y$. To do this I am using the Newton-Raphton method to approximate the roots to $f(x)=x^2-y$. The $n^{th}$ iteration ...
1
vote
0answers
236 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 ...
1
vote
3answers
2k 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 ...
0
votes
1answer
285 views

Simultaneous recursion

I have no idea how to even start proving the following theorem: If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, ...
5
votes
2answers
328 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 ...
10
votes
1answer
905 views

How else can we be nauty?

The graph canonical labelling package nauty is widely regarded as one of the best (if not the best) around. Unfortunately, it's quite a large package, and making a GPU version seems to be a highly ...
8
votes
1answer
105 views

Are the unit partial quotients of $\pi, \log(2), \zeta(3) $ and other constants $all$ governed by $H=0.415\dots$?

Khinchin showed that given the simple continued fraction of a real number, $$r = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1} {\ddots}}}$$ then it is almost always true that the partial quotients $a_i$ ...
7
votes
1answer
772 views

Why is Householder computationally more stable than modified Gram-Schmidt?

I'm having trouble nailing down why using Householder transformations yields a more stable/accurate result than the modified Gram-Schmidt method when computing the QR decomposition of a matrix. Can ...
4
votes
2answers
51 views

What are all the concordant forms $n$ such that $a^2+b^2 = c^2,\,a^2+nb^2=d^2$ for $n<1000$?

Part I. The list of congruent numbers $n<10^4$ such that the system, $$a^2-nb^2 = c^2$$ $$a^2+nb^2 = d^2$$ has a solution in the positive integers is known (A003273) $$n = 5, 6, 7, 13, 14, 15, ...
2
votes
2answers
483 views

Galois group command for Magma online calculator?

I need to test if a family of 7th deg and 13 deg equations are solvable. I'm new to Magma, so my apologies, but what would I type in, http://magma.maths.usyd.edu.au/calc/ to determine the Galois ...
8
votes
3answers
309 views

Three pythagorean triples

Are there any solutions for $a, b, c$ such that: $$a, b, c \in \Bbb N_1$$ $$\sqrt{a^2+(b+c)^2} \in \Bbb N_1$$ $$\sqrt{b^2+(a+c)^2} \in \Bbb N_1$$ $$\sqrt{c^2+(a+b)^2} \in \Bbb N_1$$
8
votes
0answers
91 views

Generalizing Bellard's “exotic” formula for $\pi$ to $m=11$

Bellard's "exotic" pi formula has the form, $$a\pi+b = \sum_{n=1}^\infty \dfrac{P(n)}{{\displaystyle \binom{mn}{2n}2^{n-1}}}$$ where $a,b,m$ are integers and he uses $m=7$. However, it seems there ...
6
votes
1answer
2k views

Wolfram Alpha error?

I was seeing some equations in WA, and i got with http://www.wolframalpha.com/input/?i=%28k%2B1%29%5E2%3E%3D4%28k-1%29%5E2 Let's manually solve the equation $$(k+1)^2\ge4(k-1)^2$$ ...
5
votes
1answer
154 views

Integer solutions to the equation $a^3+b^3+c^3=30$

The following problem was posed to me but I could not do much about it: Determine if there are any integer solutions to the equation $a^3+b^3+c^3=30$ I made a computer search that shows that ...
4
votes
1answer
108 views

GAP code to get Multiplication Table.

I have a finite set $S=\{0,1,2,\ldots,n-1\}$ and binary operation $\star$ on $S$ defined by $$x\star y= \left\{ \begin{array}{l l l} \frac{3(x+y)}{2} ~~\text{modulo} ~~n& \qquad \mbox{if $x$ ...
3
votes
1answer
175 views

Given 3 random points, what is the probability of these two situations involving a perpendicular bisector and distances?

Suppose we're given 3 random points $p_0=(x_0,y_0),p_1=(x_1,y_1),p_2=(x_2,y_2)$ from a two-dimensional continuous uniform distribution $\{U(a,b)\}^2$, for some $(a\in\mathbb{R})\lt (b\in\mathbb{R})$, ...
1
vote
0answers
69 views

An elliptic curve for the multigrade $\sum^8 a_n^k = \sum^8 b_n^k$ for $k=1,2,3,4,5,9$?

I. The first solution to, $$\sum^6_{n=1} a_n^9 =\sum^6_{n=1} b_n^9$$ $$13^9+18^9+23^9-5^9-10^9-15^9 = 9^9+21^9+22^9-1^9-13^9-14^9$$ was found in 1967 by computer search by Lander et al. It stood ...
0
votes
1answer
945 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 ...
6
votes
3answers
280 views

Mathematical Limitations of Computer Experiments

One problem that has always bothered me is the limitations of computers in studying math. With a chaotic dynamical system, for example, we know mathematically that they possess trajectories that never ...
5
votes
1answer
2k views

How does Knuth's algorithm for calculating logarithm work?

I had a look at Knuth's The Art of Computer Programming, book 1. In chapter 1, section 1.2.2, exercise 25, he presents the following algorithm for calculating logarithm: given $x\in[1,2)$, do the ...
4
votes
1answer
318 views

Computing with ideals: over $K$ or over $\mathbb{Q}\subseteq K$? does it matter?

I'm beginning to learn to use SINGULAR, the computer algebra system (CAS) for commutative algebra. NOTATION: If $K$ is a field of characteristic $0$, then $\mathbb{Q}\subseteq K$; otherwise ...
3
votes
3answers
136 views

Formal notion of computational content

In constructive mathematics we often hear expressions such as "extracting computational content from proofs", "the constructivity of mathematics lies in its computational content", "realizability ...
2
votes
0answers
172 views

Using GAP to compute the abelianization of a subgroup

Let $K$ be the group generated by four elements $x_1,\cdots,x_4$ with relations that each generator commutes with all its conjugates. (An equivalent relation is, any simple commutator with repeated ...
2
votes
1answer
176 views

Is there a computer programm or CAS (maybe GAP?) that can calculate with projective (indecomposable) A-modules (A is a finite dimensional k-algebra)?

I have the following question(s): I have an "Algebra-With-One" $R$ as a subalgebra of a full matrix algebra in GAP. Furthermore, I have 5 primitive orthogonal idempotents $e_1,...,e_5$, which sum up ...
1
vote
2answers
353 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
2answers
94 views

Is there any good strategy for computing null space of a matrix with entries $\cos x$ and $\sin x$?

For example, say $A= \left ( \begin{matrix} \cos x & -\sin x & 0 \\ \cos y \sin x & \cos x \cos y & -\sin y \\ \sin x \sin y & \sin y \cos x & \cos y \end{matrix} \right)$. ...
6
votes
3answers
724 views

FFT with powers of 3

Classic Fast Fourier Transfrom (FFT) works fine, when $n$ is power of 2. How to generalize FFT procedure when $n$ is power of 3? Is it possible to easily modify the algorithm and preserve its ...
3
votes
4answers
259 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 ...
3
votes
2answers
3k 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 ...
1
vote
0answers
156 views

Counting problem of combinations of symmetric matrix.

Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below- $G$ is partitioned in to two sub ...
1
vote
1answer
74 views

Is there a good strategy for computing eigenspace corresponding to $1$ of a matrix with entries of trigonom

For example, say $A= \left ( \begin{matrix} \cos x & -\sin x & 0 \\ \cos y \sin x & \cos x \cos y & -\sin y \\ \sin x \sin y & \sin y \cos x & \cos y \end{matrix} \right)$. ...