# Question
Title: What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$
By unrolling the recursion, \begin{equation\*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^{\frac{1}{8}})+3) + 6 = T(n^{\frac{1}{8}}) +9 \\ \end{split} \end{equation\*}

Claim: $T(n) = T(n^{\frac{1}{2^k}}) + 3 \cdot k$

Base Case: $k=1$ \begin{equation\*} \begin{split} T(n) &= T(n^{\frac{1}{2^1}}) + 3 \cdot 1 \\ T(n) &= T(\sqrt{n}) + 3 \end{split} \end{equation\*}

Inductive Hypothesis: Assume that k=i is true, \begin{equation\*} \begin{split} T(n) &= T(n^{\frac{1}{2^i}}) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^i+1}}+3) + 3 \cdot i \\ &= (T(n^{\frac{1}{2^i+1}}) + 3 \cdot (i +1) \\ \end{split} \end{equation\*}

These are my questions...

1. I am unsure if my base case is correct
2. I am also not sure how to proceed (what value can I substitute in to get a closed form)

Any help would be appreciated!

# Answer
> 1 votes
Where are you using that T(n) = c for n \<= 10? Your formula is wrong when the argument is less than 10. K = 1 is not the base case. N \<= 10 is the base case.

Clearly T(n) = c for n \<= 10, T(n) = c+3 if 10 \< n \<= 100, T(n) = c+6 if 100 \< n \<= 10,000, T(n) = c+9 if 10,000 \< n \<= 100,000,000 etc.

Let f(n) = log\_10 (max (n, 10)) so for the four cases above we have f(n) = 1, 1 \< f(n) \<= 2, 2 \< f(n) \<= 4, 4 \< f(n) \<= 8 etc.

Let g(n) = ceil(log\_2(f(n))), then g(n) = 0, 1, 2, 3 etc, and T(n) = c + 3 g(n).

# Answer
> 0 votes
Assume the following: $T(n) \leq c\log\_2(\log\_2(n)), n \> 10$ and $T(4) = c$ as a base case (because $4^2 \> 10$.)

Now we can proceed by induction:
**Base case:** $$c\log\_2(\log\_2(4)) = c\log\_2(2) = c \geq T(4)$$ **General case:**
We know $T(\sqrt{n}) \leq c\log\_2(\log\_2(\sqrt{n}))$ (induction hypo.). Hence:

$$T(n) = T(\sqrt{n})+3 \leq c\log\_2(\log\_2(\sqrt{n})) + 3$$

We can rewrite the right term: $$c\log\_2(\log\_2(\sqrt{n})) + 3 = c\log\_2\left(\frac 12 \log\_2(n)\right) +3 = c\log\_2(\log\_2(n)) - c + 3$$ Let $c = 3$. This results in: $$T(n) = T(\sqrt{n})+3 \leq 3\log\_2(\log\_2(n)) - 3 + 3 = 3\log\_2(\log\_2(n))$$ Hence: $T(n) \leq 3\log\_2(\log\_2(n))$.

---

You can also show $T(n) \geq 3\log\_2(\log\_2(n))$ in the same manner. Thus $T(n)\in O(\log \log(n))$. I hope this helps.

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Rice's Theorem for Turing machine with fixed output
So I was supposed to prove with the help of Rice's Theorem whether the language: $L\_{5} = \\{w \in \\{0,1\\}^{\*}|\forall x \in \\{0,1\\}^{\*}, M\_{w}(w) =x\\}$ is decidable.

First of all: I don't understand, why we can use Rice's Theorem in the first place: If I would chose two Turingmachines $M\_{w}$ and $M\_{w'}$ with $w \neq w'$ then I would get $M\_{w}(w) = M\_{w'}(w) = x$. But this would lead to $w'$ not being in $L\_{5}$ and $w \in L\_{5}$. Or am I misunderstanding something?

Second: The solution says, that the Language $L\_{5}$ is decidable as $L\_{5} = \emptyset$ because the output is clearly determined with a fixed input. But why is that so? I thought that $L\_{5}$ is not empty because there are TM which output x on their own input and there are some which do not.

# Answer
> 1 votes
A word $w$ belongs to $L\_5$ if for all $x \in \\{0,1\\}^\*$ it is the case that $M\_w(w) = x$. In particular, if $w \in L\_5$ then $M\_w(w) = 0$ and $M\_w(w) = 1$, which can't both be true. So no word belongs to $L\_5$.

---
Tags: turing-machines, decision-problem, rice-theorem
---


title: DFA for every run of a's=2 or 3

text:
# Question
Title: DFA for every run of a's=2 or 3
I am trying to create a dfa for L={w: every run of a's has length either two or three}

this is my attempt at the solution..i feel like I am missing something..?

# Answer
> 0 votes
Yes, there is something wrong. In your comment you stated that you feel that it should be accepting $baabbabbab$. You are wrong about this.

The language you want is $L=\\{w \in \\{a,b\\}^\* | w = ((aa|aaa|\epsilon)b)^\*(aa|aaa|\epsilon)\\}$

Clearly, $baabbabbab \not\in L$.

Regarding your DFA, I have some excellent news but you'll quiesce in your pants about it. In fact, your DFA accepts any string that ends in a run of a's of length 2 or 3 and contains no runs of length 4 i.e. $L(\<your\ DFA\>) = \\{w \in \\{a,b\\}^\* | w= (ab|aab|aaab|b)^\*(aa|aaa)\\}$.

**HINT**

State $q\_1$ in your proposed DFA, on $b$, should go to a halting state.

# Answer
> 0 votes
I came across this question in Peter Linz' *Introduction to Formal Languages and Automata*. There it is mentioned that "a run in a string is a substring of length atleast 2". Hence a single $a$ is not a *run of* $a$. Moreover, *every run of $a$'s is either of length two or three* can be read as "if there exists a run of $a$'s , then it should be either of length two or three". Hence 0 or 1 $a$ should also be accepted. Your DFA is right except for the fact that $q\_0$ and $q\_1$ will also be accepting states. $baabbabbab \in L$ because it has run of $a$'s of length two.

# Answer
> 0 votes
5 states: E = Error detected, and S0 to S3 = No error detected, input ends in 0, 1, 2, or 3 a’s. S0, S2 and S3 are accepting.

An a moves from S0, S1, S2 to S1, S2, S3, and from S3 or E To E. b moves from S0, S2 or S3 to S0, and from S1 or E to E.

Close to yours, but S0 is accepting, and b in state S1 goes to the error state.

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: Proof of the undecidability of compiler code optimization
While reading *Compilers* by *Alfred Aho*, I came across this statement:

> The problem of generating the optimal target code from a source program is undecidable in general.

The Wikipedia entry on optimizing compilers reiterates the same without a proof.

Here's my question: Is there a proof (formal or informal) of why this statement is true? If so, please provide it.

# Answer
Optimized program must have the same behavior as the original program. Consider the following program:

```
int main() {
    f();
    g();
}

```

, where it's guaranteed that $f$ is pure function. The only question is: does it finish its execution? If it does, then we can replace `main()`'s body with `g()`. Otherwise, we should replace it with an infinite loop. Unfortunately, verifying whether `f()` finishes its execution is undecidable.

Another example is the program with body `print(f(42))`, where `f` is pure. The optimal program would just replace `f(42)` with its value. However, there is no algorithm that does this. We may try to compute it in compile-time, but it may never finish.

Another example (now without infinite loops). Assume that your program defines a context-free grammar and $f(x)$ checks whether string $x$ belongs to the language defined by this grammar (for any CFG we can build such $f$ automatically). Then if $f$ is a constant "true", then

```
if (f(x)) {
    g()
}

```

can be optimized to `g()`. Unfortunately, checking that grammar accepts all strings is called a universality problem and is known to be undecidable.
> 42 votes

# Answer
For most interesting optimisations, I think this is implied by Rice's theorem. For real numbers, Richardson's theorem is also relevant here.
> 9 votes

# Answer
With some programming languages and computation models, you could even say that **optimizing programs is the same as running them** — just with a subset of computation rules. Then, if you allow enough optimizations to happen, it is clear that optimization faces the same non-termination problems as running programs.

Let me elaborate on my claim by providing a **concrete example of a made-up language and its computational semantics**.

Consider the following source code of a very **primitive imperative language** \[1\].

```
i := 0;;

IF (i == 0) do:
  SKIP
;;

WHILE true do:
  i := i + (1 + 1) ;;
  i := i + 3

```

I hope the language grammar becomes clear from the above sample. It supports statements such as assignments `variable name := ...`, if conditions `IF ... do:`, while loops `WHILE ... do:`), and concatenated statements `... ;; ...`. Moreoever, it allows scalar expressions such as boolean conditions `... == ...`, `true`, `false`, and simple arithmetic like `... + 3` within some of the previous statements.

## Evaluation by Rules

Let us now invent a computational semantics for running such programs. Concretely, we will do so in terms of **small-step semantics**, i.e. a binary evaluation relation between contextual statements: we write `p,Γ ⤳ p',Γ'` if program `p` with variable states `Γ` transitions (computes, evaluates) to program `p'` with variable states `Γ'`. Then, the interpreter for our language works as follows: upon a program `p`, it picks the default start state for variables `Γ_ini` and tries reducing it as long as possible:

> `p,Γ_ini ⤳ p',Γ' ⤳ p'',Γ'' ⤳ ... ⤳ RET`

Hopefully, this ends with a special program `RET` denoting termination. But it may very well happen that running does not terminate at all. For instance, our sample program invokes such non-terminating behavior — at least with the (intuitive) semantics we give next.

We give the following rules on statements, where `S`, `S'`, `T` are meta variables for statements, `E`, `E'` are meta variables for expressions, and `Γ` a meta variable for contexts, and all of them are implicitly all-quantified.

* if `S,Γ ⤳ S',Γ'`, then `(S ;; T),Γ ⤳ (S' ;; T),Γ'`
* always `(SKIP ;; S),Γ ⤳ S,Γ`
* if `E,Γ ⇝ E'`, then `(X := E),Γ ⤳ (X := E'),Γ`
* if `E,Γ ⇝ E'`, then `(IF E do S),Γ ⤳ (IF E' do: S),Γ`
* always `(IF true do: S),Γ ⤳ S,Γ`
* always `(IF false do: S),Γ ⤳ SKIP,Γ`
* always `(WHILE E do: S),Γ ⤳ (IF E do: S ;; WHILE E do: S),Γ`

where ⇝ is a similar small-step relation on expressions that I omit here. There, `E,Γ ⇝ E'` means that expression `E` in context `Γ` transitions to expression `E'`. Note that since expressins cannot change variable state in our language, we omit the context `Γ` on the right-hand side of ⇝.

## Optimization by Restricted Evaluation

How can we now formulate optimization rules for our language? For instance, our intuition demands that in the program above the statement `IF (i == 0) do: SKIP` optimize to nothing. It turns out we can achieve this with the very same tool of small-step semantics. For our purposes, we give the following set of optimization rules for the optimization relation ⤅:

* if `S,Γ ⤅ S',Γ'`, then `(S ;; T),Γ ⤳ (S' ;; T),Γ'`
* if *forall* Δ, `T,Δ ⤅ T',Δ`, then `(S ;; T),Γ ⤳ (S ;; T'),Γ` (optimization does not need to be sequential as evaluation was)
* always `(IF E do: SKIP),Γ ⤅ SKIP,Γ`
* always `(SKIP ;; E),Γ ⤅ E,Γ`

With them, we see that our program above indeed first optimizes to `i := 0 ;; (SKIP ;; WHILE true do: ...)` (where I annotated parentheses explicitly) and then to `i := 0 ;; (WHILE true do: ...)` as desired.

Note that in contrast to the evaluation rules, here the exhaustive application of the optimization rules above does terminate — at least I hope this can be proven via induction. But this is just a consequence of our yet naive way of optimization. If we optimized many things further, we would also run into possibly non-terminating territory.

### Correctness of Optimization

Importantly, **optimization rules need to be derivable from the evaluation rules** for *sane* programs, i.e. be a *subset* in some sense. Otherwise, our optimizations would be wrong. Regarding sanity, for instance our third optimization rule can only be derived *if* we assume that for `E` occurring in the if condition, we always have either `E,Γ ⇝ ... ⇝ true` or `E,Γ ⇝ ... ⇝ false`. Moreover, our second rule is only derivable if we assume that the `S` contained therein never gets stuck. In richer languages, `S` may even throw an exception.

However, both previous assumptions do usually hold if our language is typed, our type theory ensures soundness ("well-typed programs never get stuck/throw exceptions"), and the input program for optimization is actually well-typed. Indeed, the definitions of sanity of many programming language optimizers usually include well-typedness as a necessary condition. The C language is a prime example for a case where sanity of programs encompasses much more than well-typedness alone: namely, many optimizations by compilers are only correct *if* the input programs do not exhibit undefined behavior.

---

\[1\]: the language and its semantics are heavily inspired from the language *Imp* presented in the *Software Foundations* series, *Volume 1: Logical Foundations* by Pierce, de Amorim, Casinghino, Gaboardi, Greenberg, Hriţcu, Sjöberg, Yorgey et al.
> 3 votes

# Answer
It’s quite easy to write a program that will either print the smallest even N \>= 4 which is not the sum of two primes, or run forever.

Run it through the optimiser. The optimised output would be either a program printing some long string of digits, or an empty loop. So that’s one hard mathematical problem your optimiser would have to crack.
> 2 votes

# Answer
Like many undecidability results about program analysis, this is a consequence of Rice's theorem.

Consider the function $g := x \mapsto \mathsf{if} \\; f(x) \\; \mathsf{then} \\; 0 \\; \mathsf{else} \\; x$ where $C$ may contain variables. An optimal optimizer must optimize calls to this function to $0$ if $f(x)$ is true for every $x$.

The property “this function evaluates to $\mathsf{true}$ regardless of the value of its argument” is a non-trivial property of partial functions, therefore in accordance to Rice's theorem there is no algorithm to decide it.

Taking the contraposite, for any correct optimizer $T$, there exists a function $f\_T$ which is always true, but such that $T$ does not realize that $f\_T$ is always true and therefore does not optimize calls to $g$ to $0$.

The one part of this proof that I didn't model formally above is “an optimal optimizer must optimize …”: I didn't define what it means for an optimizer to be optimal. This requires a cost model over the programming language. One possible cost model is that every function call costs $1$. In this model, replacing $g(x)$ by $0$ decreases the cost by at least 1 so an optimal optimizer must do it.

This example works with any cost model where a function application has a nonzero cost and the cost of evaluating a program is larger or equal than the cost of evaluating any subprogram that gets evaluated as part of the evaluation of the larger program. For example, any “sane” small-step semantics is of this type: calling a function is a beta reduction, and the cost of evaluating a program is the number of instances of reduction rules that get applied.
> 2 votes

---
Tags: undecidability, compilers
---


# Question
Title: Uniform generation of random bipartite bi-regular graphs?
I want an algorithm that takes the following

**Input:** $M,N,k,d$ positive integers such that $kM = dN$.

and produces the following

**Output:** Random bipartite graph, with $M$ vertices all of degree $k$ on one partition, and $N$ vertices all of degree $d$ on the other partition. No loops allowed. The output should be uniformly distributed among all possible graphs.

Does an algorithm like this exist? If so please provide a reference.

# Answer
The problem of generating random $d$-regular graphs uniformly at random has been extensively studied. Some of the proposed algorithms are quite sophisticated. In general, the problem becomes more difficult as $d$ grows as a function of $n$. To the best of my knowledge, the problem is still open for $d = \omega\left(\sqrt{n}\right)$.

However, if one assumes that $d$ is a constant, then there is a simple and efficient algorithm called the **configuration model**:

https://en.wikipedia.org/wiki/Configuration\_model

It can be easily adapted to the case of biregular graphs with $M$ vertices of degree $k$ on the left side, and $N$ vertices of degree $d$ on the right side. Of course, for this to be possible at all we need $Mk=Nd$.

The algorithm is as follows:

* Assign each vertex on the left side $k$ \`\`half-edges", and each vertex on the right $d$ half-edges.
* Choose a uniformly random perfect matching of size $Mk$ matching all of the half-edges on the left side to the half-edges on the right side.
* This tells you which vertices to connect to which, but there may be double edges. Repeat the above procedure until there are no double edges.

It is pretty easy to see that the resulting distribution is uniform by counting the number of perfect matching that can yield a given graph. It is harder to analyze the probability that there are no double edges, which is critical if we want to bound the expected runtime. However, it turns out that for constant $k$ and $d$, the probability that there are no double edges is a constant independent of $n$, and so we only need to repeat the algorithm $O(1)$ times.
> 2 votes

# Answer
Because it seems nobody will answer this question any time soon, I will give you what I tried for the same problem. I guess my answer lacks a formal proof but it successfully solved my case. The following python style pseudocode generate `edges` which contains tuples of vertices.

```
# Assuming there are M a_nodes and N b_nodes
cur_b_nodes = set(range(N))  # b nodes with the lowest degrees
next_b_nodes = set()  # b nodes with the second lowset degrees

edges = []
for a_node in range(M):
    for _ in range(k):
        if not cur_b_nodes:
            cur_b_nodes = next_b_nodes
            next_b_nodes = set()
        b_node = sample(cur_out_nodes, 1)[0]  # Random sampling
        cur_b_nodes.remove(out_node)
        next_b_nodes.add(out_node)

        edges.append((a_node, b_node))

```

I think this is an approach with the lowest time complexity. Any comments will be welcome.
> 0 votes

---
Tags: algorithms, graphs, randomness, sampling
---


# Question
Title: Solving T(n) = 3T(n/3)+n/2 using master method
I thought I understood the Master Method quite well till I saw this question

$T(n) = 3T(\frac{n}{3})+\frac{n}{2}$

My approach: $a = 3 ; b=3$ and $f(n) = \frac{n}{2}$

$n^{\log\_b{a}}$ = $n^{log\_3{3}} = n$

This looked like a classic solution of master method using case 1.

But since case 1 implies $f(n) = n^{\log\_3{3} - ε}$ and I cannot find any way that ε can be represented, I understand that case 1 is not the way.

However the solution says that this is solvable by case 2 of the master method and the solution is $T(n) = \theta(n^{log\_3{3}} \log^{ n}) $

Case 2 of the master method states that if $f(n) = n^{log\_b{a}} \log^{k}{ n}$ then $T(n) = \theta(n^{log\_b{a}} \log^{k+1}{ n}) $

Can someone explain how this is solved using case 2 of the master method and why this fits under case 2?

# Answer
> 0 votes
In a recurrence of the form:

$$T(n)=aT(n/b)+O(n^d)$$

Case 2 of the master theorem applies when we do **equal work at every level** of the recursion tree. This happens when the amount of work done at the root - $O(n^d)$ - is equal to the amount of work done at the leaves. In other words, when the *rate of subproblem proliferation (RSP)* is equal to the *rate of work shrinkage (RWS)* per subproblem:

* The RSP is $a=3$ in your recurrence. This means that, as we move down the tree, we have more subproblems to solve (which is bad news). In particular, at level $j$, we have $3^j$ subproblems.
* The RWS is $b^d=3^1=3$ in your recurrence. This means that, as we move down the tree, each subproblem does less and less work (which is good news). In particular, at level $j$, each subproblem accounts for $O(n/3^j)$ of the total amount of work.

Since $a=b^d$, the RSP and the RWS cancel out. Thus, it is easy to predict what the running time will be. Since we have a logarithmic number of levels - $log(n)$ - and the total amount of work is the same at every level - $O(n)$ - then the running time is $O(n \cdot log(n))$.

# Answer
> 1 votes
While applying master's theorem all you have to do is compare which of $f(n)$ or $(n^{\log\_b{a}})$ is asymptotically greater. The greater of the two functions determines the solution to the recurrence. There are only possible outcomes for this comparison:
\[1\] $(n^{\log\_b{a}})$ is asymptotically greater than $f(n)$
\[2\] Both are asymptotically equal
\[3\] $f(n)$ is asymptotically greater than $(n^{\log\_b{a}})$

Yours falls in case 2.

# Answer
> 1 votes
In the recurrence relation $T(n)=3T(\frac{n}{3})+\frac{n}{2}$

The last term $\frac{n}{2}$ can be written as $n\cdot\frac{1}{2}$ aka $n\cdot c$ cause $\frac{1}{2}$ is a constant.

From Masters Theorem:

$n^{\log\_{3}(3)} =1$. So, $n^1= f(n)$

This resembles case 2 of masters theorem $T(n) = \theta(n^{\log\_{b}{a}}\log\_{2}{n} )$

thus, $T(n) = \theta(n\log\_{}{n} )$

# Answer
> 0 votes
Case 2 of masters theorem says that:

**if** **`f(n) = θ(n^(logb a))`**, then **`T(n) = θ(n^(logb a)logn)`**.

`^` means power.

In term **`log n`** of **`θ(n^(logb a)logn)`**, the base does not matter.

So going by your way, you are right in saying that

**`a = 3; b = 3 and f(n) = n^2`**

```
f(n) = n/2

f(n) <= 2*(n/2) for all n > 1, this means that:

f(n) = O(n)

```

Also

```
f(n) >= 0.8*(n/2) for all n > 1, this means that:

f(n) = omega(n)

```

Hence **`f(n) = θ(n)`**

Therefore, the solution is **`T(n) = θ(nlogn)`**

# Answer
> 0 votes
This question can be solved by Master Theorem:
In a recursion form :

where a\>=1, b\>1, k \>=0 and p is a real number, then:

1. if a \> bk, then
2. if a = bk

```
   a.) if p >-1, then

```

```
       b.) if p = -1, then

```

```
       c.) if p < -1, then

```

3. if a \< bk
a.) if p \>=0, then

b.) if p\<0, then T(n) = O(nk)

So, the above equation

```
   T(n) = 3T(n/3) + n/3

a = 3, b = 3, k =1, p =0

```

so it fall into 2.a case, where a = bk
So answer will be

```
O(n⋅log(n))

```

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Why are sensors transducers when analogue-to-digital-converters (ADC) do the actual conversion?
As sensors only sense continuous quantities whereas an ADC is a device which actually converts one form of input to another.

# Answer
A sensor is a kind of transducer that converts physical quantity like temp or pressure into electrical signal (voltage, current or charge). ADC converts the electrical signal generated from sensors to an equivalent binary code, that can be then processed by a logic processor (microcontroller, DSP, FPGA ...).
> 1 votes

---
Tags: transducers
---


title: How is CPU different from GPU?

text:
# Question
Title: How is CPU different from GPU?
A central processing unit offers to handle various operations like calculating, watching movies, making presentation etc. While a graphics processing unit is majorly used for the purpose of video rendering or playing of high-quality graphical games. I found the above statement on a website listing the differences between CPU and GPU. What I am not able to understand is how making PPTs,listening to songs from graphics in terms of mathematical operations that the brain of computer applies! All these operations handled in terms of bits,so why treat them differently? Also why cant we have a PC completely based on GPUs if they so good at executing parallel instructions and handling large amount of bits for graphics?Though i have heard about GPGPUs but why cant traditional GPUs be used?

# Answer
GPUs are highly specialized: they are *very* good at a *very small number* of things, but they are extremely bad at everything else.

CPUs are general: they are mediocre at *everything*.

GPUs are good at applying *the same* operation out of a *small number* of potential operations, and in particular, the same *very simple* operation to *a lot of identical* things. E.g. when you want to brighten up a picture, you need to apply the same extremely simple multiplication to all 3 colors of all 10million pixels of a 4K screen.

A CPU is almost exactly the opposite: the number of potential different operations is not small, it is almost endless. (Word processing, spreadsheet crunching, compiling, web browsing, emailing, controlling a robot, driving a car, …) The operations aren't simple, they are extremely complex. And you don't apply the same operation to a huge number of identical things, you apply a different operation to a number of different things.

GPGPU (General-purpose GPU) is a misnomer, really. They are not "general purpose" in the same sense that a general purpose CPU is. What is meant by that, really, is that they can be used for purposes other than creating pictures *that still have the same characteristics as graphics*. For example, modern graphics cards can do particle simulations for generating realistic rain or explosions. What "GPGPU" means is that you can use those same particle simulation features without generating a picture from it, and instead, say, generate velocity predictions for the fragments of an exploding asteroid.

But, reading your mail is a very different thing than simulating a billion particles.
> 3 votes

# Answer
The basic architecture of CPU and GPU are different. Modern CPU's consist of a set of cores. Each core has its own a set of registers, a ALU and a control unit with some private cache. In a CPU the number of ALU's (the actual processor) is in 1-100 range. In a GPU number of ALU's are in thousands. The register files are larger and is shared among multiple ALU. A large register file with a set of ALU's(typically in range 32--128) and some additional hardware are known as streaming multiprocessors in a NVIDIA GPU. A GPU has a large number of streaming multiprocessors (can be in 100's). Having a large number of ALU's give the GPU's its extreme compute capability. Only limitation is the computation should have **a certain kind of parallelism**.

GPGPU don't have some hardware component like texture units (which are required for graphics processing but would not be relevant for general computing).
> 2 votes

---
Tags: computer-architecture, cpu, computer-games, computer-graphics
---


# Question
Title: Spanning tree in a graph of intersecting sets
Consider $n$ sets, $X\_i$, each having $n$ elements or fewer, drawn among a set of at most $m \gt n$ elements. In other words $$\forall i \in \[1 \ldots n\],~|X\_i| \le n~\wedge~\left|\bigcup\_{i=1}^n X\_i\right| \le m$$

Consider the complete graph $G$ formed by taking every $X\_i$ as a node, and weighing every edge $(i,j)$ by the cardinal of the symmetric difference $X\_i \triangle X\_j$.

An immediate bound on the weight of the minimal spanning tree is $\mathcal{O}(n^2)$, since each edge is at most $2 n$, but can we refine this to $\mathcal{O}(m)$?

For illustration, consider $2 p$ sets, $p$ of which contain the integers between $1$ and $p$ and $p$ of which contain the integers of between $p+1$ and $2p$. A minimal spanning tree has weight $p$ but a poorly chose tree on this graph would have weight $(p-1)p$. Intuitively, if there are only $m$ values to chose from, the sets can't all be that different from one another.

EDIT: Contributor Dmitry gives a nice counterexample below in which $m$ is nearly but not quite $n^2$.

A counterexample or proof would still be of interest in the case where $m = \mathcal{O}(k n)$. Can the weight of spanning-tree be bound by $\mathcal{O}(f(k) n)$? By $\mathcal{O}(f(k) n \log^c n)$?

# Answer
> 3 votes
Interesting question.

The right intuition should probably be along the guideline that two random subsets of cardinality $n$ drawn from some $cn$ elements for some constant $c$ differ from each other significantly with a probability very close to 1 and, hence, the weight of the minimum spanning tree of the graph $G$ should be $\mathcal\Theta(n^2)$ on average. I cannot prove that guideline is correct, however.

Instead, I will present one series of such examples. More specifically, from some $n$ (that can be arbitrary large), there are $n$ sets, each having $(n-1)/2$ elements drawn from a set of $n$ elements, such that the cardinality of the symmetric difference between any two sets is no less than $(n-1)/2$. So the weight of the minimum spanning tree is no less than $(n-1)^2/2=\mathcal\Theta(n^2)$.

---

Here is the construction, using quadratic residue.

**Example.** Let $n=p$ be an odd prime. Let $X\_0$ be the set of all non-zero quadratic residues of $p$ between 0 and $p-1$ inclusive. In other words, $$X\_0=\\{0\le k\lt p: \left(\frac {k}p\right)=1\\}$$ where $\left(\frac{\cdot}p\right)$ is the Legendre symbol. For $0\le i\lt p$, let $X\_i$ be "$X\_0$ plus $i$", i.e., $$X\_i=\\{0\le k\lt p: \left(\frac {k-i}p\right)=1\\}.$$ Then $|X\_i|=\frac{p-1}2$ for all $i$ and $|X\_i \triangle X\_j|\ge \frac{p-1}2$ for all $i\not=j$.

**Proof**: Since $\left(\frac{\cdot}p\right)$ is either $-1$, $0$, or $1$, we have $1+\left(\frac{\cdot}p\right)\ge0$. Hence, $$\begin{aligned} &\quad\quad \sum\_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &\ge\sum\_{0\le k\lt p\\,\land\\,\left(\frac {k-i}p\right)=1\\,\land\\, \left(\frac {k-j}p\right)=1}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &=\sum\_{0\le k\lt p\\,\land\\,\left(\frac {k-i}p\right)=1\\,\land\\, \left(\frac {k-j}p\right)=1}4\\ &=4\\,|X\_i\cap X\_j| \end{aligned}$$ On the other hand, we have $$\begin{aligned} &\quad\quad \sum\_{0\le k\lt p}\left(1+\left(\frac {k-i}p\right)\right)\left(1+\left(\frac {k-j}p\right)\right)\\ &=\sum\_{0\le k\lt p}\left(1 + \left(\frac {k-i}p\right) + \left(\frac {k-j}p\right)+ \left(\frac {k-i}p\right)\left(\frac {k-j}p\right)\right)\\ &=p + 0 + 0 + \sum\_{0\le k\lt p} \frac {k^2-(i+j)k+ij}p\\ &=p-1 \end{aligned}$$ Since $p\nmid(-(i+j))^2-4ij=(i-j)^2$, the last equality above comes from the case of $p\nmid b^2-4ac$, theorem 1 in the paper *On Certain Sums with Quadratic Expressions Involving the Legendre Symbol*. So we have $|X\_i\cap X\_j|\le \frac{p-1}4.$

Since $|X\_i|=|X\_j|=\frac{p-1}2$, $\ |X\_i \triangle X\_j|=|X\_i|+|X\_j|-2|X\_i\cap X\_j|\ge \frac{p-1}2.$ $\quad\checkmark$

---

For people who appreciate concrete examples, here are the sets when $n=17$, where $|X\_i \triangle X\_j|\ge 8$. $$\begin{aligned} X\_{0}&=\\{\phantom{1}1, \phantom{1}2, \phantom{1}4, \phantom{1}8, \phantom{1}9, 13, 15, 16 \\}\\ X\_{1}&=\\{\phantom{1}2, \phantom{1}3, \phantom{1}5, \phantom{1}9, 10, 14, 16, \phantom{1}0 \\}\\ X\_{2}&=\\{\phantom{1}3, \phantom{1}4, \phantom{1}6, 10, 11, 15, \phantom{1}0, \phantom{1}1 \\}\\ X\_{3}&=\\{\phantom{1}4, \phantom{1}5, \phantom{1}7, 11, 12, 16, \phantom{1}1, \phantom{1}2 \\}\\ X\_{4}&=\\{\phantom{1}5, \phantom{1}6, \phantom{1}8, 12, 13, \phantom{1}0, \phantom{1}2, \phantom{1}3 \\}\\ X\_{5}&=\\{\phantom{1}6, \phantom{1}7, \phantom{1}9, 13, 14, \phantom{1}1, \phantom{1}3, \phantom{1}4 \\}\\ X\_{6}&=\\{\phantom{1}7, \phantom{1}8, 10, 14, 15, \phantom{1}2, \phantom{1}4, \phantom{1}5 \\}\\ X\_{7}&=\\{\phantom{1}8, \phantom{1}9, 11, 15, 16, \phantom{1}3, \phantom{1}5, \phantom{1}6 \\}\\ X\_{8}&=\\{\phantom{1}9, 10, 12, 16, \phantom{1}0, \phantom{1}4, \phantom{1}6, \phantom{1}7 \\}\\ X\_{9}&=\\{10, 11, 13, \phantom{1}0, \phantom{1}1, \phantom{1}5, \phantom{1}7, \phantom{1}8 \\}\\ X\_{10}&=\\{11, 12, 14, \phantom{1}1, \phantom{1}2, \phantom{1}6, \phantom{1}8, \phantom{1}9 \\}\\ X\_{11}&=\\{12, 13, 15, \phantom{1}2, \phantom{1}3, \phantom{1}7, \phantom{1}9, 10 \\}\\ X\_{12}&=\\{13, 14, 16, \phantom{1}3, \phantom{1}4, \phantom{1}8, 10, 11 \\}\\ X\_{13}&=\\{14, 15, \phantom{1}0, \phantom{1}4, \phantom{1}5, \phantom{1}9, 11, 12 \\}\\ X\_{14}&=\\{15, 16, \phantom{1}1, \phantom{1}5, \phantom{1}6, 10, 12, 13 \\}\\ X\_{15}&=\\{16, \phantom{1}0, \phantom{1}2, \phantom{1}6, \phantom{1}7, 11, 13, 14 \\}\\ X\_{16}&=\\{\phantom{1}0, \phantom{1}1, \phantom{1}3, \phantom{1}7, \phantom{1}8, 12, 14, 15 \\}\\ \end{aligned}$$

# Answer
> 2 votes
You can't. Consider the following sets for some $k$, with $m=k^2$ (they both are powers of $2$):

* $\\{1..k\\}$, $\\{k+1..2k\\}$, $\ldots$, $\\{m-k+1..m\\}$
* $\\{1, 3, 5, \ldots, 2k-1\\}$, $\\{2, 4, 6, \ldots, 2k\\}$, $\\{2k+1, 2k+3, \ldots, 4k - 1\\}$, $\\{2k+2, 2k+4, \ldots, 4k\\}$, $\ldots$
* $\\{1, 5, 9, \ldots, 4k - 3\\}$, $\\{2, 6, 10, \ldots, 4k-2\\}$ $\ldots$.

Each symmetric difference is at least $\frac k2$. Each level has $\frac mk$ sets, and there are $1 + \log \frac mk$ levels. Therefore, there are $\frac mk(1 + \log \frac mk)$ sets. Since each set must have cardinality at most the number of sets, we must have $k \le \frac mk (1 + \log \frac mk)$, and it's satisfied when $m = k^2$.

The size of the minimum spanning tree is at least $\frac k 2 \cdot \frac mk (1 + \log \frac mk) = \Omega(m \log m)$.

---
Tags: graphs, sets, minimum-spanning-tree, finite-sets
---


# Question
Title: Is every subset of a decidable set, also decidable?
Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?

I believe it would be true because all the subsets of B should also be decidable making A decidable. I'm not sure if my thought process is right or if there's a easier more intuitive way to explain this.

# Answer
> 14 votes
This is a common misconception: complexity is not a measure of *size*. That is, it's not that "bigger" language are harder. Intuitively, a language becomes harder when it's harder to describe it (TMs being a form of description). For example, as @Yuval Filmus points out in the comments, the language whose description is "everything" is very easy to decide.

Similarly, the converse is not true - that is, smaller languages are not "harder" as well. For example, the language "nothing" is also easily decidable.

So the containment relation does not preserve hardness. Indeed - that's why we use the relatively complicated notion of reductions between languages, rather than showing containment.

So the simple answer to your question is that it's false, and an example, as in the comments, is $\Sigma^\*$, which is decidable, but contains an undecidable language (indeed, every undecidable language).

# Answer
> 2 votes
Definitely not. Just think about that the universal set of input is a decidable language, but there are infinite subsets of it are undecidable...

# Answer
> 0 votes
Its not true.

Proof : Let $A=\Sigma^\*$,we know that $A$ is decidable. Now lets take a look at

$$ \Sigma^\*\cap A\_{TM}=A\_{TM}$$ Since $\Sigma^\*$ is the Set which contains all languagues it also contains $A\_{TM}$. But $A\_{TM}$ is known to be undecidable. Therefore its not true for all languagues that every subset of a decidable languague is decidable . $\blacksquare$

---
Tags: computability, undecidability, closure-properties, sets
---


# Question
Title: Is it necessary for NP problems to be decision problems?
Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems are decision problems. So what type of problems are basically in the class NP ? And is it unnecessary to say that solutions to such problems have a polynomial length output(as decision problems necessarily output either 0 or 1) ?

# Answer
Indeed problems in NP are decision problems which output 0 or 1 for a given input string. Prof Roughgarden is referring to the fact that problems in NP have short polynomially bounded proof (in the input length) of membership that can be verified efficiently (by polynomial time algorithm).
> 4 votes

# Answer
**Yes, NP is commonly only defined for decision problems**

In the commonly used definition of an NP problem, the answer can only be yes or no, as given on Wikipedia https://en.wikipedia.org/wiki/NP\_(complexity):

> In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems.

This is also made more explicit at:

> Many computer science problems are contained in NP, like decision versions of many search and optimization problems.

where e.g. the "search version" of the problem means "find the solution if it exists".

To give a concrete example, we could think of:

* is a given boolean formula satisfiable? Decision version of SAT.
* find an assignment for this formula if one exists. Search version of SAT.

**Search problems have dedicated classes called FNP and TFNP**

Since NP does not cover search problems, there is a specifically named complexity class for search problems called FNP which the Wikipedia page defines as:

> A binary relation P(x,y), where y is at most polynomially longer than x, is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y.

So here for a concrete SAT example you could think of:

* `x` as an boolean formula
* `y` as an assignment that satisfies the formula

Besides FNP, there is also the related TFNP class, for which an answer always exists. An example of this is the version of the integer factorization problem:

> P(x, y): x is an integer, and y is the list of all divisors

This version of the problem always has a trivial solution: 1 and x!

Note that we could however also formulate integer factorization as an FNP problem:

> P(x, y): x is an integer, and y is a non-empty list of all divisors \> 1 and \< x

where there is no solution for prime numbers.

**For every NP problem there is an FNP problem and vice versa**

For every FNP search problem we can trivially make up a corresponding NP decision problem, this is trivial

> for a given problem `x`, does a solution `y` exist that satisfies `x`

And conversely, for every NP problem there is a FNP problem. This is because from the definition of an NP problem, there is a verifier `V(x, y)` which checks if `y` is a solution to problem instance `x`. And so we formulate the FNP problem as:

> P(x, y) = V(x, y)

To be more precise, the FNP of an NP problem might not be unique, since there might be multiple correct answers for a given satisfiability decision.

**You can always reduce an FNP problem to an NP problem in polynomial time by bisection**

So from this, we see that there is a fundamental equivalence between NP and FNP problems, which gives precise meaning to informally saying that an FNP problem "is NP".

This reduction is trivial and generally useless in practice however.

For example, consider the FNP version of integer factorization.

And then consider the NP problem:

> Does integer x have a non-trivial factorization where the largest factor is larger than a chosen value z?

Note that now the input of the NP problem is a pair: (x, z), not just x.

If we could solve the above problem, we could just bisect the largest factor of x, divide x by it, and continue until the last factor.

Note that on the above reduction, we did use the property of the specific factorization problem that we can divide x by its factor to make the problem smaller, but this is not needed in general.

We just have to think as:

* the solution to every problem is a string of 0s and 1s which can be interpreted as an integer
* the size of the solution has to be polynomially bound by the size of the input, otherwise we wouldn't be above to verify it in polynomial time

Once solutions are encoded like this, we must have a maximum solution for a given problem, M. And so we just create an NP problem as:

> Is there a solution encoded as a number larger than M/2

and bisect like that.

**An FNP problem might be fundamentally harder than its (non binary cheat) decision version**

On the previous section, we saw that a reduction from FNP to an associated bisection decision problem is always possible in P.

However, if we consider more strictly only the exact decision problem without that extra bisection parameter, this is believed to not hold.

The trivial bisection reduction is generally useless, as it is possible that some non-bisection reductions could always be harder than the FNP problem. This is to be expected since the bisection exists for any problem, without using any properties of the problem.

One notable example is integer factorization, in which we know that the non-bisection NP version of the FNP problem, i.e.: "is the number prime", can be solved in polynomial time due to the AKS primality test.

Therefore, this serves as an example in which the FNP problem could be fundamentally harder than the non-bisection version of the problem, since it is currently believed that integer factorization is not in P (but also not NP-complete).

It is worth noting that in other cases however, the FNP problem can reduce to the non-trivial-bisection NP problem. https://blog.computationalcomplexity.org/2019/01/search-versus-decision.html mentions that this is the case for example of graph isomorphism (which like integer factorization is thought to be NP-intermediate). Such problems are called self-reducible. The proof of self-reducibility has been asked at: Why is Graph Isomorphism downward self reducible?

Furthermore, the wiki page for FNP mentions that this has actually been proven:

> Bellare and Goldwasser showed in 1994 using some standard assumptions that there exist problems in NP such that their FNP versions are not self-reducible, implying that they are harder than their corresponding decision problem.

**If the associated NP problem of an FNP-problem is NP-complete, we can always reduce the FNP to the NP problem in polynomial time**

Shown at https://cseweb.ucsd.edu/~mihir/cse200/decision-search.pdf "4 Decision vs Search for NP-complete languages".

For example for SAT, we could just set one variable to true and false, and then do the decision problem on a smaller problem. We then pick the value that works if any, and continue with that and the smaller problem with one less variable.

Then the argument goes along the "every NP Problem can be reduced to SAT" lines.

Note however that this is only known to be true in general for NP-complete decision problems! For example in integer factorization, the decision problem is P, while the search problem is believed to not be in P.

**TFNP appears to be easier than FNP**

As mentioned on the wiki page https://en.wikipedia.org/wiki/TFNP there are no known NP-hard problems known to be in TFNP, while there are obviously NP-hard FNP problems (e.g. SAT).

It is also worth noting that there isn't a trivial way to convert a TFNP problem to an NP problem like there is for FNP problems, because now we can't just use the "is there a solution" conversion.

You can always add an extra restriction to the TFNP problem that knocks off some solutions to reach a FNP problem however, like we did for integer factorization (exclude empty lists and 1 and N), but then the question is if you can still use that restricted solution.

**Decision problems form languages**

Another "philosophical" motivation for NP dealing only with decision problems is that the yes/no decision leads maps better in the concept of a formal language accepted by a Turing Machine: the formal language is the set of all strings accepted by the given machine (terminates and outputs yes on the tape).

Notably Turing complete languages are at the top of the Chomsky hierarchy, which has been an useful tool to classify the parsing complexity programming-like languages.

**Related questions**
> 1 votes

---
Tags: algorithms, np, p-vs-np
---


# Question
Title: Reference for counting the number of paths in a DAG
Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .

Is there a reference or name for the algorithm? If not, are there well known applications?

# Answer
> 1 votes
This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details.

It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs by extending the value set to $\mathbb{N} \cup \infty$ and adding a suitable $a^\*$ operator.

---
Tags: reference-request, dag
---


# Question
Title: Factoring algorithms after number field sieves
It seems that the General Number Field Sieve (GNFS) became number one and then RSA stopped its factoring challenges and there have been no advances in factoring algorithms besides quantum computers. So **are there faster algorithms after GNFS for classical computers?** Note that the 1980s and 1990s saw a series of new factoring algorithms, including elliptic curve and quadratic sieve. And then progress stopped.

# Answer
> 3 votes
From the first line of Wikipedia's GNFS page:

> "the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than"

The following factorizations of RSA numbers used none other than the GNFS algorithm:

**Conclusion:** The top researchers in the field are breaking factorization records using none other than GNFS (usually the CADO-NFS implementation). If there was a faster factorization algorithm for arbitrary semi-primes, surely the groups of Zimmerman and Lenstra would be using it, or at least mentioning it somewhere in their papers. *GNFS is still the fastest for arbitrary semi-primes.* For specific semi-primes like $p^2$ where $p$ is prime, there's faster algorithms such as doing the square root.

**A more interesting question might be**: *What are some recent developments in the field of factoring numbers on classical computers?* I might also be interested if there's anything promising out there that's been developed recently and might have a chance at beating GNFS one day. Also if you look at the above references, the authors will tell you of great achievements in improving implementations of the GNFS algorithm (for example the matrix step used to be harder than the sieving itself, but that was sorted out at around the time of factoring RSA-220).

---
Tags: algorithms, reference-request, quantum-computing, factoring
---


# Question
Title: Transport Triggered CPU Architecture MOV and Turing Completeness
Reading up on TTA CPU designs and the wikipedia article states that

> **Some** TTA implementations support conditional execution.

The trick to make an TTA ISA Turing-complete with an unconditional MOV instruction escapes me. Can anyone explain how that would work? (or share some resources where it is explained)

# Answer
For a CPU designed to use a TTA (Transport Triggered Architecture), one way to implement conditional branch could use a couple of addresses for these purposes:

* BRANCH\_ADDRESS: stores the location to branch to
* BRANCH\_ZERO: Sets PC to BRANCH\_ADDRESS when value written is 0. Otherwise does nothing.

This could be used to implement a 'branch-if-zero'. You could also add additional addresses that implement other branch modes, including those ithat hook into flags/state of other components hooked up to the TTA CPU, such as an ALU.
> 1 votes

# Answer
It all comes down to what you consider "conditional". For example, when you trigger an `AND`, the output varies depending on its operands: is that a conditional operation?

In this case, Wikipedia is talking about "conditional transport" (the ability to turn busses on and off via a register), not "conditional execution" (the ability to jump to different places based on some condition). The latter is what's needed for Turing-completeness, as you correctly pointed out.

In some TTAs, you can directly write to the program counter; in others, there's a functional unit that handles instruction fetching and decoding and all that, and it has ports for jumps. In the latter case, conditional jumps can be implemented with multiple ports, just like you might expect: write an address to the "jump destination" port, then write a value to the "branch if zero trigger" port, and it'll branch to the destination if the trigger value was zero.

Wikipedia suggests that a single port can be used for this:

> TTA implementations that only support unconditional data transports, such as the MAXQ, typically have a special function unit tightly connected to the program counter that responds to a variety of destination addresses. Each such address, when used as the destination of a "move", has a different effect on the program counter—each "relative branch " instruction has a different destination address for each condition; and other destination addresses are used CALL, RETNZ, etc.

This has the same effect: you just have to write the destination and the "opcode" to the same port, one after the other.
> 1 votes

# Answer
"unconditional MOV" just means no special support to skip transport (e.g., using guards). Computing the PC is still an option, and while coding becomes (more) awkward, Turing completeness is achieved.
> 0 votes

---
Tags: computer-architecture, turing-completeness, cpu
---


title: P vs. NP and Godel's Theorems

text:
# Question
Title: P vs. NP and Godel's Theorems
This post is based loosely on a previous post, but the presentation is somewhat different and hopefully much more succinct.

Basically, I'm wondering if it is plausible for there to be a formal proof of P!=NP if ZF is consistent (obviously the converse is true). The idea is this: since proofs to sentences in ZF can be viewed as witnesses in an NP-language, if P!=NP then this means that for some fixed $k$ not all provable sentences $\phi$ of ZF have a proof of length $\leq {|\phi|}^k$. But if ZF is inconsistent, then every sentence of sufficient length has a relatively short proof derived from a fixed contradiction. So we get that P!=NP implies that ZF is consistent. So if we have a formal proof of P!=NP then this would imply through Godel's Second Incompleteness Theorem that ZF is inconsistent (and thus P=NP) as well. Is there a problem with this approach?

# Answer
> 6 votes
> if P!=NP then this means that for some fixed $k$ not all true sentences $\phi$ of ZF have a proof of length ≤ $|ϕ|^k$.

You do not need to assume $P \neq NP$ to prove this claim. If all true sentences $\phi$ of ZF have a proof of length $\leq |\phi|^k$ then the halting problem could be solved by enumerating all proofs of "$M$ is halting" and "$M$ is not halting" up to that size. So it's not possible for all true sentences to have a short proof. Instead of $|\phi|^k$ we can take a function that grows even faster, e.g. $2^{2^{2^{|\phi|}}}$. There's no computable limit on how long a proof can be compared to its statement.

However, to speak about true sentences, we are assuming implicitly that ZF already has a model. So this reasoning does not prove that ZF is consistent - it assumes it from the start. There's no contradiction between "not all true statements have a short proof" and "all statements have a short proof" if there are no true statements.

# Answer
> 2 votes
Let $k=1$. Since there exist statements that have multiple very short proofs, there must be some sentence that has a shortest proof longer than its own length. So we already live in the "bad world" you're imagining. Since any short proof can have an irrelevant line introduced without changing anything as long as that line is a tautology, we even live in a pretty extreme version.

I'm not sure exactly what your reasoning is or where it's going wrong, but I think where you're going wrong is that in a world where ZF is consistent the set of valid deductions is different from in a world in which ZF is inconsistent.

---
Tags: complexity-theory, np-hard, p-vs-np
---


# Question
Title: What is the optimal algorithm for playing the hangman word game?
Suppose we are playing the game hangman. My opponent and I both have access to the dictionary during the game. My opponent picks a word from the dictionary with knowledge of the algorithm which I will use to guess his secret word. Once my opponent has picked a word, I am given only the length of the word. I can guess a letter which I think will be in the word, and if it is in the word my opponent identifies all of the positions of that letter in that word. If I guess a letter which isn't in the word, that's counted as one mistake. If I can guess the word before too many mistakes I win.

My opponent's goal should be to pick a word which maximizes the number of mistakes (incorrect guesses) I make before I can guess the word. My goal is to minimize them. (Traditionally, if the number of mistakes is \> some number then I lose the game, but we can relax that constraint.)

Consider three algorithms for letter guessing. These are the main ones I've thought of, but there are probably more, and I welcome alternate ideas. In all three algorithms, the first step will be to gather the list of words which are the same length as the secret word. Then, for each letter in the alphabet, count the number of words in the dictionary which contain that letter. For example, maybe 5000 contain "a", 300 contain "b", and so on. Here it is in python:

```
    alphabet = set('abcdefghijklmnopqrstuvwxyz')
    probabilities = {letter:0 for letter in alphabet}

    for word in dictionary:
        for letter in word:
            if letter in alphabet:
                probabilities[letter] += 1

    # now we have the letter frequencies

```

After that is where the three algorithms diverge.

1. In the first algorithm, we guess the letter which the most number of remaining words contain. So if 5000 remaining words contain "a" and no other letters are in that many words, we will pick "a" every time. If "a" is correct, this gives us positional information which we can filter the list further. For example, we might filter the list by all words that match ".a..". (Dots are unknown letters.) If "a" is incorrect, we filter out all words which contain "a". In the case where there is a tie and two letters are found in an equal number of words, letters are chosen alphabetically. So if we know the word matches ".ays", we'll just guess words in alphabetical order.
2. This is only slightly different from the first algorithm. Instead of always choosing alphabetical ordering, in the case of a tie we choose letters randomly. This has the benefit that our opponent doesn't know what we will pick. In the first strategy, "rays" is always better than "days". This avoids that issue.
3. In this case, we pick letters with a probability proportional to the number of words which contain that letter. At the beginning when we tallied the number of words which contain "a" and the number which contain "b" and so on, since "a" happened to be found in the most number of words, in strategies 1 and 2 we picked "a" 100% of the time. Instead, we will still choose "a" a plurality of the time, but a small number of times we'll pick "z" even though a might be found in 10x more words. I have my doubts about this strategy being optimal but it was used in research in 2010.

**So I have two questions:**

1. What is the optimal letter-guessing strategy which I should use *assuming that my opponent knows I will use this strategy*? In this we want to minimize the average number of guesses it will take to guess the secret word.
2. For a given word, say "pays", what is the average number of mistakes M I should be expected to make? Is there a closed-form way to calculate M, as opposed to running this simulation many times and averaging the results?

Clarifications

* Any English dictionary can be used. For example, this English dictionary with 84k words.. Subsets of dictionaries carefully chosen for ambiguity could also be interesting but are outside of the scope of this question.
* There is no constraint on the word size as long as the word is in the dictionary. The guesser will know the word size before he begins guessing.
* Only the total number of mistakes matters, which is independent of the word size. You don't get more chances for longer words, or fewer chances for shorter ones.
* I'm only interested in minimizing the average number of mistakes. If there are two optimal algorithms which have an equivalently small average number of mistakes, both are acceptable.
* In principle it is possible for there to be a situation where choosing one letter (say "b") leads to more information than another (say "a") even though "a" occurs in more possible words than "b" does. I am open to this possibility in practice as well. The three algorithms illustrated above assume that this does not happen due to the fact that a correct guess tends to yield more information than an incorrect one (i.e. positional information about a correct letter is usually better than "this letter is not in the word"). But an optimal algorithm need not make this assumption.

# Answer
> 3 votes
It is possible to compute the optimal strategy, but the computation might be fairly intensive, and I'm not sure whether it will give you much of a gain over simple heuristics. I'll explain how below. The main idea is to use dynamic programming.

# Deterministic strategies

Let me start first with the special case of deterministic strategies for choosing which letter to guess next, as they are easiest to analyze. This will give us a warmup before we move on to randomized strategies (which will probably be superior).

The state of the game at any point can be summarized by the pair $(g,r)$, where $g$ is the set of letters that have been guessed so far, and $r$ is the responses (i.e., the sequence of blanks and letters from $g$ that is visible to the player). The order of past guesses doesn't matter (which is why it suffices to have a set $g$ of past guesses). We'll say that a word $w$ is consistent with $(g,r)$ if it remains possible, i.e., if the opponent's word is $w$ and you make the guesses in $g$, then you'd get the response $r$.

Let $p(g,r)=1$ if it is possible to win from here, if starting from the state $(g,r)$. That means that there exists a strategy to win: where no matter which word the opponent is thinking of (as long as it is consistent with $(g,r)$), the number of wrong guesses you've made so far, plus the number you make in the future with this strategy, won't exceed the upper limit. Otherwise, define $p(g,r)=0$.

Now you can compute $p(g,r)$ with dynamic programming, using the recurrence relation

$$p(g,r) = \bigvee\_a \bigwedge\_{(g',r')} p(g',r'),$$

where $a$ ranges over all letters not in $g$ (i.e., all possibilities for which letter to guess next), and $(g',r')$ ranges over all possible responses if you guess $a$ next (i.e., $g'=g\cup \\{a\\}$, and we range over all words $w$ that are consistent with $(g,r)$ and compute the response $r'$ to guesses $g'$ if the word is $w$).

In particular, I suggest you compute $p(g,r)$ using depth-first search and memoization. Then, $p(\emptyset, - - \cdots -)$ will tell you whether it is possible to win within the upper limit, no matter what word the opponent chooses. By tracing the computation backward, you can reconstruct the optimal strategy.

Is this feasible? I expect it is. I think the number of possible states $(g,r)$ is not too large. (In particular, you can ignore states $(g,r)$ where you've already made too many incorrect guesses, and any state where only one word is consistent with that state is automatically a win, so it doesn't need further analysis.) As an optimization, given a state $(g,r)$, you can try enumerating all words $w$ that are consistent with them and simulate some fixed heuristic and check whether it will win for each word; if so, you don't need to do any further depth-first traversal and you can immediately mark $p(g,r)=1$. Also, you only need to consider guesses $a$ that appear in at least one word that is consistent with $(g,r)$.

So it should be pretty straightforward to compute the optimal deterministic strategy.

# Randomized strategies

We can follow a similar method to handle randomized strategies, but it gets a little more involved. Now let $p(g,r)$ denote the probability of winning from here, if we use the optimal strategies from here on. We can again compute this using dynamic programming.

The key difference is in the recurrence relation where we compute $p(g,r)$ from the quantities $p(g',r')$ where $(g',r')$ range over all states that could occur next after guessing one more letter. Here we have a simple two-player game. First we choose a probability distribution over the letters not in $g$. Then the opponent sees our distribution, and chooses a distribution on words $w$ that are consistent with $(g,r)$. Our payoff (and the amount the opponent loses) is equal to the probability that we win from here on given those choices. Notice that this can be computed from the $p(g',r')$ values. It turns out that since we go first and the opponent sees our choice, the opponent doesn't need a randomized strategy; they can do equally well with a deterministic strategy, i.e., by picking a single word $w$ based on our distribution. Then if we form a matrix $M$ where $M\_{w,i}$ holds the probability of winning if we choose letter $i$ next and the opponent chooses word $w$; we can fill in $M\_{w,i}$ as $p(g',r')$ where $g'=g \cup \\{i\\}$ and $r'$ is the response to guess $g'$ if the word is $w$. Then, we seek to solve the optimization problem $$\max\_v \min\_w (Mv)\_w = -\min\_v \max\_w -(Mv)\_w = -\min\_v \\|-Mv\\|\_\infty.$$ This can be solved using linear programming. So, we can compute $p(g,r)$ using linear programming from the values $p(g',r')$ where $g'$ is one bigger than $g$.

Putting this all together, we'll use depth-first traversal with memoization (or dynamic programming), using linear programming at each step to solve the 2-player game. This gives us the optimal randomized strategy to play hangman.

The resulting computation might be very expensive, as it requires billions or trillions of steps, where you solve a linear program in each step. So, I don't know whether it's realistic to use it in practice.

Some optimizations are possible, as suggested by @j\_random\_hacker. You can first compute $p(g,r)$ for deterministic strategies; then you only need to consider randomized strategies for states $(g,r)$ where $p(g,r)=0$.

# Heuristic strategies

You listed some reasonable heuristics for choosing a strategy. Here is one more heuristic. Given the state $(g,r)$, enumerate all possibilities for the next guess $a \notin g$. Let's focus on a single letter $a$. Then, for each $(g',r')$ that could occur as a next state after guessing $a$ (so $g'=g\cup \\{a\\}$), count the number of words $w$ consistent with $(g',r')$; take the maximum over these numbers, and use that as the count associated with $a$. The heuristic strategy is to choose the letter $a$ whose count is smallest.

# Computing the expected number of mistakes

You can compute the expected number of mistakes of a particular randomized strategy using dynamic programming. The details are similar to above, but the recurrence relation becomes simpler: it becomes

$$p(g,r) = \min\_w \mathbb{E}\[p(g',r')\],$$

where $w$ ranges over all words consistent with $(g,r)$, and $(g',r')$ is the distribution on the next state if the word is $w$ and the next letter guessed is chosen by your strategy. Given your strategy and the word $w$, it is easy to compute the distribution on guesses and thereby obtain the distribution on next states, so it's easy to compute $\mathbb{E}\[p(g',r')\]$.

---
Tags: game-theory, statistics, monte-carlo
---


# Question
Title: How to prove the language of all Turing Machines that accept an undecidable language is undecidable?
I want to prove that $L=\\{\langle M \rangle |L(M)\text{ is undecidable}\\}$ is undecidable

I am not sure about this. This is my try :

Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be a TM which is recognizing $A\_{TM}$. Let $S$ be a TM which works on input $\langle M,w \rangle$ in the following way(the goal is that $S$ will be a decider for $A\_{TM}$):

1. Construct a TM $N$ which works on Input $x$ as follows: Run $M$ on $w$. If $M$ $accepts$ run $A$ on $x$ and accept $x$ if $A$ accepts.(In this case is $L(N)=A\_{TM}$). If $M$ $rejects$ $w$, $accept$ $x$.(In this case is $L(N)=\Sigma^\*$)
2. Run $E$ on $N$ and accept if N accepts. Otherwise reject

I am not sure if my reduction is the right way or not. Maybe someone can help to finish the reduction :)

# Answer
I think you are on the right track but things need to be made more explicit. First, what machine exactly is $A$? Any machine? Where does your contradiction appear?

First, you need to explicitly say that $A$ is a machine for an undecidable language, for example, let $A$ be the universal machine, that on inputs $\langle M \rangle w$ simulates $M$ on $w$, and accepts if $M$ accepts $w$.

Then, say explicitly that $S$ is a decider (a machine that always halts), and include the simple extra steps that show that $S$ accepts $\langle M \rangle w$ if and only if $w \in L(M)$. Finally, recall that $S$ is then a decider for a problem we already know is undecidable; a contradiction.

Edit: Sorry, it seems that $A\_{TM}$ is standard notation for the universal machine. Forget about that comment if that is the notation used in your context.
> 2 votes

---
Tags: formal-languages, turing-machines, undecidability, church-turing-thesis
---


# Question
Title: How to view Graph Reduction/Graph Representation for a Haskell program?
I know that under the hood, for a Haskell program, the GHC compiler uses graph reduction for optimization. Is there any way to view this graphical representation of the program? I haven't been able to find an existing plugin that, given a Haskell program, produces its graphical representation. I am relatively new to Haskell.

Are there research tools available to study and manipulate such graphs?

# Answer
> 1 votes
Welcome to CS.SE!

I cannot present the underlying algorithms themselves, just the concepts they use.

The **normal form** (**NF**) of some expression is basically its result, like `42`, `Just 1`, `\ x -> 1 + x`.

The **weak head normal form** (**WHNF**) is some expression which is one of three:

1. A lambda: `\ x -> x + 5 * 6`. The **NF** is `\ x -> x + 30`.
2. Data constructor: `(3, 2 + 5)`. The **NF** is `(3, 7)`. It could be partially applied: `(,) (2 * 5)`. The **NF** is `\ x -> (10, x)`.
3. Partially applied built-in function: `(+) (2 * 8)`. The **NF** is `\ x -> 16 + x`.

As one can see, **WHNF** generalizes **NF**.

So, what have graphs got to do with this? Well, one can understand `f e1 e2 ... en` as a graph with a node `f` which is connected with `n` other nodes: `e1, e2, ..., en`. Evaluation is the reduction of the nodes**1**. To show why this is actually very cool I am going to use a picture which I stumbled upon on Wikipedia and HaskellWiki not so long ago:

So, what is going on in this picture? The idea is simple: when working with lists, we have a binary operation `(:)` and some initial value `[]`. When we are folding, we have a binary operation `f` and some initial value `z`. The data structure does not change - only the nodes of our graph. To get the complete result (**NF**, that is), we reduce the graph.

**(Please note that the initial `1 : 2 : 3 : 4 : 5 : []` could not have been reduced any further; in (pseudo-)haskell the lists are: `data [a] = a : [a] | []`.)**

---

**1**Some technical details on evaluation (the basic tools to manipulate graphs, just as you have asked). The programmer might force the reduction. `seq x y` forces its first argument to the **WHNF** and returns the second (being basically `flip const` magically strict in the first argument). More formally:

> ...`seq x y` means that whenever `y` is evaluated to weak head normal form, `x` is also evaluated to weak head normal form.

If the programmer wants to do the same for the **NF**, they should take a look at `Control.DeepSeq.deepseq`.

---
Tags: programming-languages, compilers, haskell
---


# Question
Title: Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight?
I know this is probably a really basic question but I just cant wrap my head around it right now.
So the basic PSO update formula is as follows: $$\bar{v}\_{n+1} = \omega \cdot \bar{v}\_n + c\_k \cdot r\_1 \cdot (\bar{p}\_{best}-\bar{p}\_n)+ c\_s\cdot r\_2 \cdot (\bar{g}\_{best}-\bar{p}\_n) $$ `velocity(n+1) = momentum_component + cognitive_component + social_component`

Now both the *cognitive* part and the *social* part have the same weight to them on the updated velocity.
So when a particle is moving around the space and lets say the cognitive part pulls the particle in a certain direction while the social component pulls the particle in the opposite direction, shouldnt the particle be stuck forever? Or at least go back and forth never converging?

However if I run the basic vanilla PSO algorithm the particles always seem to converge to the gbest as if their pbest has barely any influence.

# Answer
The random number biases distance along the vectors, so it changes per update helping in escaping local optimum, and the global best also changes during the algorithm, if you really want some of these answers try programming a visual particle system using PSO.
> -1 votes

---
Tags: algorithms, optimization, machine-learning
---


# Question
Title: Algorithm to compute average length of a simple path
Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?

# Answer
> 5 votes
I guess you already know that a polynomial algorithm for counting the number of simple paths between two nodes would imply P=NP, this result is due to Valiant (The complexity of enumeration and reliability problems, 1979).

Now imagine, expecting to discover a contradiction, that you could compute $\text{avg}(G, u, v)$ in polynomial time.

Let $G+l$ be the graph resulting from adding a simple path of length $l$ between $u$ and $v$ in $G$. This new path is made of $l-1$ new nodes and it does not interfere with any previous path from $u$ to $v$, provided $l \geq 2$.

Then, $\text{avg}(G+3,u,v) - \text{avg}(G+2,u,v)$ = $1/(\\#\text{Paths}(G,u,v)+1)$, from which you can get $\\#\text{Paths}(G,u,v)$ in polynomial time. But we know this cannot be expected to be done in polynomial time, a contradiction.

---
Tags: algorithms, graphs, np-hard
---


title: Combinations of set unions

text:
# Question
Title: Combinations of set unions
I have a set $S = \\{0,1,2,3,4,5,6,7,8,9\\}$. $S\_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S\_i$ has the same union, that is $S\_1 \cup S\_2\cup S\_3 = S\_1\cup S\_2\cup S\_4 = ...=S\_3\cup S\_4\cup S\_5 = A$ and no $S\_i\cup S\_j = A$. What is lexicoraphical least of such $S\_i$s?
I have to write a Python code for this and I would appreciate any help that could direct me to find a solution. What should I know to be able to solve this problem in the shortest possible period? Also, if there's a better way to formulate this problem please do leave me comments with your suggestions. If the information is not sufficient I can clarify further.

# Answer
> 2 votes
I understood the problem as that we can select any $S\_i$ satisfying these conditions. Then the answer is $\\{0, 1, 2, 3, 4, 5\\}$. The construction is unique in a certain sense.

Wlog we can assume that $S=A$ (otherwise, just remove redundant elements from $S$). I'll use $A, B, C, D, E$ instead of $S\_i$. One way to arrive at a solution is to draw a Venn diagram for $A, B, C$ and to think about it:

What can we say about it:

* $A \setminus (B \cup C) \ne \emptyset$. Otherwise $B \cup C = A \cup B \cup C = S$. Similarly for $B$ and $C$.
* For $D$ we must have $A \setminus (B \cup C) \subseteq D$. Otherwise, $B \cup C \cup D \ne B \cup C \cup A = S$. Similarly for $B$ and $C$.
* For $D$ we must have $A \cap C \setminus B \not \subseteq D$. Otherwise (just look at the diagram), $$B \cup D = B \cup (A \setminus (B \cup C)) \cup (C \setminus (A \cup B)) \cup (A \cap C \setminus B) = S$$
* What we said for $D$ also holds for $E$. I.e. it must contain the symmetric difference but must not contain $A \cap C \setminus B$ and similar.
* We must have $D \cup E \cup X = S$ for $X = A,B,C$. Therefore, $D \cup E \cup (A \cap B \cap C) = S$. In particular, it means that $A \cap B \cap C \not \subseteq D \cup E$, since otherwise $D \cup E = S$.

Also, $S \setminus (A \cap B \cap C) \subseteq D \cup E$. Therefore, forgetting about symmetric difference: $$((A \cap C) \cup (A \cap B) \cup (B \cup C)) \setminus (A \cap B \cap C) \subseteq D \cup E$$ Therefore, while $A \cap C \setminus B$ doesn't belong to either $D$ or $E$, it belongs to their union.

Note that conditions above are necessary and sufficient. Putting this together:

* $A \setminus (B \cup C)$ must have at least one element, which also belongs to both $D$ and $E$. The same for $B, C$.
* $A \cap C \setminus B$ must have at least two elements: one belongs to $D$, another belongs to $E$. The same for other pairwise intersections.
* $A \cap B \cap C$ has at least one element, which doesn't belong to either $D$ and $E$.

Note that we've used all $10$ elements from $S$. All sets $A,..,E$ have $6$ elements, so we just select one of them to be $S\_1$, and arrange elements in the sets so that $S\_1 = \\{0,..,5\\}$

---
Tags: combinatorics, sets, python
---


# Question
Title: Bits needed to send parameters of perfect hash functions
Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters will be used by the user to compute the hash of a certain file in order to find its position between files on the main server. The question is that how many bits are needed to be transmitted between the server and the user? Is that in order of $O(n)$? Can anybody suggest a specific algorithm with its parameters and communication cost?

# Answer
If I understand you correctly, the following is the case:

1. The server has $n$ files in some order $f\_1, f\_2, \dots, f\_n$.
2. The user also has exactly one of those files, $f\_u$, but does not know $u$.
3. The user and server agree on some protocol beforehand, which does not depend on any of the $f$.
4. The server gets to communicate some bits of information to the user once, and only in this direction.
5. From this information the user must be able to find integer $k$ such that $f\_k = f\_u$.

---

Based on the above I would choose some strong cryptographic hashing function $H$, and use it to hash all files on the server. Take the $k$-bit prefix of this hash such that all prefixes are unique. Send these in the correct order for $O(kn)$ total complexity.

How big does $k$ need to be in practice? The chance that the first hash is not a duplicate is $1$, the second $1- \frac{1}{2^k}$ chance, the third $1- \frac{2}{2^k}$, etc. We find that none are duplicates as $\prod\_{i=0}^{n-1} (1 - i/2^k) \approx e^{-n^2/2^{k+1}}$ by the Birthday paradox. Let's say we're okay with constant chance of failure $\epsilon$, and thus we want $e^{-n^2/2^{k+1}} \> 1-\epsilon$, which gives $k \in O(\log(n))$.

Thus our solution uses $O(n \log n)$ bits. You can't beat this (asymptotically) either, because a full permutation worth of information needs to be transferred, which takes $O(\log n!) = O(n \log n)$ bits.
> 1 votes

---
Tags: hash-tables, databases
---


# Question
Title: How to answer the following queries on a tree?
Given a tree of "N" nodes(each node has been assigned a value A\[i\],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : \[w\]

(which means find the lowest valued node in the sub-tree of \[w\] , only considering those nodes in the sub-tree of \[w\] which have a depth less than equal to K) .

Example :

Value of nodes of tree :

A\[1\] = 10

A\[2\] = 20

A\[3\] = 30

A\[4\] = 40

A\[5\] = 50

A\[6\] = 60

Edges of tree : \[1-2\],

\[2-3\],

\[3-4\],

\[4-5\],

\[4-6\].

K=2.

Query-1 : \[w\]=1 . All nodes in subtree of \[w\] : (1,2,3,4,5,6) , now, all nodes in sub-tree of \[w\] having depth less than equal to K : (1,2) . Hence , minimum(A\[1\],A\[2\])=min(10,20)=10 is the answer .

Query-2 : \[w\]=4 . All nodes in subtree of \[w\] : (4,5,6) , now, all nodes in sub-tree of \[w\] having depth less than equal to K : (4,5,6). Hence , minimum(A\[4\],A\[5\],A\[6\]) = min(40,50,60)=40 is the answer .

# Answer
Without any precomputation, a depth-limited version of depth-first search would be a natural approach to this problem: then it's like finding the minimum of an array, you could find the minimum weight during the search. But a time-efficient way (if you have multiple queries for different nodes and $K$) is to indeed precompute the answer for all the nodes: a linear algorithm seems achievable, starting from the bottom level up to the root, level by level. You have to store for each node an array $a$ such as $a(K)$ gives the desired value. And if you modify the value of a node later, I think a backpropagation scheme could be also considered.
> 1 votes

---
Tags: algorithms, trees
---


title: Faster computation of $ke^{-(x - h)^2}$

text:
# Question
Title: Faster computation of $ke^{-(x - h)^2}$
The question is quite simple; almost every computer language today provides the $\exp(x)$ function in their standard library to compute expressions like $ke^{-(x - h)^2}.$ However, I would like to know whether this function is the fastest way to compute the above expression. In other words, is there some way to compute $ke^{-(x - h)^2}$ faster than $\exp(x)$ in standard libraries while keeping the result very accurate?

I would like to specify that Taylor series will not work for my application, nor will any other polynomial approximations.

In the end, I wish to compute a series of these expressions, $$\sum^n\_{i = 0} k\_ie^{-(x - h\_i)^2}$$ for some integral $n \geq 0.$

# Answer
> 2 votes
There are several reasons why your standard library implementation of `exp` is slower than you might hope:

* It should to be accurate to 0.5ulp (or 1ulp at worst), no matter what number you give it. This means that special care may need to be taken, say, in the subnormal range.
* It needs to work for *all* floating point numbers, and return a reasonable answer for all of them. Assuming that you're on an IEEE-754 platform, this includes NaN, Inf, etc. The standard explains what the "correct" answer is for all of those cases, and the library function needs to get it right.
* It *may* not be specialised for your specific instruction set (i.e. your CPU may have some advanced floating-point instructions that `libc` doesn't use by default).

This is what it means to be general-purpose.

Chances are that your standard library has had a lot of effort put into it, and you cannot beat it and still be general-purpose. To get more performance, you need to relax some restrictions. So we're going to need some details. How much accuracy is enough? Can you assume anything about the range of inputs?

I've gone through a typical implementation elsewhere (see this previous answer), and that should help you get an idea of how these things can be implemented.

# Answer
> 1 votes
TL;DR: Using the `exp` function of your library is likely the fastest way to compute $ke^{-(x-h)^{2}}$, but it's usually worthwhile to do some limited experiments to double-check that assumption.

Generally speaking, when programming for a reasonably mature platform, standard math libraries tend to be highly optimized by both domain experts and microarchitecture experts. While not all functions may be optimized equally well, the most commonly used math functions (`exp`, `log`, `sin`, `cos`, `atan{2}`) tend to be the most heavily optimized.

I am assuming you have already profiled your code to establish that the multiple calls to `exp` are a bottleneck in your code, and that you have double-checked your algorithm(s) to minimize the calls to this function. I further assume that you have already established that you cannot perform the computation at lower precision (say, `float` instead of `double`), which results in a significant performance increase on most platforms.

Are you using the latest compiler and libraries available for your platform? Performance improvements are incorporated all the time, so recent tool chains with their associated libraries tend to offer the highest performance. Are you targeting the compiler's code generation to the architecture that most closely reflects your processor's architecture? Newer processors tend to add performance enhancing hardware, such as fused multiply-add (FMA) units and wider SIMD operations and compiler often need to be instructed to use them via compiler flags, e.g. `-march=core-avx2`.

Also, make sure you are maxing out compiler optimizations. Some advanced optimizations may require adding compiler switches by hand as they are not subsumed under `-O3`. Examples could be auto-vectorization, whole-program optimization (by use of an optimizing linker), or profile-guided optimizations. Your math library may offer multiple levels of performance / accuracy trade-offs. For example, Intel's MKL provides three modes: high accuracy (maximum error \< 1 ulp), lower accuracy (maximum eror \< 4 ulp), enhanced performance. The lower the accuracy requirement, the higher the performance.

Note that the overall numerical error in the evaluation of the expression will very likely be dominated by the error in the `exp` argument *magnified* through exponentiation. Depending on the magnitude of the argument, a 1 ulp error in the input can well turn into a 1000 ulp error in the output. In light of that, the `exp` function itself does not have to be extremely accurate.

Standard math library functions need to follow the relevant language specification exactly, which includes overhead for the handling of special cases and detection of errors. Standards may also mandate certain accuracy requirements. If your use case allows the elimination of special case handling and a reduction in accuracy, you could try to roll your own function, like the exemplary C implementation below, which requires hardware support for FMA. It is usually a good idea to use the tool chain specific attributes to force inlining of any custom function to eliminate function call overhead and improve instruction scheduling flexibility.

```
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>

double uint64_as_double (uint64_t a)
{
    double r;
    memcpy (&r, &a, sizeof r);
    return r;
}

uint64_t double_as_uint64 (double a)
{
    uint64_t r;
    memcpy (&r, &a, sizeof r);
    return r;
}

/* Compute exponential function e**x. Maximum error found in testing: < 0.9 ulp */
double my_exp (double a)
{
    const double ln2_hi = 6.9314718055829871e-01;
    const double ln2_lo = 1.6465949582897082e-12;
    const double l2e = 1.4426950408889634; // log2(e)
    const double cvt = 6755399441055744.0; // 3 * 2**51
    double f, j, p, r;
    uint64_t i;

    // exp(a) = exp2(i) * exp(f); i = rint (a / log(2))
    j = fma (l2e, a, cvt);
    i = double_as_uint64 (j);
    j = j - cvt;
    f = fma (j, -ln2_hi, a);
    f = fma (j, -ln2_lo, f);
    // approximate p = exp(f) on interval [-log(2)/2, +log(2)/2]
    p =            2.5022018235176802e-8;  // 0x1.ade0000000000p-26
    p = fma (p, f, 2.7630903491116071e-7); // 0x1.28af3fcaa8f70p-22
    p = fma (p, f, 2.7557514543681978e-6); // 0x1.71dee62382584p-19
    p = fma (p, f, 2.4801491039342422e-5); // 0x1.a01997c8b03e6p-16
    p = fma (p, f, 1.9841269589067952e-4); // 0x1.a01a01475dae0p-13
    p = fma (p, f, 1.3888888945916467e-3); // 0x1.6c16c1852b7d7p-10
    p = fma (p, f, 8.3333333334557717e-3); // 0x1.11111111224c6p-7
    p = fma (p, f, 4.1666666666519782e-2); // 0x1.55555555502a5p-5
    p = fma (p, f, 1.6666666666666477e-1); // 0x1.5555555555511p-3
    p = fma (p, f, 5.0000000000000122e-1); // 0x1.000000000000bp-1
    p = fma (p, f, 1.0000000000000000e+0); // 0x1.0000000000000p+0
    p = fma (p, f, 1.0000000000000000e+0); // 0x1.0000000000000p+0

    // exp(a) = 2**i * exp(f);
    uint64_t ri = (double_as_uint64 (p) + (i << 52));
    r = uint64_as_double (ri);

    // handle special cases
    double fa = fabs (a);
    if (! (fa < 708.0)) { // |a| >= 708 requires double scaling
        i = (a > 0.0) ? 0ULL : 0x8030000000000000ULL;
        r = uint64_as_double (0x7fe0000000000000ULL + i);
        r = r * uint64_as_double (ri - i - 0x3ff0000000000000ULL);
        if (! (fa < 746.0)) { // |a| >= 746 severe overflow / underflow
            r = (a > 0.0) ? INFINITY : 0.0;
            if (isnan (a)) {
                r = a + a;
            }
        }
    }
    return r;
}

```

# Answer
> 0 votes
See njuffa’s answer first.

You can improve on it if x is often close to h. Njuffa’s answer finds the result for cases where the result is between sqrt(0.5) and sqrt(2) and scaling by a power of 2. If abs(h-x) is small enough that the exponent is less than sqrt(1/2) then you can remove all the scaling code; if x is even closer to h then you can use a lower degree polynomial. If you evaluate this term gazillion times with the same k, then k can be incorporated in the polynomial.

And on typical processors you can evaluate a polynomial if high degree with less latency then using the Horner scheme by evaluating even and odd powers in parallel.

---
Tags: efficiency
---


# Question
Title: How do you convert bits into a different alphabet?
I have forgotten how to do this. How do I figure out what the requirements are for a 128-bit string using a certain alphabet?

That is to say, I want to generate a UUID (128-bit) value, using only the 10 numbers for the alphabet. How many numbers do I need, and what is the general equation so I can figure this out for any alphabet of any size?

What is the equation for any n-bit value with any x-letter alphabet?

The way I do it is to guess and slowly iterate until I arrive at a close number. For powers of 10 it's easy:

```
Math.pow(2, 128)
3.402823669209385e+38
Math.pow(10, 39)
1e+39

```

For other numbers, it takes a little more guessing. Would love to know the equation for this.

# Answer
To estimate the number of decimal digits needed to represent a $128$ bit number you use logarithms to base $10$:

$128 \times \log\_{10}(2) \approx 38.53$

so you need $39$ decimal digits to represent a $128$ bit number.

In a general, for an “alphabet” with $n$ symbols you need to find the value of $128 \times \log\_n (2)$ and then round this up to the next whole number.
> 2 votes

---
Tags: mathematical-foundations
---


# Question
Title: Does every thread have its main function?
Does every thread have its own main function?

I know that its have its own stack, but what about main function (not necessarily a function which called main).

For example, when creating a thread, we pass a function as an argument for the new thread to run it.

I tried to search about this topic, but couldn't find answers.

# Answer
> 1 votes
For any reasonable definition of a 'main function', *no*.

Each thread has to start at *some* point in the code. For the main thread that is usually called the main function.

Modern programming languages are often designed that when starting a new thread it starts in a given function. You could call that the 'main function' of that thread, but is more commonly called its entry point.

However the entry point of a thread does not have to be at some dedicated function, or even at the start of a function. As a counterexample I would invite you to look at POSIX `fork()`.

---
Tags: threads
---


# Question
Title: Error in pivot selection algorithm for merge phase [Sorting]
In the paper Comparison Based Sorting for Systems with Multiple GPUs, the authors describe the selection of a pivot element with respect to the partition on the first GPU (and its mirrored counterpart on the other GPU-partition). That pivot element is crucial for being able to merge the two partitions, given that we have already sorted them on each GPU locally.

However, the pseudo-code for that pivot-selection, as shown in the paper, doesn't seem to reflect the whole truth since when implementing it 1:1, the selected pivot element is off by some elements in some cases, depending on the input - the amount of elements to sort and therefore the amount of elements per partition (the chunk of data that each GPU gets).

To get more specific, the problem is - to my understanding - that the while loop is exited too early due to the stride being reduced down to zero before the correct pivot element has been found. In general, the approach is binary search-like, where the range of where the pivot can fall, is halved each iteration.

Can anyone spot what needs to be done here?

Here is a C++ implementation of the pivot selection:

```
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b)
{
  size_t pivot = a.size() / 2;
  size_t stride = pivot / 2;
  while (stride > 0)
  {
    if (a[a.size() - pivot - 1] < b[pivot])
    {
      if (a[a.size() - pivot - 2] < b[pivot + 1] &&
          a[a.size() - pivot] > b[pivot - 1])
      {
        return pivot;
      }
      else
      {
        pivot = pivot - stride;
      }
    }
    else
    {
      pivot = pivot + stride;
    }
    stride = stride / 2;
  }
  return pivot;
}

```

P.S.: I tried ceiling the stride in order to not skip iterations when the stride is odd, but this introduced the issue of moving out of bounds of the array and even after handling those cases by clipping to the array bounds, the pivot was not always correct.

# Answer
The "Algorithm 1 Pivot selection" of that paper is rather sloppy. The critical mistake is, as you have noted, "the while loop in the algorithm is exited too early due to the stride being reduced down to zero before the correct pivot element has been found".

There are two other drawbacks.

* The condition, `a[len(a) − pivot − 2] < b[pivot + 1]` is superfluous since it is implied by `a[len(a) − pivot − 1] < b[pivot]`.
* It does not handle the situation where there are equal elements in the array.

To address that critical mistake, make sure that the stride is always greater than 0. To prevent out-of-bounds exceptions, extreme boundary cases should be specially handled beforehand. To handle equal elements, equal signs can be included at some comparisons.

Here is a correct algorithm in C++ that selects the desired pivot, following the pseudocode in the paper with the aforementioned modifications.

```
// Return a pivot so that a[size-pivot:size] and b[0:pivot] should
// be swapped. If 0 is returned, no elements should be swapped.
// It is assumed that vector a and b are sorted of the same size.
size_t SelectPivot(const std::vector<int> &a, const std::vector<int> &b) {
  size_t size = a.size();

  if (b[0] >= a[size - 1]) return 0;
  if (a[0] >= b[size - 1]) return size;

  size_t pivot = size / 2;
  size_t stride = std::max(1, pivot / 2);
  while (true) {
      if (a[size - pivot - 1] <= b[pivot]) {
          if (a[size - pivot] > b[pivot - 1]) return pivot;
          else pivot = pivot - stride;
      } else {
          pivot = pivot + stride;
      }

      stride = (stride + 1) / 2;
  }

  return pivot;
}

```

Note that the method above requires the size of `a` is equal to that of `b`. Otherwise, a few more lines of code are needed.

If you are not required to stick to the pseudocode in that paper, which is not very good anyway, please check another version of my answer, where I use my preferred version of binary search to select the desired pivot.
> 2 votes

---
Tags: algorithm-analysis, reference-request, sorting, search-algorithms, binary-search
---


# Question
Title: Book recommendations on the analysis of randomized algorithms
I would like to read some books (or any other material) that cover the design of randomized algorithms with a particular focus on the analysis. My main goal is to develop the rigour needed to construct the **proof of correctness** for such algorithms.

I am currently reading Probability and Computing - M. Mitzenmacher, E. Upfal, which I find to be a good introduction to this topic.

What are your suggestions?

# Answer
> 4 votes
*Randomized Algorithms* by Motwani, Rajeev, and Raghavan contains a lot of excellent material on the design and analysis of algorithms. They show many proofs of correctness for different randomized algorithms.

# Answer
> 4 votes
I do not know if it meets your needs but MIT's OCW site has free lecture notes from a class on the subject here:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/lecture-notes/

It also has assignments and answers here:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/assignments/

The syllabus refers to the book one of the other answers lists and it has links to related OCW classes:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-randomized-algorithms-fall-2002/syllabus/

Maybe this material will help. Nice that they provide free lecture notes as PDF files.

Bobby

# Answer
> 1 votes
The Book 'The Design of approximation algorithms' contains some chapters regarding randomized (approximation) algorithms.

I think it is well written and some algorithms would be easy to understand for 'beginners'.

It is free for everyone https://www.designofapproxalgs.com/index.php

---
Tags: algorithm-analysis, randomized-algorithms, books
---