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

39
votes
4answers
18k 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 ...
19
votes
4answers
480 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. ...
6
votes
3answers
277 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 ...
4
votes
6answers
562 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 now:...
4
votes
2answers
226 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 ...
5
votes
5answers
561 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 ...
1
vote
2answers
114 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 ...
21
votes
8answers
6k 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 ...
16
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 ...
10
votes
1answer
107 views

Given two algebraic conjugates $\alpha,\beta$ and their minimal polynomial, find a polynomial that vanishes at $\alpha\beta$ in a efficient way

Inspired by this question, I was wondering about the following problem. $\alpha,\beta,\gamma,\ldots$ are the roots of an irreducible polynomial over $\mathbb{Q}$. How to compute the coefficients ...
7
votes
2answers
562 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 ...
17
votes
5answers
982 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 ...
9
votes
9answers
15k 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 ...
12
votes
1answer
208 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, $$F(m)=m^2+...
9
votes
2answers
3k 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 ...
11
votes
1answer
448 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 ...
7
votes
5answers
385 views

What is a nice way to compute $f(x) = x / (\exp(x) - 1)$?

I want it to be stable near $f(0) = 1$. Is there a nice function that does this already, like maybe a hyperbolic trig function or something like expm1, or should I just check if $x$ is near zero and ...
4
votes
4answers
99 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, ...
1
vote
2answers
1k 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
77 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
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 ...
48
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, ...
9
votes
1answer
136 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$ ...
10
votes
6answers
582 views

Calculating logs and fractional exponents by hand

In view of what we can compute by hand, on a piece of paper, without having to use a computer or a calculator, how far can we go with the evaluation of $\log$-functions and fractional powers? More ...
12
votes
2answers
304 views

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

I realize that 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=...
9
votes
0answers
108 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 ...
9
votes
3answers
335 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
1answer
983 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 ...
5
votes
3answers
2k views

What free software can I use to solve a system of linear equations containing an unknown?

Question: What free software can I use to solve a system of linear equations $M\mathbf{x}=\mathbf{y}$ where the entries of $\mathbf{y}$ vary with an unknown quantity $n$? Presumably I could do this ...
5
votes
2answers
346 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 ...
11
votes
1answer
1k 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 ...
6
votes
3answers
130 views

Digits of $\pi$ using Integer Arithmetic

How can I compute the first few decimal digits of $\pi$ using only integer arithmetic? By 'integer arithmetic' I mean the operations of addition, subtraction, and multiplication with both operands as ...
6
votes
3answers
297 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
170 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
122 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
177 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})$, ...
3
votes
2answers
637 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 ...
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$$ $$(k+1)^2-(2k-2)^2\...
2
votes
1answer
188 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 ...
2
votes
0answers
213 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
0answers
82 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
1k 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 ...
-2
votes
2answers
95 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
905 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 ...
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
324 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 $\mathbb{...
3
votes
2answers
4k 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 ...
3
votes
1answer
217 views

Conjecture about Rabin-Miller pseudo prime test

I tested the Rabin-Miller pseudo prime algorithm using a single test value and found that the number of false calls depends on the size of the number to test, reducing to a (conjectured) negligible ...
3
votes
4answers
261 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
1answer
76 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...