17 votes
Accepted

Are there any compression algorithms based on PI?

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 $\...
user avatar
14 votes

Are there any compression algorithms based on PI?

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: ...
user avatar
13 votes
Accepted

How does a computer interpret real numbers?

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....
user avatar
9 votes

How does a computer interpret real numbers?

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 ...
user avatar
  • 24.9k
8 votes
Accepted

Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor?

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 (...
user avatar
8 votes
Accepted

Is it possible to make a language that can build upon itself perfectly?

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. ...
user avatar
8 votes
Accepted

Is there way to calculate $\sum_{i<j<k\leq n} A_i \cdot A_j \cdot A_k$ faster than $O(n^3)$

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 \...
user avatar
6 votes
Accepted

Are regular languages and their regular expressions part of computer science?

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 ...
user avatar
  • 352
6 votes

Fermat's last theorem: How to (partially) solve by programs

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 ...
user avatar
  • 24.9k
5 votes
Accepted

How did the Logic Theorist prove the Pons Asinorum?

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 ...
user avatar
5 votes
Accepted

Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

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 ...
user avatar
  • 24.9k
5 votes
Accepted

Is global non-convex optimization NP-complete?

Yes, non-convex optimization is NP-hard. For a simple proof, consider the following reduction from Subset-Sum. The Subset-Sum problem asks whether there is a subset of the input integers $a_1, \dots, ...
user avatar
5 votes

Being stuck and frustrated with my masters project

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), ...
user avatar
5 votes

Understanding Time Complexity

This is just an example. Easiest to think of an algorithm that has two nested loops over an array of size $n$ (e.g. Bubble Sort). You are correct. Again, if you think of an algorithm that has two ...
user avatar
  • 1,369
4 votes

Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?

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 ...
user avatar
4 votes
Accepted

Approximate a float using a minimal fraction

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 $...
user avatar
4 votes
Accepted

Abs(sum of differences of elements in a sorted array) = array.Max()-array.Min() Why?

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 ...
user avatar
  • 506
4 votes
Accepted

Why does radix sort work?

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....
user avatar
  • 9,179
4 votes

Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

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 ...
user avatar
  • 280
4 votes

Is it possible to make a language that can build upon itself perfectly?

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 ...
user avatar
  • 6,978
4 votes
Accepted

Counting the number of multiples of number A that perfectly divides the number B

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$...
user avatar
  • 106
4 votes

Fermat's last theorem: How to (partially) solve by programs

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'...
user avatar
4 votes
Accepted

Min-plus matrix multiplication implementation

In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition. If you want to adapt matrix multiplication to the tropical semiring, you literally ...
user avatar
  • 16.1k
3 votes

How to find the most unique vectors in a set?

I suspect your problem might be NP-hard (by reduction from Clique), so it might be hard to find an efficient algorithm for it. One heuristic is to use the farthest-point first method, where at each ...
user avatar
  • 140k
3 votes

How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?

It can be computed in a completely analytical way. Take: $$ F_n = F_{n-1} + F_{n-2} + F_{n-1}F_{n-2} $$ Adding $1$ to both sides and factorizing we obtain: $$ F_n + 1 = (F_{n-1} +1)(F_{n-2}+1) $$ ...
user avatar
  • 4,112
3 votes

Good resources for understanding semidefinite relaxation for combinatorial problems

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 ...
user avatar
3 votes
Accepted

Solving for the matrix $W$ in an equation involving $W \cdot W^{T}$

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.
user avatar
  • 902
3 votes
Accepted

Can a computer count to infinity?

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 (...
user avatar
  • 20.3k
3 votes
Accepted

Matrix Multiplication Algorithms for Non-Square Matrices

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 ...
user avatar
3 votes

What are some of the practical applications of functions that extract the exponent and mantissa of a floating point number?

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 ...
user avatar
  • 24.9k

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