# Tag Info

23

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

9

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.

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

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

7

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

6

There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about. The three relevant distinctions for this question in my opinion are as follows: First The notion of regular languages and related things like recursive enumerability. Individual regular languages ...

6

See for example Sophie Germain. Sophie Germain proved that every prime number p with certain properties could be used as an expoonent in Fermat's Last Theorem. She used her theorem to prove that all primes up to 100 would work. Apparently checking her theorem was quite a lot of work because later her theorem was used to check first the primes up to 187 and ...

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

5

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project. ...

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

Radix sort sorts numbers by sorting on the least significant digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the most significant digit first. The key point to radix sort is that the digit sorts used in each iteration of radix sort are stable: numbers (digit here) with the same value appear in the ...

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$,[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\}$, ... 4 First of all, it is well-known that it suffices to consider odd prime$n$Kummer showed that if$p$doesn't divide the numerators of any of the Bernoulli numbers$B_2,B_4,\ldots, B_{p-3}$then Fermat's last theorem holds for$n = p$. Such primes are called regular. Vandiver gave a criterion which handles irregular primes. The criterion is a bit complicated, ... 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.

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