# Question
Title: Using limits to determine asymptotic bound
By using limits, show that log n! ∈ Θ(n logn).

Using Stirling's approximation for n! I get the limit: $$\lim\_{n \to ∞} \frac{log({\sqrt{2πn}}\*(\frac{n}{e})^n)}{nlogn} = constant \> 0$$

When I break this down separately: $$\lim\_{n \to ∞} \frac{\sqrt{2πn}}{n^n} * \lim\_{n \to ∞} (\frac{n}{e})^n = constant \> 0$$

To me, the left limit approaches 0 and the right limit approaches infinity. Can I not rewrite the limit like this? Or do I need to use L'Hopistal's rule? Because I don't understand how I would do that here.

# Answer
You have some algebra mistake but, in general, you are right that you cannot always rewrite a limit of products as the products of limits. Let $f(n)$ and $g(n)$ be two functions. Then $$\lim\_{n \to \infty} f(n)g(n) = \lim\_{n \to \infty} f(n) \cdot \lim\_{n \to \infty} f(n)$$ only holds if $\lim\_{n \to \infty} f(n)$ and $\lim\_{n \to \infty} f(n)$ exist and are either both finite, or one is infinite and the other is not $0$.

To handle the original limit without using L'Hôpital's rule: $$ \begin{align\*} \lim\_{n \to \infty} \frac{\log n!}{n \log n} &= \lim\_{n \to \infty} \frac{\log (\sqrt{2\pi n} \cdot (n/e)^n )}{n \log n}\\ & =\lim\_{n \to \infty} \frac{\log \sqrt{2\pi n}}{n \log n} \+ \lim\_{n \to \infty} \frac{\log (n/e)^n }{n \log n} \\ &=0 + \lim\_{n \to \infty} \frac{n \log n }{n \log n} - \lim\_{n \to \infty} \frac{n \log e}{n \log n} =1 - 0 = 1. \end{align\*} $$

Therefore $\log n! \sim n \log n$.
> 0 votes

# Answer
$$\log\left(\sqrt{2\pi n}\left(\dfrac ne\right)^n\right)=\log\sqrt{2\pi}+\frac12\log n +n\log n-n.$$

Clearly, this expression is dominated by the term $n\log n$ and your limit is $1$.
> 1 votes

# Answer
You broke this down, but in a very unpractical way.

$\log {(n/e)^n} = n \log (n /e) = n (\log n - 1)$ is much more helpful.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: The length of the shortest $s$-$t$ path equals the maximum tension between $s$ and $t$
I am stuck at the following exercise:

> Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t \in V$ and weights $w\_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. For any $i \in V$ let further be $\pi\_i \in \mathbb{R}$ be the so-called **potential** of $i$. The potential difference $\tau\_{ij} = \pi\_i − \pi\_j$ is called the **tension** of the arc $(i, j)$ with respect to the potential vector $\pi$. Finally, let $\mathcal{P}$ denote the set of all directed paths from $s$ to $t$.
>
> Now consider the following LP $(P)$: \begin{align} \max& \sum\_{(i,j) \in P} \tau\_{ij}\\ s.t. & \qquad P \in \mathcal{P} \\ & \qquad \tau\_{ij} = \pi\_i - \pi\_j \text{ for all $(i,j) \in A$}\\ & \qquad \tau\_{ij} \le w\_{ij} \text{ for all $(i,j) \in A$}\\ & \qquad \pi\_i \in \mathbb{R} \text{ for all $i \in V$} \end{align}
>
> If $P^\ast$ is a path for which the maximum in $\mathcal{P}$ is achieved, the value $\sum\_{(i,j) \in P^\ast} \tau\_{ij}$ is referred to as **maximum tension** between $s$ and $t$.
>
> Prove that under the assumption that an $s$-$t$ shortest path exists with respect to the arc weights $w\_{ij}$, the length of a shortest $s$-$t$ path equals the maximum tension between $s$ and $t$.

If I am not mistaken we have by the definition of $\tau\_{ij}$ that $\sum\_{(i,j) \in P} \tau\_{ij} = \pi\_s-\pi\_t$, so the maximal tension is constant for all $P \in \mathcal{P}$. Could you please tell me what I am misunderstanding?

Remark: I know that this is supposed to be the dual of the shortest path problem, but I am supposed to do this directly.

# Answer
The statement in the exercise, "If $P^\ast$ is a path for which the maximum in $\mathcal{P}$ is achieved, the value $\sum\_{(i,j) \in P^\ast} \tau\_{ij}$ is referred to as **maximum tension** between $s$ and $t$." is indeed quite confusing.

As you have pointed out, given $i\to\pi\_i$ for all $i\in V$ and $\tau\_{ij}=\pi\_i-\pi\_j$, we know the sum $\sum\_{(i,j) \in P} \tau\_{ij} = \pi\_s-\pi\_t$ does not depend on the choice of $P \in \mathcal{P}$.

Here is an equivalent but clearer definition of the maximum tension.

Consider a directed graph $G = (V, A)$ with start vertex $s ∈ V$, target vertex $t ∈ V$ and weights $w\_{ij} \in \mathbb{R}$ for each arc $(i, j)\in A$. Assume there is a path from $s$ to $t$. Then the maximum tension of $(G, s, t, w)$ is the optimal value of the objective function of the the following linear program. When $G$ and $w$ are understood, we also call it the maximum tension from $s$ to $t$.

$$\begin{array}{rl} \max&\pi\_s-\pi\_t\\ s.t. & \pi\_i - \pi\_j \le w\_{ij} \text{ for all }(i,j) \in A\\ & \pi\_i \in \mathbb{R} \text{ for all $i \in V$} \end{array}$$

The essential point here is that the assignment $\pi\_i$ for all $i\in V$ are independent variables in the linear program above.
> 1 votes

---
Tags: graphs, optimization, shortest-path, linear-programming
---


title: Hamiltonian Graph Way

text:
# Question
Title: Hamiltonian Graph Way
Recently i studied three theorems which says about Hamiltonian graph, they are as follows,

1. Dirac's Theorem: Let G be some simple graph of order n \>= 3,

for all vertices of the graph G, its degree \>= n/2 then we say given simple graph is actually an Hamiltonian graph.

2. Ore's Theorem: Let G be a simple graph of order n \>=3,

sum of degree of any two vertices which are not adjacent \>= n then we say given simple graph is an Hamiltonian graph.

3. Another is a simple graph with (n-1) C 2 edges + 2 edges implies its an Hamiltonian graph.

given this basic definition, my question is will this even work in reverse manner, suppose if i give an hamiltonian graph will all this theorem satisfy? Below is one question i am wondering about!!

thankyou in advance! :)

# Answer
Consider a graph $G$ that is a single cycle of length $\geqslant 5$. Then it should be clear that none of the properties is true, while $G$ is hamiltonian.
> 1 votes

---
Tags: graphs, hamiltonian-circuit
---


# Question
Title: Why solving #2SAT in polynomial time implies P = NP?
The wikipedia article for #P states that if we have a polynomial-time algorithm for a #P-complete problem, P = NP is true.

As #2SAT is #P-complete, this would mean that providing a polynomial-time algorithm for #2SAT implies P = NP.

But why exactly is that? It means that there is at least one NP-complete problem that can be reduced to #2SAT right?

# Answer
> 2 votes
*The Complexity of Enumeration and Reliability Problems* by Leslie G. Valiant gives a series of reductions to prove that $\sharp\texttt{3SAT}\leqslant \sharp\texttt{2SAT}$. Since there is a trivial reduction from $\texttt{3SAT}$ to $\sharp\texttt{3SAT}$, you have the wanted reduction.

---
Tags: complexity-theory, satisfiability, p-vs-np, counting
---


# Question
Title: Are there any NP-complete problems that are also in IP?
I am wondering if anyone knows if there are any NP-complete problems that are also known to be in IP (interactive polynomial time). I know problems like Graph Isomorphism are in IP, but such problems are not known to be NP-complete.

Moreover, if there were or were not an NP-complete problem in IP, what would be the consequences?

# Answer
> 2 votes
$$ IP = PSPACE $$ According to wikipedia. Thus $NP \subseteq IP$ and all NP-complete problems are in $IP$.

---
Tags: complexity-theory, np-complete, interactive-proof-systems
---


# Question
Title: Are there any known interactive proof protocols for NP-complete problems?
In a 2015 Quanta article talking about a breakthrough in the graph isomorphism problem, it was mentioned that graph isomorphism has a unique property where we have an interactive proof protocol for it. That is a prover can convince a verifier that two graphs are not isomorphic in polynomial time. That is, for the *graph non-isomorphism problem* a prover can convince an efficient verifier that two graphs are not isomorphic. We note that graph non-isomorphism is not known to be in either $NP$ or $BPP$.

But (as indicated by the Quanta article), is it the case that we have no known interactive proof protocol for NP-complete problems? That is, do we not have interactive proof protocols for problems like say the complement of Subset-Sum, where a prover needs to convince a polynomial-time verifier that there is *no subset* of the problem whose instance equals a target value?

And moreover, what would be the implication if there was, or was not such an algorithm for an NP-complete problem? If my understanding is correct, if there was such an algorithm, then it would prove that $coNP \subset IP$, but this is already known since $IP =PSPACE$, so I suppose I am confused on why this problem would be a big deal or not.

# Answer
That article is talking about Arthur-Merlin protocols, which are a certain type of interactive protocol, with additional restrictions. IP = PSPACE doesn't apply, because not all interactive protocols are Arthur-Merlin protocols.

It is known that graph non-isomorphism is in AM. Also, it is considered unlikely that the complement of any NP-complete problem is in AM: if that were true for any NP-complete problem, then all of coNP would be contained in AM, which would imply some implausible consequences that complexity theorists don't expect to be true.

Consequently, it is considered unlikely that graph isomorphism is NP-complete. If graph isomorphism were NP-complete, then it would be a problem whose complement is in AM, proving that all of coNP is in AM, which would be surprising.
> 1 votes

---
Tags: complexity-theory, np-complete, co-np, interactive-proof-systems
---


# Question
Title: Formal proof for in-balanced pipeline throughput
It is a well known fact, the throughput of a given compute pipeline (say, CPU instruction pipeline) is determined by its "slow" segment.

All the resources I've seen so far, demonstrates this fact via describing a **concrete** pipeline with 2-3 stages.

I'd love to see, more-or-less, some formal proof, the above holds for any in-balanced K-pipeline.

# Answer
This is formalized in Amdahl's law, which provides a quantitative version of that claim.
> 0 votes

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Max-flow problem with additional constraint
Consider the max-flow problem with a set of additional constraints, each in the following form: the flow on edge $e$ must equal the flow on edge $e'$. My question is how to modify existng max-flow algo to solve this variant.

# Answer
One way to solve the max-flow problem is that of considering the its linear programming formulation and using any algorithm to solve linear-programs.

Given a directed graph $G=(V,E)$, a source $s \in V$ with no incoming edges, a sink $t \in V$ with no outgoing edges, and a non-negative capacity $c\_e$ for each edge $e \in E$, the formulation has one variable $f\_e \in \mathbb{R}$ for each edge $e \in E$ and it is as follows: $$ \max \sum\_{(s,v) \in E}f\_{(s,v)} \quad \mbox{s.t.} \\ 0 \le f\_e \le c\_e \quad \forall e\in E \\ \sum\_{(u,v) \in E} f\_{(u,v)} = \sum\_{(v,u) \in E} f\_{(u,v)} \quad \forall v \in V \setminus \\{s,t\\} $$ You can directly add your constraints to this formulation in the form $ f\_e = f\_{e'} $.
> 2 votes

---
Tags: algorithms, optimization, combinatorics, network-flow
---


# Question
Title: search for the next prime number more efficiently?
```
   bool isPrime(int n) const {
    if(n<2)return false;
    if(n==2)return true;
    if(n%2==0)return false;
    for(int i=3;(i*i)<=n;i++){
        if(n%i==0)return false;
    }
    return true;
}

```

this worst case procedure should produce an O (sqrt (N)) which would be the number of comparisons I am going to do in the for loop.

Now if I add this:

```
    int getPrime(int n) {
    int i=n;
    while(!isPrime(i))
        i++;

    return i;
}

```

I should have an O (n) * O (sqrt (n)) and therefore the total complexity should be O (n ^ 2) more precisely n for the while loop and n ^ 1/2 the for loop now if i sum the exponent i will have n ^ 3/5 then O (n ^ 1.5)

It's right?

does anyone know a way to do it more efficiently?

# Answer
If this is going to be called a small number of times, efficiency doesn't really matter.

If it's going to be called many times, then `isPrime()` should cache a list of already discovered primes (or an array of booleans indexed by the number to be tested) and run the loop only if *n* is larger than the largest in the list.

If you have some idea of the range of values this is going to be used with, you can seed the cache using the Sieve of Eratosthenes.

Also, you can trivially cut the time in half by incrementing the loop indices by 2 rather than by 1, skipping the even values.
> 1 votes

---
Tags: time-complexity, algorithm-analysis, runtime-analysis, big-o-notation, primes
---


# Question
Title: How to get the formal model using propositional logic
**Input**

There are three chairs (1,2,3) in the same row. We need to find a seat for three guests (a,b,c).

**Constraints**

* The first guest does not want to be seated next to the third one (neither left nor right).
* The first guest does not want to be placed on the leftmost chair.
* The second guest does not want to be seated on the right side of the third.

How would this translate to propositional logic? I have difficulties coming out with a solution because all the models I've seen did not have these constraints that depend on two inputs. The end goal is to solve this problem by using a SAT solver.

# Answer
For this problem, the simplest approach is to try all $3^3=27$ cases by hand.

If you must use a SAT solver, introduce boolean variables to represent the solution. A natural approach is to let $x\_{i,j}$ be true if the $i$th guest sits in the $j$th chair. Now you should be able to take it from here and translate each of those constraints into a boolean formula on those variables. For instance, your first constraint can become the formula $$\neg(x\_{1,1} \land x\_{3,2}) \land \neg(x\_{1,2} \land x\_{3,1}) \land \neg(x\_{1,2} \land x\_{3,1}) \land \neg(x\_{1,3} \land x\_{3,2}).$$ You should be able to turn that into a formula in CNF form, and to translate the other constraints as well.
> 1 votes

---
Tags: satisfiability, propositional-logic
---


# Question
Title: Consider a Hamming(7, 4) code and the word 1111111 received at the output of a noisy binary channel
Why is it possible that this word can have 4 errors but not 2?

# Answer
The message 1111111 cannot have 2 errors because 1111111 is a valid codeword and the minimum Hamming distance between any two distinct codewords of $H(7,4)$ is $3$.

To see that it can have $4$ errors, notice that 0010110 is a valid codeword.
> 0 votes

---
Tags: error-correcting-codes, hamming-code
---


title: 0<i => 0 < i + j proof?

text:
# Question
Title: 0<i => 0 < i + j proof?
If we have the natural numbers defined as:

Plus the following:

$pred \space \\\_\\\_\<\\\_\\\_ \space: Nat \times Nat$

$\forall i,j:Nat$

* $0\<suc(j)$
* $\neg(i\<0)$
* $suc(i) \< suc(j) \Longleftrightarrow i\<j$

How to prove $0\<i =\> 0 \< i + j$ by induction?

For the base case the premise fails when $i=0$, and thus the implication holds.

For the induction step, we assume $i = suc(i')$ for some $i':Nat$ such that $\forall j:Nat, \space 0\<i' =\> 0 \< i' + j $ **(IH)**

We assume $0 \< i$ **(H)**, so, we have $0 \< i =\> 0 \< suc(i')$

But I can't move from there, as I need to find a way to use the inductive hypothesis (IH) to complete the proof, but I don't know how. Can you help please?

# Answer
There is no need for an induction here.

* if $j = 0$ then $0\<i \Rightarrow i + j = i + 0 = i\>0$;
* otherwise, $j = suc(j')$ and $0 \< i \Rightarrow i+j = i+suc(j') = suc(i + j') \> 0$.
> 1 votes

---
Tags: induction, formal-methods, software-verification
---


# Question
Title: How to Apply Elementary Axioms from Kleene Star to an Inequality
## Axioms For *

\begin{align} 1 + aa^\* &\leq a^\* \\ 1 + a^\*a &\leq a^\* \\ b + ax &\leq x \to a^\*b \leq x \\ b + xa &\leq x \to ba^\* \leq x \\ \end{align}

## Elementary Results

\begin{align} a \leq b &\to a + c \leq b + c \\ a \leq b &\to ac \leq bc\\, \wedge\\, ca \leq cb \\ a \leq b &\to a^\* \leq b^\* \end{align}

## Problem

Prove the following identity in a Kleene algebra using only the axioms and elementary results. $$(a + ab + b)^\* = (a + b)^\*$$

Solution: \begin{align} (a + b)^\* &= (a + ab + b)^\* \\ (a + b)^\* &\leq (a + ab + b)^\* \\ 1 + (a + b)(a + b)^\* &\leq 1 + (a + ab + b)(a + ab + b)^\* \\ (a + b)(a + b)^\* &\leq (a + ab + b)(a + ab + b)^\* \\ \end{align}

## Quesiton

1. So for them to be equal the sets should be contained in each other. At which point do I transition to an inequality?
2. Is it right to say a $\*$ cannot be removed since it has no inverse?
3. Can I distribute into a $\*$? Say $(a +b)(a + b)^\*$ or do they need to have the same $\*$ height?

Some hints to get further would be greatly appreciated.

# Answer
> 2 votes
I assume that in your definition $a \leq b$ iff $a + b = b$.

First, note that if $a \leq b$ and $b \leq a$, then $a = a + b = b + a = b$. Therefore, in order to show that $a = b$, it is sufficient to show that $a \leq b$ and $b \leq a$.

Now, you want to show that $(a + b)^\ast = (a + ab + b)^\ast$. As explained in the previous paragraph, it is sufficient to show that inequalities with $\leq$ in both directions hold (*"\[...\] for them to be equal the sets should be contained in each other"*).

---

The inequality $(a + b)^\ast \leq (a + ab + b)^\ast$ is almost trivial:

$$(a + b) + ab = a + ab + b $$

therefore $(a + b) \leq (a + ab + b)$, and by monotonicity (your ER-3), it thus holds

$$(a + b)^\ast \leq (a + ab + b)^\ast.$$

---

The other direction is a bit trickier.

By monotonicity (ER-2), (def-$\leq$), (Ax-1):

$$a(a + b)^\ast \leq (a + b)(a + b)^\ast \leq 1 + (a + b)(a + b)^\ast \leq (a+b)^\ast$$

Analogously, $b(a + b)^\ast \leq (a+b)^\ast$.

From both previous statements, again using monotonicity (ER-2):

$$ab(a+b)^\ast \leq a(a+b)^\ast \leq (a+b)^\ast.$$

To summarize: so far, we know that $a$,$b$ and $ab$ are all $\leq (a+b)^\ast$.

Now, observe that from (ER-1), it follows that if $x \leq w$ and $y \leq w$, then $x + y \leq w + y \leq w + w = w$. Thus, from $a\leq (a + b)^\ast$, $ab \leq (a + b)^\ast$ and $b \leq (a + b)^\ast$, you obtain:

$$(a + ab + b)(a+b)^\ast = a(a+b)^\ast + ab(a+b)^\ast + b(a+b)^\ast \leq (a + b)^\ast.$$

Since additionally $1 \leq (a+b)^\ast$ (directly from Ax-1), you obtain:

$$1 + (a + ab + b)(a+b)^\ast \leq (a+b)^\ast.$$

With (Ax-3) it follows:

$$(a + ab + b)^\ast = 1\cdot(a + ab + b)^\ast \leq (a + b)^\ast$$

---

Thus, both inequalities hold, hence we get the equality.

You cannot simply "remove" $^\ast$, nothing is told about "inverse" in the definition of a Kleene algebra. I also don't know what you mean by "$\ast$-height".

# Answer
> 0 votes
You need a full set of axioms. For this, you can use the axioms for

1. a monoid: *associativity* $x(yz) = (xy)z$ and *identity* $x1 = x = 1x$;
2. a partial ordering possessing least upper bounds $⋁F$ of finite subsets $F$: defining $0 = ⋁∅$ and $a + b = ⋁\\{a,b\\}$: an equivalent set of identities is captured by another instance of monoid axioms $x + (y + z) = (x + y) + z$, $x + 0 = x = 0 + x$, along with upper semi-lattice axioms $x + y = y + x$ and $x + x = x$; and
3. finite distributivity: $x\left(⋁A\right)y = ⋁\left(\\{x\\}A\\{y\\}\right)$, which is equivalently captured by the *zero property* $y0z = 0$ and *distributivity property* $w(x + y)z = wxz + wyz$.

So, yes, you can always distribute and the sum operator, $+$, is the least upper bound operator. The ordering relation is equivalently given in terms of the least upper bound operator by way of the following equivalences $x ≤ y ⇔ y ≥ x ⇔ ∃z (y = x + z) ⇔ y = x + y$. In addition, the sum and product operator are both order-preserving, as a consequence ... so are all polynomials.

The resulting algebraic structure is an *idempotent semiring*, which is also known as a *dioid*. Adding in the \*-operator, along with your axioms (or any of a number of other equivalent axiomatizations), make this a set of axioms suitable for *Kleene algebra*.

The * operator is also order-preserving. If $a ≤ b$, then $1 + a b^\* ≤ 1 + b b^\*$, therefore $\[a^\* = \]1 a^\* ≤ b^\*$, by your \*-axioms. So, all Kleene-algebraic operators, and functions composed therefrom, are order-preserving.

Since $a + b ≤ a + ab + b$, then $\left(a + b\right)^\* ≤ \left(a + ab + b\right)^\*$. The proof of $\left(a + ab + b\right)^\* ≤ \left(a + b\right)^\*$ was already given in another reply.

It generalizes to $f(a,b) ≤ (a + b)^\*$, for *all* Kleene-algebraic functions $f(a,b)$ of $a$ and $b$. In fact, the only values a Kleene-algebraic function of $(a + b)^\*$ can take, are $0$, $1$ and $(a + b)^\*$, which, by virtue of $f(a,b) ≤ f((a + b)^\*, (a + b)^\*)$, renders the proof of $f(a,b) ≤ (a + b)^\*$ trivial. Another way of saying this is that the Kleene-subalgebra generated by $(a + b)^\*$ is just $\\{0, 1, (a + b)^\*\\}$, which is either a 3-element Kleene algebra or else is the unique 2-element Kleene algebra $\\{0,1\\}$, with $(a + b)^\* = 1$, if $a + b ≤ 1$.

Thus, $(a + b)^\*$ is the maximum element of the Kleene-subalgebra generated by $\\{a,b\\}$.

---
Tags: proof-techniques, regular-expressions, check-my-answer, kleene-star, algebra
---


# Question
Title: How to show closure of regular languages without DFA,NFA,reg expressions
Given a $\Sigma$ I define a regular language as one of the folllows:

* $\emptyset$
* $\left\\{ \sigma \right\\}$ for any $\sigma \in \Sigma$
* $L\_1 \cup L\_2$ for regular $L\_1, L\_2$
* $L\_1 \cdot L\_2 $ for regular $L\_1,L\_2$
* $L^\*$ for regular $L$

Now, I would like to show that for a given regular language $L$, its complement $\overline{L}$ is regular as well. I want to do so based only on this definition (i.e. without proving its equivalent to DFA, NFA or reg expression).

However, I'm having a bit of trouble here, not sure how to do so. Maybe I want to express the complement of $L$ as a sort of unions/contactinations? Not really sure how to go for it. Any ideas?

# Answer
> 1 votes
Your definition is the same as the usual definition with regular expressions. While regular expressions also admit the empty word $\epsilon$, it is expressible as $\emptyset^\*$.

There is no simple rule for complementing regular expressions, and it is known that such complementation can result in an exponential blow-up (for example, the language of all words *not* containing all alphabet symbols has a regular expression of size $O(|\Sigma|^2)$, but its complement requires a regular expression of length exponential in $|\Sigma|$).

# Answer
> 1 votes
Complement means relative complement $Σ^\* - L$. You already have closure under set subtraction and, in fact, also intersection and even interleave. So, the real question is how to do set-subtraction.

You can evaluate it algebraically, but you get a system that amounts to the description of a deterministic automaton. I will only illustrate it with a couple of examples, one of which will involve the relative complement with respect to $Σ^\*$, where $Σ = \\{a,b\\}$.

**Example 1:** $a b^\* a - (ab)^\*a$:
Set $A = a b^\* a - (ab)^\*a$. Using the identity $x^\*y = y + x x^\* y$, we write $$A = a b^\* a - (a + a b (a b)^\* a) = a\left(b^\* a - 1 - b (a b)^\* a\right) = a B,$$ where $B = b^\* a - 1 - b (a b)^\* a$ and $1$ denotes the empty word.

The set-theoretic subtraction of $1$ is trivial since $b^\* a$ does not contain the empty word. Therefore, we can write $B = b^\*a - b (a b)^\* a$. Thus, continuing on, we have $$B = a + b b^\* a - b (a b)^\* a = a + b\left(b^\* a - (a b)^\* a\right) = a C + b D,$$ where, $C = 1$ and $D = b^\* a - (a b)^\* a$.

For $D$, we have $$D = a + b b^\* a - a - a b (a b)^\* a = a\left(1 - 1 - b (a b)^\* a\right) + b b^\* a = b b^\* a,$$ since the set-theoretic identity holds $x - x - y = 0 - y = 0$.

The resulting system $$A ≥ a B, B ≥ a C + b D, C ≥ 1, D ≥ b b^\* a,$$ has to be written as a system of inequalities to avoid infinite regresses that occur if repeats of terms appear on the right-hand side (e.g. an equation like $D = ⋯ + D + ⋯$); and it is the *least* solution we seek out.

Solving for $(C,D)$ immediately yield the results $(C,D) = \left(1, b b^\* a\right)$. Substituting into the other two inequalities yields $$A ≥ a B, B ≥ a + b b b^\* a = \left(1 + b b b^\*\right) a,$$ whose least solution is $$(A,B) = \left(a \left(1 + b b b^\*\right) a, \left(1 + b b b^\*\right) a\right).$$

The corresponding automaton has states $A$, $B$, $C$, $D$, plus whatever other states result from reducing the expression for $D$ to a system of inequalities. The start state is $A$, and $C$ is a final state, plus whatever other final state might come from the subsystem headed by $D$. (There are none. The subsystem headed by $D$ leads back to $C$ as its sole final state.) The expression of interest is that for $A$, and we can thus write $$ab^\*a - (ab)^\*a = a\left(1 + b b b^\*\right)a.$$

**Example 2:** $(a + b)^\* - (a + b)^\* b b (a + b)^\*$
Setting this expression to $A$, you can write $$A = 1 + a A + b \left(A - b (a + b)^\*\right) = 1 + a A + b B,$$ where $B = A - b (a + b)^\*$. In-line substituting this expression for $A$ into $B$ yields $$B = 1 + a A + b \left(B - (a + b)^\*\right) = 1 + a A.$$ The last equality follows from the identity $f(a,b) - (a + b)^\* = 0$, for any regular expression $f(a,b)$ in $a$ and $b$, since the set corresponding to $(a + b)^\*$ is maximal. Thus, the corresponding system is $$A ≥ 1 + a A + b B, B ≥ 1 + a A,$$ which, upon in-line substitution of the expression for $B$ into $A$, yields $$A ≥ 1 + a A + b + b a A = 1 + b + (a + b a) A,$$ whose least solution is $A = (a + b a)^\* (1 + b)$. Thus, $$(a + b)^\* - (a + b)^\* b b (a + b)^\* = (a + b a)^\* (1 + b).$$

---
Tags: regular-languages, kleene-star
---


title: Worst-case prime sieve

text:
# Question
Title: Worst-case prime sieve
The Sieve of Eratosthenes bothers me because you have to specify an upper bound before you begin the algorithm.

Is there a prime sieve that doesn't require this?

More Formally:

Is it possible to write an iterator on which the i'th call to next() yields the prime number $p\_i$ in only $O((p\_i - p\_{i-1})log(log(p\_i)))$ time for all i \> 1 ?

(Note: I'm looking for a worst-case solution, not amortized. For amortized time, you can simply use Sieve of Eratosthenes and restart the algorithm doubling n each time you hit the previous upper bound)

# Answer
Most fast sieves are segmented, so you can get this in efficient amortized time. When you call to get the next segment, you may have to increase the auxiliary prime list, but that's a trivial amount of time. Then you just sieve that segment, exactly how it would be done if you were sieving to some large known upper bound. You can wrap all of that in a next() call. I believe primesieve and primegen both have setups like this. This is also how my `forprimes` and `forcomposites` work, as well as my iterator in Perl/ntheory.

This is likely faster than prime-by-prime extensible sieves. I see in the Rosetta Code extensible prime generator task the C solution is a simple segmented generator like I mention above. The first D solution is the rather horrible method you noted. A number of the languages, including Go, implement O'Neill's lazy functional sieve which is more directly what you might be asking for. Ben Tilly shows a lazy sieve using closures in Perl here that should meet your complexity goal.

Of course you can do primality tests, but that takes more time than sieving until your input is large (how large depends on your implementations of both sieve and primality test, but it would certainly be before 10^25).
> 2 votes

# Answer
What you are after is called an "incremental sieve" in the literature. The sieve of Bengalloun does a little better than what you have requested: it only requires $O(p\_i - p\_{i-1})$ time, and can be sped up by a $\log\log p\_i$ factor. The article is paywalled, but there is a nice brief description of the algorithm in Paul Pritchard, "Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987) pp.17-35.
> 0 votes

# Answer
That's actually just a bit of clever programming; I wouldn't even call it "computer science". Create a data structure that you call a sieve. For example, using one byte for the numbers from 30k to 30k + 29 to indicate which of 30k+1, 30k+7, 30k+11, 30k+13, 30k+17, 30k+19, 30k+23 and 30k+29 are primes. At any point in time, you store two values 30k and 30k', and allocate (k' - k) bytes of memory indicating which primes there are in the interval 30k ≤ p \< 30k'.

If you want to know if p is a prime: If p \< 10 then 2, 3, 5, 7 are primes. Otherwise write p = 30k + n, 0 ≤ n \< 30. If n mod 30 ≠ 1, 7, 11, 13, 17, 19, 23, 29 then n is not prime. If 30k + n is not in the stored range then recreate a sieve with a different starting point. But most likely you just look up one bit in a sieve.

Depending on your use, you may *always* store bits for small primes because you will often need them, plus bytes for some additional range which is variable. And when you change the stored range, make sure there is some overlap - if your sieve stored numbers from 3 trillion to 3 trillion + 299,999 then you don't want to recalculate a sieve if I examine p, p+1, p-1, p, p+1, p-1 etc. with p at the end or the start of your sieve.
> 0 votes

---
Tags: primes
---


title: How does Pollard's rho algorithm work?

text:
# Question
Title: How does Pollard's rho algorithm work?
I am trying to understand how does `Pollard's rho` algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and also on internet but still can not understand its structure or analysis. This is a java implementation of the pseudocode from the CLRS book along with `euclid` `gcd` algorithm:

```
public static void pollardRho(int n) {
    Random rand = new Random();
    int i = 1;
    int x0 = rand.nextInt(n);
    int y = x0;
    int k = 2;
    while (true) {
        i++;
        int x = (x0 * x0 - 1) % n;
        int d = gcd(y - x, n);
        if (d != 1 && d != n) {
            System.out.println(d);
        }
        if (i == k) {
            y = x;
            k *= 2;
        }
        x0 = x;
    }
}

public static int gcd(int a, int b) {
    // fixes the issue with java modulo operator % returning negative
    // results based on the fact that gcd(a, b) = gcd(|a|, |b|)
    if (a < 0) a = -a;
    if (b < 0) b = -b;

    while (b != 0) {
        int tmp = b;
        b = (a % b);
        a = tmp;
    }
    return a;
}

```
* Why does it choose $x = (x\_0^2 - 1) \mod n$?
* What does $y$ actually represent and why is it chosen to be equal to $\\{x\_1,x\_2,x\_4,x\_8,x\_{16},...\\}$?
* Why does it compute $\text{GCD}(y-x,n)$ and how does $d$ turns out to be a factor of $n$?
* And why is the expected running time is $O(n^{1/4})$ arithmetic operations and $O(2^{\beta/4} \beta^2)$ bit operations assuming that $n$ is $\beta$ bits long?

I understand that if there exists a non-trivial square-root of $x^2 \equiv 1 \pmod{n}$ then $n$ is a composite and $x$ is a factor, but $y - x$ is not a square root of $n$ is it?

# Answer
The idea behind Pollard $\rho$ is that if you take any function $f : \[0, n - 1\] \to \[0, n - 1\]$, the iteration $x\_{k + 1} = f(x\_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and consider it modulo $n = p\_1 p\_2 \dotsm p\_r$, where the $p\_i$ are primes:

$\begin{equation\*} x\_{k + 1} = f(x\_k) \bmod n = f(x\_k) \bmod p\_1 p\_2 \dotsm p\_r \end{equation\*}$

Thus it repeats the same iteration structure modulo each of the primes into which $n$ factors.

We don't know anything about the cycles, but it is easy to see that if you go with $x\_0 = x'\_0$ and:

$\begin{align\*} x\_{k + 1} &= f(x\_k) \\ x'\_{k + 1} &= f(f(x'\_k)) \end{align\*}$

(i.e., $x'$ advances twice as fast) eventually $x'\_k$ and $x\_k$ will span one (or more) cycles (see Floyd's cycle detection algorithm for details), thus in our case, $x'\_k \equiv x\_k \mod{p\_i}$, and $\gcd(x'\_k, x\_k)$ will be a factor of $n$, hopefully a non-trivial one.

Any polynomial works, but we want irreducible ones (no non-trivial factors, detecting those is not the point of the exercise). Linear polynomials don't give factors, next simplest to compute is a quadratic one, but just $x^2$ doesn't work either (reducible), so take $x^2 + 1$ for simplicity. Remember the idea here is to work with very large numbers, few and simple arithmetic operations are a distinct bonus. The analysis of the algorithm (e.g. in Knuth's "Seminumerical algorithms") models $f(x) \bmod p$ as a random function, which is close enough to explain the overall characteristics of the algorithm.
> 5 votes

# Answer
Just one part of the answer: You calculate a sequence and look for cycles. There are two well-known algorithms for cycle detections, Brent's and Floyd's. One calculates $x\_{2k}$ and $x\_k$ in parallel which will find cycles, the other tries to detect cycles of length ≤ 2, then length ≤ 4, then length ≤ 8, then length ≤ 16 etc. by calculating 2^k values from some starting point with k growing if no cycle is found. For example, if it takes 25 steps to enter a cycle of length 39, then when k = 32, y is set to a point in the cycle. When k = 64, x hasn't quite gone through the cycle since step 32, so y is set to a different point in the cycle (note that the algorithm doesn't know that it is inside the cycle). Then the algorithm would progress x until k = 128, but after 39 steps at k = 103 the cycle is found.

And another part: If p is a factor, then the sequence $x\_k \mod p$ will run into a cycle after about $p^{1/2}$ iterations (at most p iterations, but the birthday paradox reduces it to the square root). But you can detect cycles for *all* primes simultaneously by checking whether n and $x\_i - x\_j$ have a common factor \> 1. That common factor divides n.

An interesting thing is that pollard-rho will find for example a factor p = 127 always at exactly the same number of iterations (specific to the number 127, and the specific implementation), no matter which n that is a multiple of 127 you would examine.

Warning: The algorithm that you found is incomplete. First, it is very slow if n is not composite. It takes $O(n^{1/2})$ if n is a prime and will tell you "n is divisible by n", so you know nothing that you didn't know before. So after say $5 n^{1/4}$ iterations you start suspecting that n is prime and try to prove it. Second, pollard-rho can find two or more factors simultaneously. Worst case, if say n = p x q x r, it is possible that pollard-rho tells you "n is divisible by p x q", so you need to check if the factors you get are indeed primes. Worse, it is possible that pollard-rho tells you "n is divisible by n" if it found the factors p, q and r at the same time. Which is 100% true and 100% useless, so you have to run the algorithm again with say x^2 + 2, x^2 + 3 etc. instead of x^2 + 1. This is rare.

When you implemented your algorithm, you can make a table telling you which prime factor p is found after how many iterations. If you find multiple primes that take the same number of iterations, then their products will cause you trouble. Note that this is a property of the algorithm and the prime, not a property of n.

PS. Why not x^2 - 1? One reason is that if you get x = 1 at some point, you are stuck. And you have to be careful if you get x = 0. But I'd suggest that if you have the algorithm implemented with x^2 + 1, then you just check what happens if you replace it with x^2 and x^2 - 1. Will it still work?

PS. Only just noticed: If n is a prime, your algorithm will run forever. If pollard-rho finds n as a factor, then it's very likely that you have a prime, so you would check that.
> 1 votes

---
Tags: algorithms, modular-arithmetic, factoring
---


# Question
Title: Removing k-smallest elements in a binary min-heap
Assuming a contiguous array implementation of a binary min heap with `n` elements, is it possible to remove the k-smallest elements in a faster time than $O(k \log n)$, as can be done via iteratively removing the minimum of the heap $k$ times?

More formally, by removal of k smallest elements, I mean removing the k smallest elements in the binary heap, ending up with a binary heap that does not have those k elements that have been removed, and a separate array that contains those k smallest elements (possibly unsorted).

# Answer
> 0 votes
No, it is not possible: since it is possible to build a min-heap with $n$ elements in $\mathcal{O}(n)$ time, being able to remove $k$ elements in $o(k\log n)$ would result in a sorting algorithm in $o(n\log n)$ when removing $n$ elements.

Since a sorting algorithm must be $\Omega(n\log n)$ in the worst case, you have the answer.

Note that, as @Russel pointed it out in the comment, you could get the $k$ smallest **unsorted** elements in $\mathcal{O}(k)$ time.

---
Tags: algorithms, heaps
---


title: Push Down Automata

text:
# Question
Title: Push Down Automata
I am learning about context free languages.

I understand how $\\{a^nb^nc^n|n\>0\\}$ can be shown to be not context free using the pumping lemma for CFL's.

Intuitively however it seems that a pushdown automata to recognize $\\{a^nb^nc^n|n\>0\\}$ can be constructed. This PDA would initially push single a's into its stack whenever it sees an a in the input. It would change state when it first encounters a b and do nothing on the stack for every b it encounters. When the first c is encountered, it would again change state and pop single a's for every c encountered. If the stack is empty at the end of the input the language is recognized as $\\{a^nb^nc^n|n\>0\\}$.

There must be something I am overlooking whilst constructing the PDA as a language is context free if its has a PDA recognizing it. Please point out my mistake.

# Answer
Because there is no control on the number of $b$'s, such a pushdown automaton would recognize $\\{a^nb^mc^n\mid n, m\> 0\\}$ which is indeed context-free.
> 3 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Complementation of deterministic Streett automata
There are a lot of work about bounds on the complementation of Streett automata (see e.g. this paper). They talk about the general setting of nondeterministic Streett automata. But what about deterministic ones?

Streett automata are closed under determinisation although with an exponential blow-up. And complementation has an exponential complexity. So I would suppose that complementation of deterministic Streett automata would be simpler, maybe polynomial?

So, how do I complement **deterministic** Streett automata? Is the task computationally easy?

**Edit**: as far as I can tell, this question is equivalent to asking how to translate a deterministic Rabin automaton to an equivalent deterministic Streett automaton.

# Answer
> 4 votes
This paper gives an example of a deterministic Rabin automaton with $\mathcal{O}(n)$ states such that there is no nondeterministic (hence no deterministic) equivalent Streett automaton with less than $2^n$ states.

I guess there is no hope for a polynomial complementation, even if the Streett automaton is deterministic.

---
Tags: automata, omega-automata
---


# Question
Title: Let F be a function defined for all nonnegative integers by the following recursive definition
Let F be a function defined for all nonnegative integers by the following recursive definition. F(0) = 0, F(1)= 1 F(n + 2) = 2F(n) + F(n +1), n\>0 Compute the first six values of F; that is, write the values of F(n) for n = 0,1,2,3,4,5

# Answer
> 0 votes
Let $F(n)=a^n$ and assume that the recurrence also holds for $n=0$.

Then

$$a^{n+2}=2a^n+a^{n+1}$$ so that

$$a^2-a-2=0$$ and $a=-1,2$.

By the theory of linear recurrences, the general solution is of the form

$$c\_+2^n+c\_-(-1)^n.$$

The initial conditions tell us that $c\_++c\_-=0$ and $3\\,c\_+=1$.

Hence

$$F(n)=\frac{2^n-(-1)^n}3.$$

Now plug $n=0,1,2,3,4,5$.

# Answer
> 0 votes
$$F(0)=0,\\F(1)=1,\\F(3)=2F(1)+F(2)=F(2)+2\\F(4)=2F(2)+F(3)=3F(2)+2,\\F(5)=2F(3)+F(4)=5F(2)+6.$$

---
Tags: logic, recursion, sets, counting
---


# Question
Title: Consider a ternary channel with the following channel matrix:
\begin{bmatrix} 1-\alpha & 3\alpha/4 & \alpha/4\\ \alpha/4 & 1-\alpha & 3\alpha/4\\ 3\alpha/4 & \alpha/4 & 1-\alpha\\ \end{bmatrix}

I was told that the probability of error of this channel can not be $\alpha/4 $ or $3\alpha/4$. How do I know this? How can i find the probability of error?

# Answer
> 1 votes
Consider an input symbol $x$. The probability that the output symbol differs from $x$ is $\alpha$ (regardless of the choice of $x$).

Therefore, regardless of the input distribution, the probability of error will be $\alpha$. As you see, you can have $\alpha = \alpha/4 = 3\alpha/4$ when $\alpha=0$.

---
Tags: information-theory, coding-theory
---


# Question
Title: Is there an algorithm for this decision problem that is better than brute-force?
Apologies for the vague title. This decision problem has applications to graph coloring but I have not found a name for it in the literature.

I am trying to improve my algorithm for a decision problem. The problem input is a graph and hypergraph which have the same vertex set, $(V, E, H)$ where $V$ is the set of vertices, $E$ is the set of edges, and $H$ is the set of hyperedges.

# The Hostile Soldiers and Alliances Game

Imagine there is a set of soldiers (vertices) such that for every pair of soldiers, either:

* The two soldiers are hostile towards each other (there is an edge between them), or
* They are indifferent towards each other (there is not an edge between them)

The soldiers can also be involved in a set of *alliances* (hyperedges).

Two alliances $A$ and $B$ can go to *war* if there exists:

* some nonempty set of soldiers $X \subseteq A \setminus B$, and
* some nonempty set of soldiers $Y \subseteq B \setminus A$

such that every soldier in $X$ is hostile to every soldier in $Y$, i.e., $X$ and $Y$ form a biclique.

The *war* results in a new alliance made up of all the soldiers who did not participate in the hostile biclique, $(A \cup B) \setminus (X \cup Y)$. An alliance cannot go to war with itself.

Now imagine that your goal is to come up with a sequence of wars (biclique, hyperedge, hyperedge) such that the last war produces an alliance with zero members. Each edge in $E$ can be used at most once in the sequence of wars.

Pictured is an example

This problem is in NP, since a proof certificate can have at most $|E|$ bicliques. I suspect that this problem is NP-complete but I have not found a reduction yet.

# My algorithm attempt

```
function decide(graph, hypergraph) -> bool:
    for each pair of hyperedges A, B in hypergraph:
        for each biclique X, Y in A, B:
            C = (A \/ B) - (X \/ Y)

            if C is empty:
                return True

            if decide(graph - biclique, hypergraph + C):
                return True

    return False

```

I am not sure of the time complexity of this algorithm, but since it is brute-force looking for a sequence of wars, I would not be surprised if it is factorial in the number of bicliques (which itself is exponential in the number of vertices).

I have not seen a case yet where a solution requires that a hyperedge is used twice in the sequence of wars. I haven't been able to prove it, but if so, then I could change the algorithm to recur on `(graph - biclique, (hypergraph + C) - (A + B))`, that is, the algorithm could eliminate $A$ and $B$ from the search after using them in a war.

Are there any opportunities for improving this algorithm?

# Answer
I figured out that this problem is isomorphic to CNF-SAT where:

* Each hyperedge $H = {v\_1, v\_2, ... v\_n}$ corresponds to a clause $(v\_1 \lor v\_2 ... \lor v\_n)$
* Each edge $(u, v)$ corresponds to the clause $(\neg u \lor \neg v)$

And a "war" between hyperedges corresponds to a particular form of resolution, where:

* $(\bigvee\_a^A a \lor \bigvee\_b^B b)$
* $(\bigvee\_c^C c \lor \bigvee\_d^D d)$
* $\bigwedge\_{(b, c)}^{B \times C} (\neg b \lor \neg c)$

resolves to:

* $(\bigvee\_a^A a \lor \bigvee\_d^D d)$

Moreover, any CNF-SAT instance can be converted into the form $\bigwedge(a \lor b \lor ... c) \land \bigwedge (\neg d \lor \neg e)$ by replacing any negated literal $\neg x\_i$ with a new variable $n\_i$ and introducing a new clause $(\neg x\_i \lor \neg n\_i)$.

Therefore there is no "sequence of wars" that leads to an empty hyperedge unless NP = coNP.
> 1 votes

---
Tags: algorithms, graphs, np, decision-problem
---


title: subtract the weight of the largest edge

text:
# Question
Title: subtract the weight of the largest edge
I have an oriented and weighted graph, and I need to find the cheapest route from source to destination. Now I have a source node A and a destination node B the cheapest path is given to me by the sum of the weight of the arches to which I have to subtract the discount, the discount is given to me by the weight of the largest arch that I encounter during the journey.

so for example

in the result the first number indicates the sum of the weight of the arches while the second number indicates the discount that I am going to subtract, i.e. the arch with the greatest weight that I encounter in my path

```
0-> 2-> 3-> 4 = 10-5

0-> 1-> 3-> 4 = 11-5

0-> 1-> 4 = 16-12 (this is the solution)

```

# Answer
> 0 votes
Not that the distance is always \> 0. The solution still doesn't require revisiting a node later, so Djikstra should be usable.

Idea: the weight of a path is always going to be (sum of all edge weights of edges in the path) - (highest weight of edge in path)

Djikstra guarantuees we always know the shortest path to a node. If we also store the discount of the current path to each node, we can know whether an edge counts as (weight of the edge) or (current discount \[ because edge weight - new discount + old discount = old discount\]), and use that as the weight wherever Djikstra needs it.

Pseudocode (adapted from Wikipedia):

```
function Dijkstra(Graph, source):

       for each vertex v in Graph.Vertices:
           dist[v] ← INFINITY
           prev[v] ← UNDEFINED
           discount[v] ← UNDEFINED
           add v to Q
       dist[source] ← 0
       discount[source] ← 0

       while Q is not empty:
          u ← vertex in Q with min dist[u]
          remove u from Q

          for each neighbor v of u still in Q:
              if Graph.Edges(u, v) > discount[u]:
                  alt ← dist[u] + discount[u]
                  if alt < dist[v]:
                      dist[v] ← alt
                      prev[v] ← u
                      discount[v] ← Graph.Edges(u,v)
              else:
                  alt ← dist[u] + Graph.Edges(u, v)
                  if alt < dist[v]:
                      dist[v] ← alt
                      prev[v] ← u
                      discount[v] ← discount[u]

      return dist[], prev[]

```

# Answer
> 1 votes
It's possible to solve this using a common trick: rather than altering the algorithm, alter the graph.

"Subtracting the weight of the largest edge" is the same as "setting the weight of the largest edge to 0". In other words, we want to find the shortest path where one edge is allowed to have weight 0.

To solve this, create a second copy of the graph. Let's write `a`, `b` for nodes in the original graph, and `a'`, `b'` for nodes in the new graph. Then for every edge `a --> b` in the original graph, add a new edge `a --> b'` from the original graph to the new graph with edge-weight 0. Then run Dijkstra's as normal.

That's it! The path will only be able to move from the old graph to the new one with cost 0 one time, encoding the fact that only one edge can be changed to 0.

---
Tags: algorithms, graphs, shortest-path, weighted-graphs, dijkstras-algorithm
---


# Question
Title: Why is determining if there is a solution to a Battleship puzzle NP-Complete?
This paper http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf says that the decision problem, "Given a particular puzzle, is there a solution?" is NP-Complete. I don't understand why this can't be done in polynomial time. Given constraints that no two ships can be orthogonally or diagonally adjacent, why not just create a grid where there are 2 times as many columns as "bins" with enough rows to put a "separator" run in between every ship. I've seen the reduction demonstrated this way and it seems like it could be done in polynomial time.

# Answer
> 5 votes
As Andreas T mentions, what you're missing is that the grid is part of the instance.
The instance specifies both the grid and the ships.

Why can't the Battleship puzzle be solved in polynomial time? This is the one million dollar question (literally). But since the paper you mention proves that Battleship is NP-complete, the widely believed conjecture P≠NP implies that Battleship cannot be solved in polynomial time.

The paper goes on to prove that Battleship cannot be solved in polynomial time even when the solution is unique, unless NP=RP, which is also considered unlikely. This is a more realistic version of the problem, since in practice Battleship problems have a unique solution.

# Answer
> 0 votes
What it means is: They have found an NP-complete problem that could be solved by creating a very cleverly designed "Battleship" instance of at most polynomial larger size, solving the "Battleship" instance and creating a solution for the original instance from that.

It's really a guess, but I suppose they figured out a way to simulate logical circuits by setting up a "Battleship" problem. With "Game of Life", I think you can create "gliders" that effectively simulate a very primitive computer.

---
Tags: np-complete, np-hard
---


# Question
Title: Modern proof of Goldwasser-Sipser IP[n]=AM[n+2]?
The original paper by Goldwasser and Sipser proved IP\[Q(n)\]=AM\[Q(n)+2\].
Is there some modern source that proofs the theorem? (The full theorem and not specific cases such as limiting the number of rounds to 2.)

# Answer
> 0 votes
See Appendix F.2.1. of Oded Goldreich's book here: https://www.wisdom.weizmann.ac.il/~oded/CC/r6.pdf

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Is it possible to measure how fast the humans are moving their bodies with different level(slow, normal, fast) from video?
Examples like

* swinging both of their hands
* squat
* walking around
* jump around
* etc

Is it possible to perform this in real time under crowded scene without depth information?

I can find out the "action level" if I knew what kind of action the person are doing, but can't find a fast solution to find out their action level if I don't know what kind of action they are doing.

Method I tried

**First**

Use adaptive background segmentation solutions like mog and mog2 of opencv, count the proportions of the foreground, but this solution cannot measure how fast the person is doing. There exist some frequencies patterns for the change of the foreground proportions, but it is hard to measure the wave of the frequencies reliable since the patterns may from A to Z.

**Second**

Use the multi-pose algorithm and tracking algorithm to compare the different positions of each pose. I measure out the pose of the person, and then compare the difference of the last keypoints, not good enough to measure how fast the people moving their body either.

pseudo codes

```
total_diff = abs(kpts_1 - kpts_2).sum()

```

**Third(Just an idea, haven't tried)**

Store n images(ex: 100), classify the action of the person by a cnn model, then measure their action level. This should work, but it can't work with crowded scenes.

**Fourth(Just an idea, haven't tried)**

Collect clips of different movement, give the activity level for different video clips manually, train a 3D/2D convolution models to classify the activity level. This will need a lot of videos, not a practical solution.

Do any research paper trying to solve this issue? What are the keywords I should try? Thanks

The keywords I tried:

Computer vision, measure human action speed

# Answer
> 0 votes
Sure. Use any method for detecting the pose of the person (or keypoints for their hands, arms, etc.) in every frame. Then, it is trivial to measure the "speed" of movement, in pixels per second: this is the distance between the two keypoint locations in two frames, divided by the time between the two frames. This measures the speed in the plane orthogonal to the vector from the camera to the person (i.e., it ignores the component of the speed in the direction towards or away from the camera).

Converting pixels per second to a more reasonable unit, like meters per second, will require a bit more work. One reasonable approach is to assume a specific height for the person, based on the average height of people, and use that as your calibration. Another way is to estimate the distance to the person (using machine learning models for monocular depth estimation, or using a RGBD camera, or using a binocular camera), and then use the camera geometry to convert a pixel distance to distance in meters.

---
Tags: algorithms, algorithm-analysis, computer-vision
---


# Question
Title: Efficiently finding/ sampling from all solutions to a constrained linear problem
Start with $N\>3$ vectors $\vec{v}\_I$ in $\mathbb{R}^3\_+$, any $3$ of which are linearly independent. $I$ here ranges from $0$ to $N-1$.
Let $v\_{\left\[abc\right\]}$ be a matrix in $\mathbb{R}^{3 \times 3}\_+$ that picks three of the (column) vectors $\vec{v}\_a\\, \vec{v}\_b\\, \vec{v}\_c$ in order $a \< b \< c$, without duplication. There are $\frac{1}{3!}N \left(N-1\right) \left(N-2\right)$ such matrices, and $\left\[abc\right\]$ enumerates them.

For each $v\_{\left\[abc\right\]}$, find the linear combination $\vec{w}\_{\left\[abc\right\]}$ that lands on a particular arbitrarily chosen point $\vec{p}$, i.e. $v\_{\left\[abc\right\]} \vec{w}\_{\left\[abc\right\]} = \vec{p}$.
Discard those linear combinations, which contain negative coordinates. Of the remaining, now non-negative combinations, if there are any, find the average. (Otherwise, return nothing)

$$\begin{align\*} {w\_{\left\[abc\right\]}}\_i &= \sum\_j {{v}\_{\left\[abc\right\]}^{-1}}\_{ij} p\_j \\ \omega\_{\left\[abc\right\]} &= \begin{cases} 1 & \text{if } 0 \le \min\_i\left({w\_{\left\[abc\right\]}}\_i\right) \\ 0 & \text{else} \end{cases} \\ n &= \sum\_{\left\[abc\right\]}\omega\_{\left\[abc\right\]} \\ w\_i &= \frac{1}{n} \sum\_{\left\[abc\right\]} {w\_{\left\[abc\right\]}}\_i \omega\_{\left\[abc\right\]} \text{ if } n\>0 \end{align\*}$$

An alternative filtering method also filters out linear combinations greater than some constant, say, $1$:

$$ \omega\_{\left\[abc\right\]}= \begin{cases} 1 & \text{if } 0 \le \min\_i\left({w\_{\left\[abc\right\]}}\_i\right) \le 1 \\ 0 & \text{else} \end{cases} $$

and instead of the unweighted average, a sample from an $n$-choice dirichlet distribution could also be taken as a weighted average, to sample from the space of all weight combinations that satisfy the filtering constraint. (I hope this is a correct statement. I haven't actually formally proved this part)

Now the question is, is there a method to calculate this, that is more efficient, than explicitly following this recipe? The $\frac{1}{3!}N \left(N-1\right) \left(N-2\right)$ very quickly makes this intractable for large $N$. In my use case, I'm looking for an $N$ somewhere between $400$ and $500$, giving me, in the worst case, $0 \le \left\[abc\right\] \< 20708500$, i.e. over 20 million matrix inversions for evaluating the correct weights for a single point.

Note: Constrained Optimization methods can absolutely find one solution that fulfills the constraints, but this method, if I did it right, finds, and can sample from the space of all of them. This is a desirable property for me. If the ability to sample from the full space makes this difficult, just finding precisely the (unweighted) average solution in a less resource-hungry way would also be appreciated.

---

I don't need absolutely insane speeds. It just needs to be tractable. I plan to implement this in python/numpy, so I don't expect ultra-optimized peak performance. But any way to save time and memory is good. Particularly great would be a "local" version of this, that lets me directly calculate a particular $w\_i$ with minimal effort.

---

I hope the notation here is clear enough. Some of the dimensionalities here are tricky so I'm not 100% sure that I got it right. Please ask if anything doesn't quite make sense.

# Answer
> 1 votes
I suggest you randomly sample 10,000 matrices $v\_{\[abc\]}$. Keep only the ones where the resulting linear combination $w\_{\left\[abc\right\]}$ meets your filtering constraints (e.g., is all positive). Average the ones kept. Output that as an estimate of the value you are seeking.

This should be a pretty good estimator of the value you are computing. You are trying to compute the expected value, with the expectation taken over all $N(N-1)(N-2)/6$ combinations, and this is a finite-sample estimate of that expectation. To put it another way, the sample mean is a good estimator for the population mean, and this method computes the sample mean. We're essentially using rejection sampling here to address the filtering condition.

How good will this be? That will depend on how many matrices/combinations you keep, with this method. Heuristically, I expect that the linear combination has about a probability $1/2$ to be non-negative in each coordinate, or about a $1/8$ probability to be non-negative in all three coordinates. So if your filtering condition is "all three coordinates must be non-negative", then I expect that you'll keep about $10000/8 \approx 1250$ combinations, which should be enough to get a good estimate of mean.

In comparison, if you had a filtering condition that was satisfied by only a miniscule fraction of matrices, then this method would not be a good choice.

---
Tags: linear-programming, linear-algebra, constraint-satisfaction
---


# Question
Title: How are frames split up in an inverted page table?
For an inverted page table, it's number of entries = number of frames in main memory.

One frame in the main memory, could be shared by two (or more) processes, say process A and process B. Usually this is noted down in process A and process B individual page table. Like process A page 0 maps to frame 1 offset 1-50, process B page 0 maps to frame 1 offset 51-100.

Since an inverted page table, has only one entry per each frame, so how is this frame splitting mechanism noted down? In this example, there is only 1 entry for frame 1, so how can it be split up to contain both process A and process B page offsets?

# Answer
> 0 votes
An inverted page table maps each page frame in physical memory to a list of one or more virtual pages in virtual memory. There is typically some kind of chaining or pointer to represent this list of virtual pages via a singly linked list. Since most page frames map to only a single process, this isn't needed for most page frames, but it is there for those where it is needed.

In the systems I am familiar with, there are no offsets. Each virtual page in virtual memory maps to a page memory in physical memory. For instance, with 4K pages, a 4K virtual page (4096 consecutive bytes in virtual memory) maps to a 4K page frame in physical memory (4096 consecutive bytes in physical memory).

---
Tags: operating-systems, virtual-memory
---


title: Representing graph as a search tree

text:
# Question
Title: Representing graph as a search tree
How do I convert a graph to a search tree? Here's the question-

The problem is that I don't know how to represent interconnections in a graph on a tree. In the diagram A is connected to D, and same goes for B and E, C and F. But in tree I think no interconnections should be there between sibling nodes. ***So how do I represent a search tree? It would be helpful if someone can also tell me what's the difference between a tree and a search tree.***

I didn't know how to do it so I drew a minimum spanning tree instead-

# Answer
Algorithms by Dasgupta, Papadimitriou and Vazirani represents a traversal tree as a tree rooted in the first vertex of the traversal search, with solid edges corresponding to edges crossed during the traversal, and dashed or dotted edges corresponding to remaining edges.

See page 92 of the pdf for an example.

There are interesting properties doing as such:

* the pre-order traversal of the tree is the same as the order of the traversal of the graph;
* the post-order traversal of a DFS tree in a directed acyclic graph results in a reverse topological order.

As for your last question, the main difference between a tree and a search tree is that the search tree is rooted.
> 0 votes

---
Tags: graphs, data-structures, search-trees
---


# Question
Title: What happens in harvard architecture pipelining if cpu needs to write data and fetch data at the same time?
What happens if Operand Fetch and Write Back happen in same cycle?

# Answer
> 0 votes
To avoid contention(hazard) between the 2 stages, a split cache i.e. I-cache(instruction cache) and a D-cache(data cache) is used. Consequently, Fetch and Writeback operations are handled by I and D cache respectively.

# Answer
> 1 votes
It depends on the processor design.

In the most simple solution, a pipeline bubble is inserted. The read (because it's earlier in the pipeline) has to wait until the next cycle after the write is done.

In a more complex processor with a cache, the cache may be able to process multiple read and write requests at the same time. In a design with a cache, both the read and write must be prepared to wait anyway, in case the cache line is not present in the cache.

---
Tags: computer-architecture, cpu, cpu-pipelines
---


# Question
Title: What are distinguishable terms in Bohm theorem?
I have just started to study "Lambda-Calculus and Combinators, an Introduction" by Roger Hindley.

There is a formulation of B ̈ohm’s theorem that I can not understand.

$M$ and $N$ are terms in bn-normal form. Based on the description I assume that $M$ could be equal to λ-term $x$ and $N=y$. $x≠y$. Both $x$ and $y$ do not have b-redexes and n-redexes. I do not understand how to distinguish between $M=x$ and $N=y$.

$xL\_1..L\_nxy =\> x$

$yL\_1..L\_nxy =\> y$

I have found another formulation of this theorem where everything is clear. A function is applied to terms rather than terms ($M$ and $N$) are applied to combinators.

# Answer
I believe the word "combinator" in your first statement of Böhm's theorem means a *closed* λ-term, i.e. one which has no free variables (as is the case here for instance); this is consistent with the fact that the statement at the end of your question mentions *closed* normal forms. Thus your example terms $M$ and $N$ are not combinators because $fv(M) = \\{x\\}$ and $fv(N) = \\{y\\}$, so they don't satisfy the assumption of Böhm's theorem.
> 2 votes

---
Tags: lambda-calculus
---


# Question
Title: How to calculate error bounds for the function behind the following algorithm?
D.E. Knuth, in his infamous The Art of Computer Programming, section 1.2.2, presents the following algorithm to efficiently calculate logarithms based on the method used by Henry Briggs:

> Suppose that we have a binary computer and a number $x$, $1\leqslant x \< 2$. Show that the following algorithm, which uses only shifting, addition, and subtraction operations proportional to the number of places of accuracy desired, may be used to calculate an approximation to $y=\log\_bx$:
>
> **L1.** \[Initialize.\] Set $y\leftarrow 0$, $z\leftarrow x$ shifted right $1$, $k\leftarrow 1$.
>
> **L2.** \[Test for end.\] If $x=1$, stop.
>
> **L3.** \[Compare.\] If $x-z \< 1$, set $z\leftarrow z$ shifted right $1$, $k\leftarrow k+1$, and repeat this step.
>
> **L4.** \[Reduce values.\] Set $x\leftarrow x-z, z\leftarrow x$ shifted right $k$, $y\leftarrow y+\log\_b(2^k/(2^k-1))$, and go to L2.

My question arose from the exercise right after the aforementioned algorithm:

> Determine the upper bounds on the accuracy of the algorithm in the previous exercise, based on the precision used in the arithmetic operations.

Knuth stays silent, giving no hints on its solution in his book.

I think I've seen something similar in the BKM Algorithm published in 1994. It uses a similar method to get logarithms and claims to have an error of $2^{-N}$ after $N$ iterations.

I kindly ask you to help me understand what does Knuth mean exactly by basing the determination of the upper bound on the precision used in the arithmetic operations, and how does one arrive at that error bound purely from this algorithm?

# Answer
$y$ is a sum of the constants $\log\_b\frac{2^k}{2^k-1}$, precomputed to a certain accuracy. These terms are summed until the value of $x$ is exhausted, i.e. (if I am right) the number of bits of $x$. So the total error is the error on the sum, itself bounded by $m$ times the accuracy, for $m$ terms.
> 0 votes

---
Tags: algorithm-analysis, error-estimation
---


# Question
Title: Getting something wrong while building parse table for the grammar
**Task** Build the Parse Table

> Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} E &\to TE' \\ E' &\to +TE'\\; |\\; \epsilon \\ T &\to F T' \\; \\ T' &\to \*FT'|\\;\\;\epsilon \\F &\to (E)\\; | \\;id \\ \end{aligned} $$

I calculated $ FIRST $ and $ FOLLOW $ sets \begin{aligned} FIRST(F) = FIRST(T) = FIRST(E) = \\{ (,id \\} \\ FIRST(T') = \\{\*,\epsilon\\}\\ FIRST(E') = \\{+,\epsilon\\} \\FOLLOW(E) = FOLLOW(E') = \\{ ),$ \\} \\ FOLLOW(T)=FOLLOW(T') = \\{+,),$\\}\\ FOLLOW(F) = \\{ +, * ,$ , )\\} \end{aligned}

Here is the rule while constructing parse table\ $$For\\; each\\; terminal\\; a\\; in\\; FIRST(A)\\;,\\; add \\; A \to \alpha; to\\; M\[A,a\]$$

When applying this rule to the production $$F\to(E)$$ I need to add this to $M\[F,id\]$ and $M\[F,(\]$ so when applying this rule again to $F\to id$, Should I need to add again to $M\[F,id\]$? Then ; It; is not LL(1) \]; grammar right? But it is given LL(1) . How , any mistake I have done?

# Answer
You have missed one important note. The rule is such

> For each production $A→α$ of the grammar, do the following:
> For each terminal $a$ in $FIRST(A)$, add $A→α;$ to $M\[A,a\]$

that is we only consider the elements in first set which is contributed by the production $A→α$ which here is $F→(E)$ ,

so for this rule ie $F→(E)$ the $FIRST(F) = \\{(\\}$ only

and for $F→id$ , $FIRST(F) = \\{id\\}$
> 0 votes

---
Tags: compilers, parsers
---


# Question
Title: Why is C still the fastest? Critique my take
A friend and I were surprised that C still has near-best performance among languages. I thought about why this is, and I wrote up a few paragraphs. I wonder if the friendly folks on CS stack could tell me where I'm wrong, too vague, or misleading. This will help me sharpen my understanding of the situation.

> One reason it’s hard to improve on C in the current context is that current OS’s force everything to “pass through” something like C anyway.
>
> When you write code in another language and execute it, the C-like thing it passes through need not be the C language itself (though pretty often it literally is, if some part of the language is implemented in C). But rather it’s the set of low-level primitives exposed by the OS (“system calls”). There aren’t terribly many of these (on the order of hundreds), and C is the modern language that is closest to them. In fact, it’s the only language(?) that actually contains the raw system calls inside the language.
>
> Using the notation “more abstract layer —(API)—\> less abstract layer”, you could write a simple diagram “your code —(system calls) —\> the OS —(instruction set) —\> the hardware”. Think of C as living pretty far to the right, toward the system calls. In fact it actually contains some (all?) of the system calls in the language itself, which I believe is unique among languages. So some parts of C are more like an API than they are like a language, and “API’s ossify”.
>
> You could ask, why not more system calls, each more specialized and optimized? Several hundred isn’t that many, in the face of the multitude of things computers can do. That question is probably deeper than I can answer, but my take is that all things being equal, a smaller API is a better API, because small API’s reduce combinatorial explosion.
>
> As your code is executed, you can understand it in stages, like a ladder, where up/down corresponds to more/less abstract. (It’s really a DAG, not a ladder, and maybe it need not even be strictly acyclic always, but whatever. Let’s pretend no branching for now.) Each rung in the ladder communicates with the rung below it through an API, that is, a little language which the lower rung created so you can tell it what you want it to do. You could even say that the rung *is just* some useful combinations of the API beneath it, packaged into an API for some higher rungs to use.
>
> Breaking things up into layers/stages/rungs is beneficial for understanding and reuse. First and fairly obviously, if you can factor out the function of one rung, you can reuse that rung, and it becomes worth it to devote significant effort to optimizing that rung. But second and maybe less obvious, if your program is in layers which communicate through limited-size APIs, it helps reduce combinatorial explosion in the space of how programs can operate. Another way to say this is with layers, there are fewer ways that things can go wrong at any layer. This is more true when the API’s on each layer are kept smaller. And third and maybe most important, the smaller an API exposed by a rung, the less you constrain the operation of the rung, so that the rung can change how it works and adapt to new situations, but still be used exactly as before.
>
> But breaking things up like this has costs. You’re always sacrificing efficiency in each individual case when you constrain your architecture like that. Also, the stability of APIs is a double-edged sword: nothing ossifies like an API. Because their benefit is that they’re reliable and stable, so many things come to rely on them, so no one wants to change them even if they’re long outmoded, because at any given moment no one wants to break everything. Hence the arcane commands at the terminal (bash language), and the relative stability of the set of system calls.

# Answer
> 4 votes
C is fastest because there is nothing *preventing* it from being the fastest.

A CPU always runs machine language. When writing a "fast" program, your goal is to give the CPU the fastest machine language to accomplish the task.

In C, it is usually possible to write something that translates into fast machine language - although you cannot write self-modifying code, or self-threaded code, for example. In other languages, you often have a lot less flexibility and the language forces you to have slower machine code.

For example, you may want to use SIMD instructions to process multiple pieces of data at the same time. In C, there's usually a compiler-specific extension which allows you to write these instructions - even if it's less convenient. In Java or C#, you simply can't use them because there's no way to use them.

Many languages insist on writing a bounds check every time you access an array. Many languages insist that you cannot access just half of a variable.

The history of C comes from people wanting to write "portable assembly code", or assembly code in a slightly nicer format. C has evolved in a direction that mostly allows you to do whatever your processor's machine code can do, and trusts you to use it responsibly. Most other languages focus on making it easier to write simple and reliable programs, and forbid you from doing things that are usually wrong. Not C.

TL;DR: C is flexible and doesn't stop you from doing things, therefore it doesn't stop you from writing fast code.

In case the fastest solution to your problem does involve self-modifying code or some other pattern which can't be expressed in C, you may find that assembly code is faster than C.

# Answer
> 4 votes
The OS has virtually nothing to do with the relative performance of languages on benchmarks. You wrote

> “your code —(system calls) —\> the OS —(instruction set) —\> the hardware”

suggesting you think that the OS acts as a sort of translation layer between user-mode code and the CPU, but in reality the OS just puts the CPU in the appropriate mode and jumps to the user code, which then runs directly on the hardware until it makes a blocking system call or it's preempted by a hardware interrupt. What runs directly on the hardware may be a bytecode interpreter, but if you were using the same language implementation without an OS, you would be using the same or a very similar bytecode interpreter. It doesn't matter what language the OS is written in, or whether an OS is present at all.

System calls usually aren't benchmarked in comparative language shootouts, so I have no hard data, but there should be no overhead in the system-call interface that is peculiar to system calls. When CPython computes `x+y`, it has to check the types of the heap objects `x` and `y`, extract the "raw" values from them, and create a new heap object to hold the result of the addition. The same steps are needed when you call an OS function that takes two numeric arguments and returns a numeric result. Data buffers (for file I/O and such) may be copied to and from the heap but don't have to be. Even CPython, which is a quite slow interpreter, supports raw I/O without copying.

The benchmark that you linked can't be trusted because it shows C++ as substantially slower than C. I don't know what they're benchmarking, but whatever it is, they could have taken their C benchmark code and compiled it as C++ with at most minor changes, and gotten the exact same performance. They chose instead to write less efficient C++ code, probably because they are biased toward thinking that C++ is a higher-level language in which you should write more maintainable code, while C is a low-level language in which you should write performance-maximizing spaghetti code. The numbers in the table reflect their biases and not the true abilities of the languages. That or the programmers they used for the different languages aren't equally skilled. Either way, all of the numbers are untrustworthy.

# Answer
> 1 votes
If one defines a "task" as a mapping between possible inputs a program might receive, and the set of possible outputs that would be acceptable for each such input, different languages will be able to process different tasks more or less efficiently. This will be especially true if one recognizes a task X as being a more specific version of Y if, for all possible inputs for which Y defines a set of possible outputs, the set of acceptable outputs for X is a subset of the set specified for Y.

In many cases, the only way of writing a program in a language that processes a broadly-specified task will be to write a program that processes a more specific version of that task, and the most efficient possible machine code for a program to process the specific version will often be less efficient than the most efficient program to process the original broadly-specified one. The efficiency of a language for processing some tasks will often depend to some degree to which programs written in that language would need to process needlessly specific versions of those tasks.

If one is evaluating how efficiently languages can process programs to perform tasks that can be precisely specified in language L, language L will be able to process such tasks precisely, without losing efficiency to over-precise specification. Consider the following three specifications for a function:

1. Given two 64-bit signed integers `x` and `y`, compute the bottom 64 bits of the mathematical product of `x` and 30, interpret them as a 64-bit signed integer, divide that by `y` using truncate-toward-zero division, and return the result.
2. Given two 64-bit signed integers `x` and `y`, return `x*y/30` if `x` is less than 300,000,000,000,000,000 and `y` is non-zero, and otherwise return any number.
3. Given two 64-bit signed integers `x` and `y`, return `x*y/30` if `x` is less than 300,000,000,000,000,000 and `y` is non-zero, and otherwise behave in any fashion whatsoever, without regard for ordinary rules about time and causality.

Each of the first two tasks is a more specific version of the one following it. A Java implementation, given the expression `x*30/y` would seek to generate the most efficient machine code to accomplish the first task. Even if the compiler could determine that `y` would always be 30, it would be obligated to generate code that performs multiplication, truncation, and division precisely as specified. A C implementation given that expression, however, would be allowed to generate the most efficient machine code for the third task. In situations where a compiler could prove that `y` would be 30, this could be vastly more efficient than the optimal code a Java implementation could produce for its task.

If one compares languages based upon how well they can handle tasks like #3 above, C will come out ahead. On the flip side, however, if one were to instead compare languages based upon how well they could handle tasks like #1 above, that advantage would disappear since any C code satisfying the tasks would have to specify the same operations as Java code. The advantage would also likely disappear for "standard C" if programs that perform task #2 above would be satisfactory, but those performing only task #3 would not, but would be available to C dialects which specify integer overflow behavior more precisely than the C Standard, but less precisely than Java.

# Answer
> 0 votes
It isn't really hard to understand what is a system call. On the x86-64 architecture, the high level code (like C or C++) is compiled to `syscall` in assembly. The assembler then converts the `syscall` instruction into its binary format that the processor understands. The `syscall` instruction makes the processor jump to the address found in the STAR64 register, a special register of the processor.

With current paging, x86-64 processors have 2 levels of protection: user and supervisor. This is set with flags in the page tables. When in user mode, the processor cannot execute privileged instructions and it cannot access supervisor mode pages. What it can do is execute `syscall` which makes it jump to a specific address in supervisor mode. At that specific address, the kernel will place an handler to handle system calls. Each operating-system is specific in what it will do in the handler. For example, Linux will look at RAX for the system call number but Windows will look at another register.

Once you understand this, I think your question becomes clear. C and C++ are most often the fastest because they compile directly to `syscall`. Meanwhile, languages like Python or Java are slower because they compile to intermediate bytecode or are all the way interpreted from code (like I think it is the case for Python). Java is compiled to bytecode that is interpreted by a JVM (Java Virtual Machine) which is itself written in C/C++ and compiled to direct system calls.

It is certain that most APIs on most operating-systems are written in C or C++. But things don't "pass through C". Things are compiled to binary which doesn't care about the high level language you are using. You could be using another language than C or C++ and it could be faster once compiled. It could be higher level and take more time to compile but still be faster once compiled.

C doesn't contain the system calls. C isn't much broader than most other languages out there. The difference is that it is compiled before execution so its hardware accesses can be compiled to a bunch of `syscall` instructions with some movs to put the right arguments into the registers.

The fact that the os API is written in C/C++ doesn't make the language more broad. For example, on Windows, the API is a set of DLLs. The header associated with a DLL can be included in a C/C++ program that will allow the use of the functions within the DLL. The DLL is then linked against and the linker resolves that, to reach a certain function, the program needs to jump at that certain address. It is mostly done just before runtime by the dynamic linker. The function itself (in the API), is doing syscalls and it is already compiled but the symbols of the functions are kept along with their positions within the code.

This doesn't augment the language itself but it simply uses the current implementation of the language to its full potential by exposing some complex APIs to the language. I think it could not do that with Java or Python because they are most often not compiled. It makes it more complex to expose low level APIs to a language that isn't compiled and that doesn't understand things like linking and system calls.

I don't think the fact there isn't much more system calls with time has much to do with the API. The API is a set of functions the os exposes to drive hardware or do some special stuff that aren't included in the language by default. The syscalls in the meantime are used by the API functions to call the kernel to do some work. API and syscall isn't the same. The syscall numbers don't need to move much because there isn't the need to add much more of them.

This is often understood once you start to get a grasp of the virtual-filesystem present on most modern operating-systems. The virtual-filesystem will present most devices as files to the upper layer of the os. To drive most devices, the only thing you need is read, write and the general ioctl call. You don't need one system call per device. This isn't a matter of reducing the amount of possible combinations. It is a matter of supporting all devices by exposing one common system call that will include support for all devices of a certain type.

The API in itself, is simply there so that the compiler knows what numbers in what registers should be paired with what syscall to have a certain effect on the computer.

---
Tags: computer-architecture, operating-systems, history, c
---


# Question
Title: If a process needs more RAM, does the Page size simply get bigger or does it get a new page?
Let's say I have a Operating System with 4KB page size, but I need to allocate 8kb of memory for all the variables. Does the Process get new page (second one) or does the current page table simply get bigger?

# Answer
Some architectures support multiple page sizes. For example x86 supports 4kB, 2MB (512\*4kB) and 1GB (512\*2MB) because of its hierarchical page table design. MIPS supports any power of two within a certain range, because of its software TLB design.

An operating system *should* allocate the largest page that it can - if the size and alignment permit. If an x86 OS notices that a whole group of 512 4kB pages are all identical refer to consecutive physical addresses, it may combine them into a 2MB page. It may even rearrange pages in physical memory to enable this to happen. The advantage of using larger pages is that it reduces cache pressure on the TLB, which leads to faster address translation on average, and that less memory is needed to store the page tables. The disadvantage is that virtual memory cannot operate in a fine-grained way, since the whole 2MB has to be swapped out, or split up into small pages again.

Typically, the smallest page size (or a reasonable page size) is used as "the" page size, and then larger pages are created as an optimization when possible. So even a MIPS OS might prefer to treat the 8kB process memory as two 4kB pages. Treating large pages as anything other than an optimization is a non-trivial design challenge.
> 2 votes

# Answer
It gets a new page.

The page size is an operating system constant, and therefore - will not change. The page size determines how "big" are individual chunks of memory.

So, for example, if your page size is 4K, and your program needs 5K bytes, then your operating system will have to allocate at least two pages for your program - one for the first 4K bytes, and another for the last 1K remaining bytes that you use.
> 1 votes

---
Tags: computer-architecture, operating-systems, memory-management, cpu, virtual-memory
---


# Question
Title: Comparing the entropy of a painting to a photograph
This is a quote from the book, "The Three-Body Problem" (page 112 in the paperback):

> He remembered taking a class in information theory as a third-year student in college. The professor had put up two pictures: One was the famous Song Dynasty painting Along the River During the Qinming Festival , full of fine, rich details; the other was a photograph of the sky on a sunny day, the deep blue expanse broken only by a wisp of cloud that one couldn't even be sure was there. The professor asked the class which picture contained more information. The answer was that the photograph's information content - its entropy - exceeded the painting's by one or two orders of magnitude.

The painting (link in quote, source is Famous Chinese Paintings) is in fact, very large - 10,671x500, or 5,335,500 pixels, as 21MB uncompressed PNG. No idea what size the photograph is...

So my question is, is the professor's statement correct - is the information-content likely two orders of magnitude larger in the photograph?

Programmer here, not a ~~physicist~~ computer-scientist, but my (limited) understand of entropy, is that it's a measure, not just of information, but *unpredictable* information. That is, if the picture were all exactly one shade of blue, it's entropy, or "information content", would be very low. And one way of measuring information content is *compressibility* (as a file, not a gas :) .

Given a file of slightly-varying blues (and some white clouds), my intuition is that it would be very compressible (some algorithms more than others, granted).

Would that reduce the "entropy" in the photograph, to something closer than the painting? Or would it still be two orders of magnitude higher?

# Answer
> 1 votes
The images in Does a simple photograph contain more information than a complex painting? - Signal Processing Stack Exchange aren't the originals, they have been processed by imgur, are .png files, and are only 762×633 pixels in size.

Answering based on that information is difficult, but even so, if one takes a section of the blue sky and zooms in on it one can see many patterns of many different colours, not only blue tones. The colour of any specific pixel isn't very predictive of that of its neighbours.

The painting has only a few different colours, and many regular patterns. It has many pixels with identically coloured neighbours. (Each brushstroke would cover a large number of pixels with the exact same colour of paint.)

So yes, without knowledge of what is significant, it's not unreasonable to conclude that the blue sky contains far more information. And this would have been even more so for the original high resolution photograph.

# Answer
> 0 votes
It sounds debatable to me. I could imagine a sense in which the quote might be correct, and another sense in which the quote might be considered incorrect.

One perspective would be: how many bits does it take to compress the image, using (perfect, ideal) lossless compression. Then I'm not sure how that would turn out, but it's possible that the compressed photograph would be larger (e.g., due to noise in the LSBs of the pixel intensities and the larger number of pixels). Modern cameras may have up to 60M pixels, compared to the 21M pixels in the painting, so it's possible that the compressed photograph might be larger than the compressed painting. So, in that sense, it's possible that the photograph might be said to have more information. (Of course, much of that information might be noise in the least significant bits of the pixels of the photograph, which isn't information that humans are likely to care about very much, but from a pedantic perspective, still counts as information.)

Another perspective would be: how many bits does it take to compress the image, using lossy compression, to some quality level. Then I would expect that the compressed image of the painting would absolutely be larger (after compression) than the compressed photograph, so in that sense, the painting can be said to have more information. (The discrepancy between lossless compression vs lossy compression is because lossy compression is likely to remove a lot of information that isn't perceptually important to humans.)

The distinction between the two perspectives amounts to whether we consider the pixel intensity as a discrete value (in which case entropy is usually considered to represent how many bits it would take to communicate those values exactly) or as a continuous value (in which case entropy is usually considered to represent how many bits it would take to communicate those values up to some acceptable amount of distortion/error). At a technical level, you can compare the definition of entropy for a discrete random variable, $H(X) = -\sum\_x p(x) \log p(x)$, with the definition of entropy for a continuous random variable, $H(X) = - \int\_x f(x) \log f(x) \\; \text{d} x$ (more precisely we should compare to the rate from rate-distortion theory, but this can be approximated by the continuous entropy minus a constant that depends on the amount of distortion that can be tolerated). Both are called "entropy", even though they are slightly different, and both are considered a measure of the amount of information present, even though they are measured slightly differently.

Overall, if I were sitting in the audience, I wouldn't be too impressed just from that description alone, and I might suspect that the professor is trying to make a point that might be true but only in a limited, technical way; or I would suspect the professor is trying to be deliberately provocative (even if possibly slightly misleading) to get everyone's intention, and I'd reserve judgement until I saw where the professor is about to go with this. But that's just me.

From a pedantic perspective, the professor was wrong to talk about the entropy of a single image, as that is not well-defined. From a mathematical perspective, information is only defined as the amount of entropy in a random variable. So, you can meaningfully talk about the entropy in a random process, not in a single sample from that process. Mathematics provides a well-defined notion of entropy, which we often use as our way of measuring information. "Information", as a word, is ambiguous. If the professor was using the word "information" in the mathematically precise sense of entropy, then the professor was incorrect to speak about the information of a single image. Alternatively, sometimes we use the word "information" in a fuzzy sense that has no precise mathematical definition. Then it's not necessarily wrong to talk about the information in a single image, it is just not clear exactly what the speaker means by that, and it is not clear whether it is meaningful to talk about the information in a single piece of data (e.g., a single image). In that case, I think a student who wanted to be pedantic would be within their rights to ask the professor to be precise about exactly what they mean by "information content". However, I read the quote as implying that by "information", the professor actually means "entropy", and in that case, the professor's statements were problematic. (See also https://i.stack.imgur.com/ooy9J.gif and How best to statistically verify random numbers?)

---
Tags: entropy
---


# Question
Title: Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?
This is probably a computer science history question.

Is there an algorithm which was originally invented to solve a contrived problem but later found practical use?

# Answer
> 2 votes
The Ternary Golay Code has parameters $\[n,k,d\]\_3=\[11,6,5\]\_3$ and thus is a linear code over $\mathbb{Z}\_3=\\{0,1,2\\}$ with $3^6=729$ codewords. It is *perfect* so that all the Hamming spheres of radius $2$ around codewords fill the whole space $\\{0,1,2\\}^{11}$ with no gaps left over. This means that the code has covering radius $2,$ any ternary string is at most Hamming distance 2 from a codeword.

This code was discovered by a Finnish football (soccer) enthusiast, which gives one a scheme of playing 729 guesses of 11 football matches (1 denotes home win, 0 denotes a draw and 2 denotes an away win) and being guaranteed to guess at least $11-2=9$ matches correctly.

https://www.wikiwand.com/en/Ternary\_Golay\_code#History\_and\_Applications

The code was also discovered by Marcel Golay 2 years later, and independently. It has beautiful mathematical structure. Unlike the related binary perfect Golay code which had direct applications to data quantization, as well as connections to Leech lattice and other structures, the alphabet of size 3 is not really practical for traditional computation.

However, recently, the ternary Golay code was applied to fault tolerant quantum computation via a method known as magic state distillation. See the paper https://arxiv.org/abs/2003.02717

---
Tags: algorithms, history
---


title: Float number to binary

text:
# Question
Title: Float number to binary
I would like to convert 0,347 and 0,9828 to binary, how can I do that?

I know that sucessive multiplication by 2 can do this, but this method seems very painful and even ineffective since the size of count.

This is for a question, and I think that sucessive multiplication is needed. But, in 0,347, I did more than 20 multiplication and did not reach result. Is this normal?

# Answer
If I understand your question correctly, you want to determine the binary representation of a floating-point number by hand. I assume you are talking about the IEEE 754 floating-point format, since this is the most common format.

You can indeed do this by successively multiplying with 2. However, just multiplying does not result in anything useful, you should also subtract one (1) every time the intermediate result is greater than or equal to 1. To understand this, you must understand how floating-point numbers are stored. This is explained pretty well on Wikipedia (and probably many other sources), including the algorithm you mean (see here).

To do this by hand is quite painful indeed. It's normal that you have to do more than 20 multiplications. You first need a few multiplications to normalize the number and determine the exponent (i.e. scale the number such that it has the form `1.xxxxx * 2^exponent`). After that, each multiplication yields exactly one bit of the mantissa. A single-precision floating-point number has a 23-bit mantissa, so to convert the number 0.347 to single-precision floating-point, you need to do 25 multiplications. A double-precision floating-point has a 52-bit mantissa, so you'll need 54 multiplications!

NB: For sake of simplicity, I did not take into account numbers larger than 1, negative numbers, special numbers (such as NaN, +/- infinity, denormal numbers, etc.) and other aspects such as rounding. These cases seem to be out of the scope of your question.
> 1 votes

# Answer
First you look at the position of the decimal sign and a possible exponent, and you find that the result you want is “347” divided by $10^3$ and “9828” divided by $10^4$.

You convert “347” and “9828” to floating point - there is no multiplication by 2 involved, but multiplication by 10. You probably get the power of 10 by looking up a table.

Doing this with high precision is harder.
> 0 votes

# Answer
Successive doublings is a good way, you can virtually do it mentally (double every digit modulo $10$, and if the next is $5$ or more, add a carry).

$$0.347\\0.694\\1.388\\2.776\\5.552\\11.104\\22.208\\44.416\\88.832\\177.664\\\cdots$$

So far, $0.347\approx\dfrac{177}{512}=0.010110001$. Straight multiplication by a large power of $2$ is also possible, but not necessarily easier/faster.

As you noticed, the process will never stop. This is because no power of $10$ is also a power of $2$, so

$$\frac n{10^k}2^l$$ is never an integer, and the given number is unlimited periodic fractional in base $2$. (Some more digits: $0.0101100011010100111111011111001110110110010001011010000111001010110000001000001100010010011011101001011110001101010011111101111\cdots$)

---

You can do faster with a table of digits over powers of $10$:

$$0.1\to0.00011001100\cdots\\0.2\to0.00110011001\cdots\\0.3\to0.01001100110\cdots\\\cdots\\0.01\to0.00000010100\cdots\\0.02\to0.00000101000\cdots\\\cdots$$

Yet another option is to do with a table of inverse powers of $10$ and perform a binary multiply:

$$0.347=347\cdot10^{-3}=101011011\times0.000000000100000110001\cdots$$
> 0 votes

---
Tags: floating-point, binary
---