The Stack Overflow podcast is back! Listen to an interview with our new CEO.
22

As of now Fürer's algorithm by Martin Fürer has a time complexity of $n \log(n)2^{Θ(log*(n))}$ which uses Fourier transforms over complex numbers. His algorithm is actually based on Schönhage and Strassen's algorithm which has a time complexity of $Θ(n\log(n)\log(\log(n)))$ Other algorithms which are faster than Grade School Multiplication algorithm are ...


17

Your suggestion doesn't make much sense, for many reasons. First of all, when trying to compress a large file, say a file of size $16$ bytes, you will have to find a place in the binary expansion of $\pi$ which agrees with your file. Since the file is $128$ bits long, one would expect this place to be around the $2^{128}$th bit. So it would be rather hard to ...


14

Based on Yuval's answer, with a slightly different explanation and an example to help illuminate the problem. Theory Take a file $16$ bytes long ($128$ bits). The compression algorithm follows: Determine where the binary expansion of $\pi$ matches the contents. Store the offset and number of sequenced bits ($128$). The offset for the file contents should ...


13

They represent continuous quantities with discrete approximations. Mostly, this is done with floating point, which is analogous to scientific notation. Essentially, they work with something like $1.xyz\times 10^k$, with some appropriate number of decimal places (and in binary, rather than decimal). It's also possible to work with some irrational numbers ...


10

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP ...


9

Note that the FFT algorithms listed by avi add a large constant, making them impractical for numbers less than thousands+ bits. In addition to that list, there are some other interesting algorithms, and open questions: Linear time multiplication on a RAM model (with precomputation) Multiplication by a Constant is Sublinear (PDF) - this means a sublinear ...


8

Interesting that you reflect on this issue. This is very similar to the issues that I was reflecting on when I started my Phd research back in 1976. Back then Extensible Languages were very in vogue. The thesis then was that there must be some core of semantic and syntactic elements that could be used as the basis for all other languages. If we constructed ...


8

Let $A = \sum_{i=1}^n A_i$. We have $$ \begin{align*} A^3 &= \sum_{i=1}^n A_i^3 + 3\sum_{i=1}^n \sum_{j \neq i} A_i^2 A_j + 6 \sum_{i < j < k} A_i A_j A_k \\ &= \sum_{i=1}^n A_i^3 + 3 \sum_{i=1}^n A_i^2 (A - A_i) + 6 \sum_{i < j < k} A_i A_j A_k. \end{align*} $$ This gives a linear time algorithm. More generally, the theory of symmetric ...


8

The real numbers are uncountable. The set of real numbers that can be represented in any way is countable. Therefore, almost all real numbers cannot be represented by a computer at all. The most common method is to store floating point numbers, which are reasonably precise approximations to real numbers that are not excessively large or small.


7

Yes and no. “Instructions” isn't the right unit of measure: most processors include an ALU and require a single instruction to perform addition or multiplication on a number of a certain size (usually 8, 16, 32 or 64 bits, often with several possible sizes). A more relevant measure is the number of clock cycles required by this instruction. Counting ...


6

Coq is a bit more cruel than paper proofs: when you write "and we are done" or "clearly" in a paper proof, there is often much more to do to convince Coq. Now I did a little clean up of your code, while trying to keep it in the same spirit. You can find it here. Several remarks: I used built in datatypes and definitions where I thought it wouldn't hurt ...


5

The fundamental restriction is human computer programmers' inability so far to create computers equipped with real intelligence. "Never" is a very long time, so it's hard to accept that something will "never" happen unless there is a very good argument. Human brains and computers are not fundamentally different. The practical difference is that some human ...


5

If you google "logic theorist source code" you find this which is clearly not the original source code, but presumably is a modernization of the ideas in the code. You can also find this 1963 RAND memorandum which is a more contemporary description of the system. It seems to include a complete code listing as well as descriptions in terms of flowcharts. As ...


4

As the comments show, roundig is a respected method for Fibonacci computations. See also "Computation by rounding" in the wiki-lemma. You avoid roundoff by computing exactly, but using numbers of the form $a+b\sqrt5$: $(a+b\sqrt5)(c+d\sqrt5) = (ac+5bd)+(ad+bc)\sqrt5$. Technically that is $Z[\sqrt5]$ I believe. But I now realise that you also have to take ...


4

There is a library called SMAPO (short for library of linear descriptions of SMAll problem instances of POlytopes in combinatorial optimization) for a lot of polytopes including the symmetric TVP as well as the graphical TSP. For the STSP, this is the list of number of facets for small polytopes Nodes in STSP | # of facets ----------------+-------------...


4

Cody's answer is excellent, and fulfils your question about translating your proof to Coq. As a complement to that, I wanted to add the same results, but proven using a different route, mainly as an illustration of some bits of Coq and to demonstrate what you can prove syntactically with very little additional work. This is not a claim however that this is ...


4

The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A best rational approximation of $x$ is a rational number $p/q$ such that $\left|x-\frac{p}{q}\right| \leq \left|x-\frac{p'}{q'}\right|$ for all $q' \leq q$. Your $p/q$ is in particular a best rational approximation, ...


4

If you picture these as distances along a road, it should be very intuitive. If (for example) you start at kilometer #7, then proceed through kilometers #45, #81, and #97, then the distances you travel are 45−7, then 81−45, then 97−81; and the total distance you travel is 97−7. Since the total distance is the sum of the individual distances, 97−7 =&...


4

It depends what you mean by "doing mathematics". If you mean large scale computation, computers can easily do this, as can be seen from programs like Wolfram Alpha. Engines like these are obviously not perfect, but given the rate of development in machine intelligence, I don't think we have reason to believe this is a cause for limitation. If by "doing ...


4

Although you're question states to be about programming language, it seems to me there are also some questions on encoding that still need answering. Let's start with the ASCII. As you've said, the encoding is arbitrary. It seems you don't like this and would rather have an 'non-arbitrary' encoding. This hard to do, but more importantly, we don't want to ...


4

Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$. Let $C=p_0^{c_0}...p_n^{c_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\...


4

Let us denote the unknowns by $x_1,\ldots,x_n$, and the coefficients by $c_1,\ldots,c_n$. For a polynomial $P(x)$, we denote $$ [P(x)] = \sum_{i=1}^n c_i P(x_i). $$ We are given the values of $[1],[x],\ldots,[x^n]$, from which we can calculate $[P(x)]$ for every polynomial of degree at most $n$. In particular, we can compute, for each $j \in \{1,\ldots,n\}$, ...


3

There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha > 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both ...


3

It depends on what you mean by "count to infinity". Specifically, how does the computer give output? consider the following quesitons: Can a computer show, on its screen, all the number from 1 till (infinity): increasing the number on screen by 1 every second? Can a computer send on the network line, a package that contains a number starting with 1, and ...


3

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys is an excellent handbook on approximation algorithms. It has an entire chapter devoted to the topic of SDPs. As of now you can download the older version directly from their website; however the printed text is pretty affordable.


3

When considering algorithms for multiplying large numbers, the first think to keep in mind is the asymptotic complexity. Generally speaking, algorithms with better (smaller) asymptotic complexity are faster, though this only goes so far. So the first thing to do to find out whether Japanese multiplication is "worthwhile" is to calculate its asymptotic ...


3

You might be looking for the Cholesky decomposition. The referenced article also contains an example for $M$ having negative entries. Note the constraints on $M$ for this decomposition to exist.


3

The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations: $$ \begin{align} &\sum_{i=0}^n a_i = p, \\ &\sum_{i=0}^n a_i p^i = q. \end{align} $$ When $p < 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$. When $p = 1$, the equations imply ...


3

They are among other things very useful for calculating logarithms, or square roots and cubic roots. For example: log x = log ($2^e * m$) = e * log 2 + log m. With 0.5 ≤ m ≤ 1, you can approximate log m using a polynomial, which wouldn't work for x which can be in the complete range of floating point numbers. $x^{1/3}$ = $(2^e * m)^{1/3}$. Let e = 3k, 3k+...


3

The key point is that essentially all programming languages are equally powerful, and as powerful as we know how to make any computing system. That is, they can all simulate a Turing machine, up to the limitations of the computer they're used on. (Real computers can run out of memory; Turing machines can't.) The only differences between programming ...


Only top voted, non community-wiki answers of a minimum length are eligible