# Question
Title: What are the most used statements in programming (ranked)?
I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (or at least for one modern language).

This is for a private research project where I am writing my own bytecode assembler and compiler for a custom language.

For example, the C#-code:

```
int a = 0;
int b = a * 2;
DoSomething(a, b);

```

would have 2 assignments and 1 function call.

So I'm wondering is there any study or somethig similar, regarding the usage frequency of statement types in general?

thx in advance

# Answer
> 2 votes
I don't know about statement types, but there's been a lot of research over the decades about CPU instruction frequency and how it impacts ISA design, IR design, and VM design... but it's all for languages like C. See, for example, loads/stores/branch frequencies for the SPEC2017 benchmarks.

If your language is C-like, there are basically only two reasons to compile to a virtual machine:

* The goal is portability and/or optimisation convenience, in which case it is an intermediate representation on the way to generating code for a real machine.
* The goal is some unusual performance constraint, such as extremely fast compilation, or for the generated code to be as tiny as possible.

In managed/interpreted languages, the main considerations are:

* If the VM code is also a distribution format (e.g. JVM or DotNET), size may be a factor.
* When interpreting, maximising the amount of "actual computation" (as opposed to interpreter overhead) performed for each interpreted instruction.
* When compiling (whether AoT or JIT), preserve as much of the relevant semantics of the source language as is needed for efficient optimisation, and discard (as far as possible) as much of the irrelevant semantics as possible.

Examples of that last point: Preserving basic types (integers, floats) is much more important than preserving non-basic types (structs, objects). Preserving the distinction between static calls and dynamic calls in OO languages is also extremely important.

I suspect that a reason why there isn't as much general research on object-oriented, managed, non-C-like languages (calling them "modern" is arguably misleading!) is because specific libraries and frameworks tend to dictate the style of programming that programmers do.

For C# specifically, if such information has been collected, it seems unlikely that Microsoft is telling anyone.

---
Tags: formal-languages, regular-languages, programming-languages, compilers, type-theory
---


# Question
Title: How to prove that the Church encoding, forall r. (F r -> r) -> r, gives an initial algebra of the functor F?
The well-known Church encoding of natural numbers can be generalized to use an arbitrary (covariant) functor `F`. The result is the type, call it `C`, defined by

```
  data C = Cfix { run :: forall r. (F r -> r) -> r }

```

Here and below, for simplicity, we will assume that `F` is a fixed, already defined functor.

It is widely known and stated that the type `C` is a fixpoint of the functor `F`, and also that `C` is an initial `F`-algebra. For example, if the functor `F a` is defined by

```
 data F a b = Empty | Cons a b

```

then a fixpoint of `F a` is `[a]` (the list of values of type `a`). Also, `[a]` is the initial algebra. The Church encoding of lists is well known. But I could not find a rigorous proof of either of these statements (`C` is a fixpoint, and `C` is the initial algebra).

The question is, how to prove rigorously one of the two statements:

1. The type `C` is a fixpoint of the type isomorphism `F C ≅ C`. In other words, we need to prove that there exist two functions, `fix :: F C -> C` and `unfix :: C -> F C` such that `fix . unfix = id` and `unfix . fix = id`.
2. The type `C` is the initial algebra of the functor `F`; that is, the initial object in the category of `F`-algebras. In other words, for any type `A` such that a function `p :: F A -> A` is given (that is, `A` is an `F`-algebra), we can find a unique function `q :: C -> A` which is an F-algebra morphism. This means, `q` must be such that the law `q . fix = p . fmap q` holds. We need to prove that, given `A` and `p`, such `q` exists and is unique.

These two statements are not equivalent; but proving (2) implies (1). (Lambek's theorem says that an initial algebra is an isomorphism.)

The code of the functions `fix` and `unfix` can be written relatively easily:

```
 fix :: F C -> C
 fix fc  = Cfix (forall r. \g -> g . fmap (\h -> h g) fc )
 unfix :: C -> F C
 unfix c = (run c) (fmap fix)

```

Given a function `p :: F A -> A`, the code of the function `q` is written as

```
 q :: C -> A
 q c = (run c) p

```

However, it seems difficult to prove directly that the functions `fix`, `unfix`, `q` satisfy the required properties. I was not able to find a complete proof.

Is it easier to prove that `C` is an initial algebra, i.e., that `q` is unique, than to prove that `fix . unfix = id`?

In the rest of this question, I will show some steps that I was able to make towards the proof that `fix . unfix = id`.

It is not possible to prove either (1) or (2) simply by using the given code of the functions. We need additional assumptions. Similarly to the Yoneda identity,

```
 forall r. (A -> r) -> F r   ≅   F A   ,

```

we need to assume that the functions' code is fully parametric (no side effects, no specially chosen values or fixed types) so that the parametricity theorem can be applied. So, we need to assume that the type `C` contains only functions of type `forall r. (F r -> r) -> r` that satisfy the appropriate naturality law (known as "free theorem" after P. Wadler's paper "Theorems for free").

The parametricity theorem gives the following naturality law ("free theorem") for this type signature:

For any types `A` and `B`, and for any functions `p :: F B -> A` and `f :: A -> B`, the function `c :: forall r. (F r -> r) -> r` must satisfy the equation

```
  c (f . p) = f . c (p . fmap f)

```

Using this naturality law with appropriately chosen `p` and `f`, one can show that the composition `fix . unfix` is a certain function of type `C -> C` that must be equal to `\c -> (run c) fix`.

However, further progress in the proof does not seem to be possible; it is not clear why this function must be equal to `id`.

Let us temporarily define the function `m`:

```
 m :: (F C -> C) -> C -> C
 m t c = (run c) t

```

Then the result I have is written as

```
fix . unfix  = m fix

```

One can also show that `unfix . fix = fmap (m fix)`.

It remains to prove that `m fix = id`. Once that is proved, we will have proved that `F C ≅ C`.

The same naturality law of `c` with different choice of `p` and `f` gives the strange identity

```
 m fix . m (m fix . fix) = m (m fix . fix)

```

But I do not know how to derive from this identity that `m fix = id`.

# Answer
> 7 votes
$\newcommand{\fix}{\mathsf{fix}}$ $\newcommand{\fold}{\mathsf{fold}}$ $\newcommand{\map}{\mathsf{map}}$

Here is, I believe, how one would use parametricity to prove your last lemma. I'm going to rework some stuff slightly for my own understanding. We have: $$C = ∀ r. (F r → r) → r$$ with $F$ functorial. We have: $$\fix : F C → C$$ corresponding to your definition, and I'm going to call a generalization of your `m`: $$\fold : (F r → r) → C → r \\ \fold\ α\ c = c\ α$$

So, we want to prove that for all $c : C$, $\fold\ \fix\ c = c$

Parametricity looks like this:

$$∀(R : a \Leftrightarrow b).\\ ∀ (α : F a → a) (β : F b → b).\\ (∀ x y. FR(x,y) → R (α\ x, β\ y))\\ → ∀ c. R (c\ α, c\ β)$$

To unpack this a bit, if we have a types $a,b$, a relation $R$ on them, algebra structures $α,β$, and a proof that they preserve the relation, then $R$ relates $c \ α$ to $c \ β$. The idea behind the "preservation" criterion is that $FR(x, y)$ holds if $x$ and $y$ have the same $F$ 'shape', and corresponding occurrences of $a$ and $b$ values are related by $R$.

So, let's make some choices. Suppose we have $ζ : F z → z$. Then: $$a \equiv C \\ b \equiv z \\ R(c, z) \equiv c\ ζ = z \\ α \equiv \fix \\ β \equiv ζ$$ the result of parametricity for these choices will be: $$R(c\ \fix, c\ ζ) \equiv c\ \fix\ ζ = c\ ζ$$

Then by function extensionality we will obtain $c = c\ \fix = \fold\ \fix\ c$. Our obligation is to prove:

$$∀ fc\ fz. FR(fc,fz) → R (\fix\ fc,ζ\ fz)$$

The goal is $$\fix\ fc\ ζ = ζ\ fz$$ By unfolding the definition of $\fix$ we know: $$\fix\ fc\ ζ = ζ (\map\_F\ (\fold\ ζ)\ fc)$$

However, the meaning of $FR(fc,fz)$ is actually that $$\map\_F\ (\fold\ ζ)\ fc = fz$$ So the result is immediate.

I haven't thought about whether it's possible to make due with dinaturality. I think it is not, but I could be wrong.

Edit:

The free theorem for this scenario is:

$$(∀ x. f (α\ x) = β (\map\_F\ f \ x)) \Rightarrow f (c\ α) = c\ β$$

If we choose $$f = \fold\ ζ \\ α = \fix \\ β = ζ$$ then our obligation is:

$$\fold\ ζ\ (\fix\ x) = \fix\ x\ ζ = ζ (\map\_F\ (\fold\ ζ)\ x)$$

which is just the definition of $\fix$. The result is:

$$\fold\ ζ\ (c\ \fix) = c\ ζ$$

which again gives us what we wanted. Note that this is also not the same as dinaturality, though. I believe the difference is that dinaturality allows us to shift $f$ around in the expression, but parametricity allows us to absorb it into one of the algebras.

---
Tags: type-theory, functional-programming, fixed-point, church-numerals
---


# Question
Title: Existence of particular/specialized halting oracles
It is known that there **does not exists** an oracle $H$ which given any pair $(M,I)$ where $M$ is a machine and $I$ is an input (possibly still a machine) to have $H(M(I)) = YES$ if $M(I)$ halts and $H(M(I)) = NO$ if $M(I)$ does not halt. This was proven by Turing. However, this can be shortly written as $$ \not\exists H \hspace{0.5cm} \forall M,I \hspace{0.5cm} H(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I) \text{ halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$

But is it possible to have the following: $$ \forall M,I \hspace{0.5cm} \exists H\_{M,I} \hspace{0.5cm} H\_{M,I}(M(I)) = \begin{cases} YES, \hspace{0.3cm}M(I) \text{ halts }\\ NO, \hspace{0.4cm} M(I) \text{ doesn not halt}\end{cases}$$

# Answer
> 2 votes
Yes. Given a machine $M$ and input $I$, one of the two things happens:

1. $M(I)$ halts.
2. $M(I)$ does not halt.

We may not be able to predict or compute which of these happens, but one and only one happens simply by rules of *classical* logic.

Now to show that $H\_{M,I}$ exists we consider two cases:

1. If $M(I)$ halts then $H\_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "yes".
2. If $M(I)$ does not halt then $H\_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "no".

Note: we proved existence of $H\_{M,I}$, but we did not give a way of computing $H\_{M,I}$ from $M$ and $I$, which is impossible as that would give us the halting oracle (exercise).

So, what Yuval said.

---
Tags: turing-machines, halting-problem
---


title: Existence of Pseudorandom Generator

text:
# Question
Title: Existence of Pseudorandom Generator
How to show that for $\epsilon\>0$, there exists a function $G:\\{0,1\\}^n-\>\\{0,1\\}^{2^{\epsilon n}}$ that is a $2^{\epsilon n}$-prg, without the condition that is is computable in $2^{O(n)}$ time. What I am trying to show is with high probability, if we take $\epsilon=1/10$, a random $G$ satisfies this condition. But in order to show that, we need to show, no circuits of size $\<2^{3/10n}$ are able to distinguish between uniform distribution of length $2^{n/10}$ and output of $G$. This I am not able to get. Can anyone give me an approach?

# Answer
If you choose $G$ from the uniform random distribution on $\\{0, 1\\}^n \to \\{0, 1\\}^{2^{\epsilon n}}$ without restrictions, then nothing can (correctly) distinguish between the uniform distribution and the output of $G$, because you made it uniformly random by definition. At this point the output of $G$ is no longer pseudo-random, it *is* random.
> 0 votes

---
Tags: randomized-algorithms, pseudo-random-generators
---


# Question
Title: How to generate a number which is divisible by all numbers in a given range?
Suppose I want to find a number that is divisible by all 3 digit numbers (100-999), how do I write a code for that. I know only "1" can divide all 3 digit numbers, but I just want to know the logic.

# Answer
> 3 votes
The number you see is known as the least common multiple.

---
Tags: algorithms
---


title: Loop optimization of non-tail recursion

text:
# Question
Title: Loop optimization of non-tail recursion
When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form:

```
fn F(x):
  if p(x):
    return F(a(x))
  else:
    return b(x)

```

Then it may be written as:

```
fn F(x):
  while p(x):
    x = a(x)
  return b(x)

```

However, I was wondering about how to do this if the recursion is not in tail call position, i.e. the value is modified after the recursive call like this:

```
fn F(x):
  if p(x):
    return h(F(a(x)))
  else:
    return b(x)

```

And I came upon this solution:

```
fn F(x):
  i = 0
  while p(x):
    x = a(x)
    i++
  x = b(x)
  repeat i times:
    x = h(x)
  return x

```

Are those two functions equivalent in functionality? Furthermore, is there a general way to make a recursive function into a loop?

# Answer
> 4 votes
One systematic way to analyze these problems is to rewrite the function in continuation-passing style. For our purposes this means that the function takes an extra argument which is another function describing the postprocessing that is to be applied to the returned value. Your third function `F` in continuation-passing style would look like

```
fn F(x, k):
  if p(x):
    return F(a(x), k ∘ h)
  else:
    return k(b(x))

```

where ∘ denotes function composition. Note that `F` is now tail recursive.

You can then look for alternate (more efficient) representations of the continuation argument. In this case, the continuation always has the form $k\_0\circ h\circ\cdots\circ h = k\_0\circ h^i$ where $k\_0$ is the continuation passed by the external caller. This can be represented by two arguments, $k\_0$ and $i$:

```
fn F(x, k0, i):
  if p(x):
    return F(a(x), k0, i+1)
  else:
    x = b(x)
    repeat i times:
      x = h(x)
    return k0(x)

```

If you convert this to an iterative function in the usual way, and assume the caller always passes the identity function and zero for the second and third arguments, you get your iterative version of the function.

Usually you won't find such a concise encoding for the continuation. But quite generally the continuation will either be the original continuation, or one of a finite number of other functions that contains the previous continuation as a free variable (and possibly some other free variables). You can represent this as an array with one element for each "level", each element being a function number and the values of the non-continuation free variables. When you recurse downward you push another element, and when you return upward you pop an element. This gets you a stack-array-based iterative algorithm with the same space and time complexity as the original algorithm, but probably better constant factors.

---
Tags: optimization, recursion, functional-programming, tail-recursion
---


# Question
Title: What's the accurate definition of a compiler?
Wikipedia:

> In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).

This implies that the compiler can also convert from a low-level language to a high-level language. But this has also got a specific name decompiler.

So what should be the definition for a compiler? 1) or 2)?

1. In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language).
2. A compiler is a computer program that translates computer code written in a high-level programming language into a low-level language.

# Answer
As the comment points out, there's not a formal definition for "compiler", instead it's understood to be that program which translates source code into the target language. Both definitions given are adequate. The definition in Wikipedia is a good one:

> In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language). The name "compiler" is primarily used for programs that translate source code from a high-level programming language to a lower level language (e.g., assembly language, object code, or machine code) to create an executable program.
> 2 votes

# Answer
Mr Raut. I did some research on your question and here is what I found:

“\[A compiler is \] Computer software that translates (compiles) source code written in a high-level language (e.g., C++) into a set of machine-language instructions that can be understood by a digital computer’s CPU. \[...\] Some compilers translate high-level language into an intermediate assembly language, which is then translated (assembled) into machine code by an assembly program or assembler. Other compilers generate machine language directly. ”

I found this on Encyclopaedia Britannica (https://www.britannica.com/technology/compiler). This implies that #2 is the preferred answer.
> 0 votes

---
Tags: compilers
---


# Question
Title: How to tell if a minimax search tree is computationally feasible using parallel computing
I am trying to apply the minimax algorithm to a game of Pokemon. This is a problem where the search tree is usually around 20 levels deep (number of turns) and each level has 9 or less branches (number of choices per turn). What I am wondering is if this is a computationally feasible problem using parallel computing? My idea for how to tackle it is to fork a new thread for the first n number of levels to break up the work.

If my math is correct this means that there will be 9^20 operations that need to be split up (technically it will be less since the number of choices per turn decrease as the game gets closer to the end). I was wondering if there is some sort of constant or general rule of thumb I can use to quickly estimate if this problem is computationally possible and worth pursuing or not?

The most ideal outcome would be if the computation can run in 2 minutes or less, but it isn't a requirement.

# Answer
> 1 votes
Plainly, evaluating $10^{19}$ positions is not going to be feasible in 7200 seconds. But if you use alpha-beta to prune the search tree and have perfect move ordering you can get that down to around $10^{10}$, a number that looks much more reasonable given that chess engines on PC hardware can do a couple million nodes per second easily. Since alpha-beta is a serial algorithm, you'll have to do more than just naively divide the search tree among processors to reap its benefits, but there has been a great deal of research in this area: start here.

# Answer
> 0 votes
It's a straightforward Fermi estimate: if you spend one microsecond of CPU time on each node of the tree, and if you visit $9^{20}$ nodes of the tree, then the computation will take about $9^{20} \times 10^{-6}$ CPU-seconds. If you have 10 CPUs, divide by 10 to get the elapsed time. I'll let you plug that into a calculator and formulate the appropriate conclusion.

---
Tags: parallel-computing, minimax
---


# Question
Title: Converting Moore to Mealy When first Node has Output
This is a homework question, which I am able to do, except my teacher failed to mention what to do when the very first node has a 1 output. I've looked through online examples, and I'm sure this has a very simple answer, but I cannot figure out what the convention would be.

On the left, we have a Moore Machine. It's first node outputs 1. Ok, no problem. But when I convert this to a Mealy, the only time q1 outputs 1, is when being traversed from q2.

But if it's the first node, it should be outputting when the whole thing begins (on lambda) AND when being traversed from q2.

I had two theories, one-- I make a new beginning node, or, I actually put λ/1 on the entry arrow/line (which I have not seen done in any example). But I'd rather not guess my way through this otherwise simple operation.

# Answer
Answering my own question like a silly person:

Ok, I learned what I was missing. A Mealy Machine cannot handle a lambda as I thought it could. As a result, my question has no real answer. Things do NOT output at the first node. Only the first traversal after the first node has any real meaning.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Are all NP-complete languages downward self-reducible?
Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we can use this fact together with the Cook-Levin theorem to prove that all NP-complete languages are downward self-reducible.

# Answer
Recall the (downward) self-reduciblity of a language.

> A language $L \in \mathrm{NP}$ is self-reducible if for every verifer $V$ for $L$, there is a polynomial-time Turing machine $M$ such that for any oracle $O\_{L}$ deciding $L$, and any $x \in L$, we have $V(x, M^{O\_{L}}(x)) = 1$.

The book gives a proof of the self-reduciblity of SAT. The idea for proving the self-reduciblity of all the $\mathrm{NP}$-complete language is similar.

Given an $\mathrm{NP}$-complete language $L$ and its verfer $V$, suppose that $L\_{V}$ is the language of $V$. For every string $w \in \Sigma^{\*}$, we define $L\_{w} = \\{ z = x \Vert w : \exists u \in \Sigma^{\*}, (x, w\Vert u) \in L\_{V} \\}$. Clearly, $L\_{w} \in \mathrm{NP}$. Since $L \in \mathrm{NP}\text{-complete}$, there exists a Karp reduction $f$ such that $$z \in L\_{w} \Leftrightarrow f(z) \in L$$ Assume we have an oracle $O\_{L}$ deciding $L$. Now we design an algorithm that, given $x \in L$, finds $w$ with $(x, w) \in L\_{V}$. Say the length of $w$ (given $x$) is $n = \mathrm{poly}(|x|)$. The algorithm proceeds as follows:

```
For i = 1 to n do:
    Set b[i] = 0;
    Set w = b[1]b[2]...b[i];
    If f(xw) is not in L (We run this step using our oracle for L)
        Set b[i] = 1;
    End if;
End for;
Return w;

```

Indeed, $w$ is a witness of $x$, i.e. $(w, x) \in L\_{V}$. And this algorithm runs in polynomial time.

Other languages in $\mathrm{NP}$ (that are not $\mathrm{NP}$-complete) may be self-reducible as well. An example is given by graph isomorphism, a language that is not known (or believed) to be in $\mathrm{P}$ or $\mathrm{NP}$-complete. On the other hand, it is believed that not all languages in $\mathrm{NP}$ are self-reducible.
> 1 votes

---
Tags: complexity-theory, np-complete
---


# Question
Title: How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$
I try to find tree height such that first i define: $H(n,k)=H(\frac{n}{2},k)+H(n,\frac{k}{4})+1$ then find height of left branch of tree=logn & right branch of tree=logk,but now why height of tree is equal to logk+logn?i guess height of tree is Max(logn,logk)why my geuss is not true?

# Answer
> 1 votes
Here is a recursive definition of a height of a tree $T$:

* If $T$ is a leaf, then its height is 0 (some people prefer to use 1).
* Otherwise, the height of $T$ is the maximum height of any of its children, plus 1.

Equivalently, the height of a tree is the maximum length of a root-to-leaf path (in edges; if you measure it in vertices, leaves should have height 1).

This makes it clear that the correct recurrence for the height is $$ H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1, $$ with an appropriate base case. The solution is roughly $\max(\log\_2 n, \log\_4 k)$, depending on the base case.

---
Tags: trees, recurrence-relation
---


title: Is there code below microcode?

text:
# Question
Title: Is there code below microcode?
Which is the lowest level of code (human written instruction for computers) in computer architecture? After doing minor research, I have come to the conclusion that, as far as determining a hierarchy in terms of the level of computer code, the following is the general level of code hierarchy: High-Level-\>Low-level-\>Assembly-\>Machine Code-\>Micro Code.

Am I correct?

If I am correct, is there a level of code below Micro code?

Is hardware control (in logical gates and transistors) code?

# Answer
> 4 votes
> Am I correct?

**Not completely**

It is wrong for 2 reasons:

1. Assembly code is just a human readable version of machine code. So the conversion process to assembly can be skipped if is not required. Unlike other codes, assembly directly corresponds to machine code. Assembly code is dependent on the Instruction Set Architecture of the machine. Converting to assembly is done by the assembler and it is optional. Machine code can be produced without the intermediate assembly code conversion step. As far as hierarchy is concerned, the assembly code and machine code are at the same level.
2. Machine code is not at a level above Micro code for 2 reasons:
    1. Not all architectures are microcoded. So microcode is optional.
    2. Microcode is **independent** of the machine code. Machine code corresponds to **what** the machine does. Micro code corresponds to **how** the machine does it. Machine code corresponds to the Instruction set. Micro code corresponds to the micro architecture of the machine. 2 machines having different microcodes can utilize the same machine code if they share the same instruction set architecture. In fact, Intel corporation sometimes updates the microcode of their processors to patch up vulnerabilities. This is called microcode update. Even after the microcode is updated, the processor can still utilize the same machine code, because the microcode is independent of the machine code. Machine code is **not** converted to micro code. Both microcode and machine code are sequences of bits. While microcode is **optional**, machine code is **essential**.

---

> Is there a level of code below Micro code?

No.

> Is hardware control (in logical gates and transistors) code?

No. Code is a sequence of instructions. Hardware is **not** a sequence of instructions. Hardware is fixed. Code can be modified. Hardware control cannot be reprogrammed, software control can be reprogrammed.

---
Tags: computer-architecture
---


# Question
Title: SICP: applicative or normal order evaluation
I'm trying to solve Problem 1.5 from SICP book. Consider the following definitions:

```
(define (p) (p))
(define (test x y) (if (= x 0) 0 y))
(test 0 (p))

```

The question is, what would happen if `(test 0 (p))` is interpreted in **applicative** vs **normal** order.

(Applicative: evaluate all the arguments and then apply the operand. Normal: fully expand the expression and then evaluate it.)

I intuitively feel that the answer must be that one of the two gets into an infinite loop, while the other stops due to the fact that `if` is a special form, which does not evaluate the `else`-branch if the `then`-branch is already evaluated.

**Question is:** will this happen? And which one will not get into an infinite loop and why?

**My reasoning** is the following:

*Applicative:* tries to evaluate all the arguments first.

`(test 0 (p))` evaluates `0` to `0` and `(p)` to `(p)`.

Thus the next step:

`(test 0 (p))` --\> same as above, we are in an endless loop.

*Normal*: fully expands the expression

`(test 0 (p))` --\> expanded to:

`(if (= 0 0) 0 (p))` --\> expanded to:

`(if (= 0 0) 0 (p))` --\> ... (it got in an infinite loop too)

OR: does it stop at this point, because `if` is a special form? (Even though this is true, if we stop now, we did not really expand everything first, as we were supposed...)

# Answer
> 0 votes
This is how I understand it:

```
; Normal
(test 0 (p))
(if (= 0 0) 0 (p)))

```

Normal order continues expanding because it hasn't yet reached an expression with only primitives, which recurses into an infinite loop replacing `(p)` by `(p)`.

```
; Applicative
(test 0 (p))
(if (= x 0) 0 y))
(if (= 0 0) 0 y))

```

Applicative order applies the procedure (the `if` predicate) to the arguments that are the values of its sub-expressions. Because `if` short-circuits, the expression reduces to `#t` before before evaluating sub-expression `y`.

---
Tags: programming-languages
---


# Question
Title: Logic behind choosing the exponent bias as $2^7 -1$ instead of $2^7$ in $32$ bits IEEE-754 floating point representation
The $\text{IEEE-754}$ uses $32$ bits to represent single precision floating point numbers. The partitions of the register are as follows:

```
        Biased
 sign  Exponent  Mantissa
+-----+--------+---------+
|1 bit| 8 bits | 23 bits |
+-----+--------+---------+

```

Now in general $8$ bits can represent $2's$ complement numbers in the range $-2^7$ to $2^7 -1$. Now the bias is added to aid in comparison purposes. In general to make the entire range non negative we can add a bias of $2^7$ to the exponent so that the range becomes $0$ to $2^8 -1$. But again the IEEE uses implicit normalization of mantissa as a result of which we need explicit representation of $0$ or $\pm \infty$. So biased exponent $E'=0$ or $255$ is reserved for this purpose.

So we have,

$$1 \leq E' \leq 254$$ $$\implies 1 \leq E+127 \leq 254$$ $$ ,\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{(where E is the actual exponent)}$$ $$\implies -126 \leq E \leq 127$$

But had we used a bias of $128$ instead of $127$ then after reserving $E'=0 \text{ or } 255$

We would have got $$ -127 \leq E \leq 126$$

So my question is, Is there any technical reason for choosing $2^7-1$ instead of $2^7$ or it is just a convention followed by IEEE? Because using the bias of $128$ we could as well allow the required reservation for the special numbers, I see that the only difference comes in the range of the exponent, which shall become $\[-127,126\]$ instead of $\[-126, 127\]$

# Answer
Jerome T. Coonen, "An Implementation Guide to a Proposed Standard for Floating-Point Arithmetic," *Computer*, Vol. 13, No. 1, January 1980, pp. 68-79

provides the following rationale:

> Because of the care taken in the treatment of Underflows, the range of normalized numbers in *single*, *double*, and *quad* formats has been chosen to diminish slightly the risk of Overflow compared with the risk of Underflow. This was done by picking the exponent bias and alignment of the binary point in the significant digit field in such a way that the product of the largest and smallest positive normalized numbers is roughly 4 in each of the basic formats.

David Stevenson, "A Proposed Standard for Binary Floating-Point Arithmetic," *Computer*, Vol. 14, No. 3, March 1981, pp. 51-62

provides a somewhat different but related reasoning:

> For the 32-bit format, precision was deemed the most important criterion, hence the choice of radix 2 instead of octal or hexadecimal. Other characteristics include not representing the leading significand bit in normalized numbers, a minimally acceptable exponent range which uses eight bits, and an exponent bias which allows the reciprocal of all normalized numbers to be represented without overflow.

David Goldberg, "What Every Computer Scientist Should Know About Floating-Point Arithmetic", *ACM Computing Surveys*, Vol. 23, No. 1, March 1991, pp. 5-48

combines the above two explanations as follows:

> Referring to Table 1, single precision has *e*max = 127 and *e*min= -126. The reason for having |*e*min| \< *e*max is so that the reciprocal of the smallest number (1/2*e*min) will not overflow. Although it is true that the reciprocal of the largest number will underflow, underflow is usually less serious than overflow.
> 3 votes

---
Tags: floating-point
---


# Question
Title: For every $\mathrm{NP}$ language $L$, is there a verifier such that, for all the certificates $u$ of other verifiers of $L$, it accepts $(x, u)$?
Let $L$ be an $\mathrm{NP}$ language. Then there exists a verifier $V$ of $L$ and a polynomial $p\colon \mathbb{N} \to \mathbb{N}$, such that for every $x \in \Sigma^{\*}$, $x \in L$ if and only if there exists a certificate $u \in \Sigma^{p(|x|)}$ for $x$ satisfying $V(x, u) = 1$.

Suppose that $\mathcal{V}\_{q}$ be all the verifiers of $L$ such that the length of the certificates of $x$ is $q(|x|)$. And for every $V \in \mathcal{V}\_{q}$, let $V\_{x}$ be all the certificates of $x$.

For every polynomial $q\colon \mathbb{N} \to \mathbb{N}$ satisfying $\mathcal{V}\_{q} \neq \varnothing$, I want to know whether there is a verifier $\bar{V} \in \mathcal{V}\_{q}$ such that for every $x \in L$, $$\bar{V}\_{x} = \bigcup\_{V \in \mathcal{V}\_{q}} V\_{x}.$$

# Answer
> 1 votes
Fix $x \in L$ of length $|x|=n$. Suppose that $\mathcal{V}\_q \neq \emptyset$, and let $m = q(n)$. Choose some $V^0 \in \mathcal{V}\_q$. For any $s \in \\{0,1\\}^m$, let $V^s(y,u) = V^0(y,u \oplus s)$ for inputs of length $n$ and witnesses of length $m$, $V^s(y,u) = 0$ for inputs of length $n$ and witnesses lengths different from $m$, and $V^s(y,u) = V^0(y,u)$ otherwise. Then $V^s$ is a verifier for $L$ for all $s$, and so $\bigcup\_{V \in \mathcal{V}\_q} V\_x = \\{0,1\\}^m$.

This means that if a verifier $\bar{V}$ exists, then $\bar{V}\_x$ is the set of all strings of length $q(|x|)$. This means that $\bar{V}$ need not consult its witness, showing that $L \in \mathsf{P}$.

---
Tags: complexity-theory, np
---


# Question
Title: What is the difference between Hamming Distance and Manhattan Distance for non-binary data?
What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference in the and x and y directions but doesnt hammming distance do the same thing?

# Answer
> 2 votes
The Hamming distance between two length-$n$ vectors is the number of coordinates in which they differ. I've only ever seen it on finite alphabets, i.e. vectors in $\Sigma^n$ where $|\Sigma|\in \mathbb{N}$. In theory there is no problem with extending this to $\mathbb{R}$, but you may have to be careful with how you use equality of floats for instance.

Specifically over $\mathbb{R}^2$, if we consider $x=(x\_0,x\_1)$ and $y=(y\_0,y\_1)$: $$\begin{cases} dist\_\textsf{Manhattan}(x,y)=|x\_0-y\_0|+|x\_1-y\_1|\\ dist\_\textsf{Hamming}(x,y)=\delta\_{x\_0,y\_0}+\delta\_{x\_1,y\_1}\end{cases}$$

Where $\delta\_{a,b}=\begin{cases}1 \text{ if }a\neq b \\0 \text{ otherwise}\end{cases}.$

The two coincide in $\\{0,1\\}^n$, because in that case we have $\delta\_{a,b}=|a-b|$.

---
Tags: algorithms, hamming-code, definitions, hamming-distance
---


# Question
Title: If $f(n)=n^a$ for a given $a>0$, find $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$
If $f(n)=n^a$ for a given $a\>0$, I need to find a function $g(n)$ such that $f(n)\notin O(g(n))$ and $f(n)\notin \Omega (g(n))$.

I am not sure how to find such function, which satisfies both of the conditions.

# Answer
For given $a\>0$ and $f(n)=n^a$ we consider $$g(n)= \begin{cases}{} n^{a+1}, & n=2k\\ 0, & n=2k-1 \end{cases}$$ for $k\in \mathbb{N}$
> 1 votes

---
Tags: complexity-theory
---


title: Optimise the size of union of sets

text:
# Question
Title: Optimise the size of union of sets
We consider a set of sets $S = \\{S\_1, S\_2, \dots, S\_n\\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S\_i$ included with a penalty for each set included. We can represent this problem as the optimisation of the following quantity:

$I = argmax\_{I} |\cup\_{S\_i \in I} S\_i| - |I|$

What would be an efficient way to solve this optimisation problem?

We know from the inclusion-exclusion principle that the union of sets can be expressed as follows:

$|S\_{i\_1} \cup \dots \cup S\_{i\_k}| = \sum\_{j=1}^{k} (-1)^{j+1} \sum\_{1 \leq l\_1, \dots, l\_j \leq k} |S\_{l\_1} \cap \dots \cap S\_{l\_j}|$

# Answer
Your problem is NP-hard. Given an instance $T\_1,\ldots,T\_n$ of Maximum Coverage, let $x\_1,\ldots,x\_n$ be new variables, and create an instance $S\_1,\ldots,S\_n$ of your problem, where $S\_i = T\_i \cup \\{x\_i\\}$. We have $$ \left| \bigcup\_{i \in I} S\_i \right| -|I| = \left| \bigcup\_{i \in I} T\_i \right|. $$

On the positive side, consider the following greedy algorithm: $I\_0 = \emptyset$, and for $k = 1,\ldots,n$, $I\_k$ is obtained from $I\_{k-1}$ by adding the set which maximizes the total number of elements covered by sets in $I\_k$. It is known that for $k \in \\{0,\ldots,n\\}$, the set $I\_k$ found by the greedy algorithm has the following property: for all sets $J\_k$ of size $k$ we have $$ \left| \bigcup\_{i \in I\_k} S\_i \right| \geq (1-1/e) \left| \bigcup\_{i \in J\_k} S\_i \right|. $$ In particular, if the optimal solution to your problem has size $k$ and objective value $O$, then $$ \left| \bigcup\_{i \in I\_k} S\_i \right| \geq (1-1/e)(O + k), $$ and so $$ \left| \bigcup\_{i \in I\_k} S\_i \right| - k \geq (1-1/e) O - k/e. $$ The minimal optimal $k$ satisfies $O \geq k$ (each set adds at least one new element), and so $(1-1/e) O - k/e \geq (1-2/e) O$. This shows that the greedy algorithm (more explicitly, finding $k$ which maximizes $|I\_k|-k$) gives a $1-2/e$ approximation to your problem (this can probably be improved).
> 2 votes

---
Tags: algorithms, optimization, search-algorithms
---


title: Maximum profit by two parameters

text:
# Question
Title: Maximum profit by two parameters
Suppose we have two markets. Each market has various **buy** & **sell** orders that we can **sell to** or **buy from** respectively. Each order represents a specific **number** of a particular **item type** that someone is selling or buying for a specific **price per item** and we can buy/sell any amount of items from/to any order. Each item type has its own **volume per item** (m3).

We have transportion that can transport a specific amount of **volume** and some **budget amount**.

Our goal is to form such transport cargo load of items that would maximize our profit by going from station `A` to station `B` assuming our limited cargo capacity and budget.

The algorithm I'm using is the following:

1. Sort **sell** orders of the **source station** by `price_per_item` in ascending order and group them by `item_type`.
2. Sort **buy** orders of the **destination station** by `price_per_item` in descending order and group them by `item_type`.
3. For each item type, form pairs of sell-buy orders based on the `amount` available in both markets (e.g. `[Item, Quantity, Buy At, Sell At]: [Apple, 25, 50, 75], [Apple, 5, 50, 70], [Apple, 20, 60, 70]`)
4. Perform one of the following actions based on user input:
    * **(A)** Sort pairs by **profit per m3** (`sell_price - buy_price / volume_per_item`) in descending order.
    * **(B)** Sort pairs by **profit / buy price** ratio (`(sell_price - buy_price / volume_per_item) / buy_price` in descending order.
5. Take as many items as possible from each pair of the sorted list until either `budget = 0` or `cargo_capacity = 0` or there are no pairs left.

When using option **(A)**, the described algorithm doesn't take the budget into account while forming the list of most profitable pairs so it gives poor results with a limited budget. When the budget is high, due to the variety of the market the following algorithm uses a full budget amount while cargo space is usually almost empty (which I don't consider the acceptable result as I need to mitigate risks of losing cargo and having large losses due to low ROI).

When using option **(B)**, the gives good profit compared to the amount used to buy the items but it doesn't utilize available budget efficiently.

**So the task is to maximize `total_profit / total_buy_price` ratio while utilizing available `budget_amount` and `cargo_capacity` as much as possible.**

Does this fall under some type of mathematical problem that can be solved in a mathematical way, and if so, can you suggest some sources to read up on in detail? Thanks.

# Answer
If you are handling only one truck/cargo in your problem, then this is a typical **Knapsack** problem. If you are handling the bigger problem of distributing all items on how many trucks, then it is a variant of **Bin Packing** problem. Both problems are **NP-Complete**, however **Knapsack** has approximate algorithms with guaranteed bounds from optimality.

I suggest you use a somehow mangling compromise between **A** and **B**:

1. Solve using **A**, then solve using **B** and take the best answer.
2. Do both sortings, keep 2 arrays, then at each step compare **A** choice to **B** choice and select the better choice (**greedy approach**)
3. Assign a weight to each factor then sort an array **C** according to your weight function. If you don't know the weights then make it equal (half for each factor). If you value price more make its weight above `0.5` if you value volume more then give it a higher weight. This is called **multiplicative weight**
> 1 votes

# Answer
this is an eve online question hahaha just take the profit per item and divide it by it's size and sort descending then fill in your cargo with as much as you can this way you hit both in the same time
> -1 votes

---
Tags: algorithms
---


# Question
Title: Relationship between Kleene Star of a subset of regular language and the regular language
If $L(R\_1) \subseteq L(R\_2) \subseteq L(R\_3)$ then $L(R\_1)^\* \subseteq L(R\_2)^\* \subseteq L(R\_3)^\*$. Does this also imply that $L(R\_1)^\* \subseteq L(R\_3)$?

# Answer
> 1 votes
Of course not: Consider R1='a', R2='a|b', R3='a|b|c', for instance.

---
Tags: regular-languages, regular-expressions, closure-properties, kleene-star
---


# Question
Title: An algorithm for effecient resource redistribution
For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each. How do I achieve the new target levels in as few truck shipments as possible?

Or given an array A{250, 150, 45, 205, 350}, how can it be transformed to {200, 200, 150, 320, 130} in as few transfers as possible? Moving 50 from A\[0\] to A\[1\] would be an efficient first move.

I'm sure I could muddle through this and come up with something, but I'm also sure this problem has already been solved by people smarter than me. And it's important to me that it be correct and as efficient as possible. This is a little outside my normal work, and I'm not sure how to search for something like this (I couldn't find anything).

Thanks much!

---

Update: An initial thought ... find the warehouse with the biggest deficit, then find the one with the biggest (or closest matching?) surplus, do the shipment, then repeat. Seems like that would work, but I'm not sure if there's a more elegant or efficient solution. I'll add an answer once I've got the code working.

# Answer
> 2 votes
There is no polynomial-time algorithm unless $\mathsf{P}=\mathsf{NP}$. Here is a proof.

Let $d\_1, d\_2, \cdots, d\_n$ be the change for each warehouse to reach its target level. For the example in the question, they are $200-250=-50$, $\ 200-150=50$, $\ 150-45-150=105$, $\ 320-205=115$, $\ 350-130=-220$. We assume that sum of all $d\_i$'s is 0; otherwise, it is not possible.

---

Proposition: The target levels can be reached in less than $n-1$ steps if and only if there exist some $d\_i$'s but not all of them whose sum is $0$.

Proof.

* "$\Leftarrow$". Suppose, WLOG, $d\_1+d\_2+\cdots+d\_k=0$ for some $1\le k\lt n$. Suppose $k\ge2$. Then we can find $d\_i\le0\le d\_j$ for some $1\le i,j\le k$. We can transfer $\min(-d\_i, d\_j)$ fish from warehouse $i$ to warehouse $j$. Then either warehouse $i$ or warehouse $j$ reaches its target level. Now we can apply math induction.
* "$\Rightarrow$". Suppose the target levels can be reached in some $k$ steps, $k\lt n-1$. At most $k+1$ warehouses are involved in those $k$ steps. The sum of changes for those warehouses must be 0. Note that $k+1\<n$. $\checkmark$.

---

Let us consider the following warehouse-distribution problem, which is an easier version of the original warehouse-distribution problem.

> Given $n$ warehouses with some fish and their target levels of fish, can we use less than $n-1$ transfers to reach their target levels?

Let us recall, as explained in the Wikipedia article subset sum problem, it is $\mathsf{NP}$-hard to decide, given a multiset of integers, whether there is a non-empty subset whose sum is zero. Given a multiset of integers $f\_1, f\_2, \cdots, f\_n$, we can construct the following instance of warehouse-distribution problem. Let $f=\sum\_{i=1}^n|f\_i|$. Let $n+1$ warehouses have $g\_1, g\_2, \cdots, g\_{n+1}$ fish respectively, where $g\_1=f+f\_1$, $g\_2=f+f\_2$, $\cdots$, $g\_n=f+f\_n$ and $g\_{n+1}=nf-\sum\_{i=1}^nf\_i$. The target for each warehouse is $f$ fish. We can verify easily, thanks to the proposition above, that we can use less than $n$ transfers to reach all target levels if and only if there is a non-empty sub-multiset of all $f\_i$'s whose sum is zero. Hence, the warehouse-distribution problem is at least as hard as the subset sum problem.

---

Since a polynomial-time algorithm is unlikely, let me give an algorithm of time-complexity about $O(n2^n)$.

1. Compute the changes, $d\_1, d\_2, \cdots, d\_n$.
2. For each subset $S$ of $\\{1,2,\cdots, n\\}$, compute $\sigma(S)=\Sigma\_{i\in S}d\_i$. When $\sigma(S)=0$ and $S$ is non-empty, $S$ will be called a zero-set.
3. For each subset $S$, let $p(S)$ be the biggest number of disjoint subsets of $S$ that are zero-sets. $p(\emptyset)=0$. For non-empty $S$, use the following recurrence relation to compute $p(S)$. A proof of the recurrence relation is given later. $$p(S) = \begin{cases} \max\_{a\in S} p(S\setminus\\{a\\}) & \text{if }S\text{ is not a zero-set} \\ 1 + \max\_{a\in S} p(S\setminus\\{a\\}) & \text{if }S\text{ is a zero-set} \\ \end{cases}$$ where $S\setminus\\{a\\}$ means $S$ without $a$.
4. The answer is $n-p(\\{1,2,\cdots,n\\})$.

---

First, for any subset $S$, we have $$\max\_{a\in S} p(S\setminus\\{a\\})\le p(S)\le 1 + \max\_{a\in S} p(S\setminus\\{a\\}).$$

Suppose $S'$ is a subset of $S$. Since any disjoint subsets of $S'$ can be considered as disjoint subsets of $S$, we have $p(S')\le p(S)$. In particular, for any number $a\in S$, we have $p(S\setminus\\{a\\})\le P(S)$.
Suppose $S\_1, S\_2, \cdots, S\_{p(S)}$ be some disjoint subsets of $S$ that are zero-sets. Let $a\in S\_1$. Then $S\_2, S\_3, \cdots, S\_{p(S)}$ are also disjoint subsets of $S\setminus\\{a\\}$, i.e., $P(S)=1+(P(S)-1)\le 1+ p(S\setminus\\{a\\})$. $\quad\checkmark$.

Now, Let me explain the recurrence relation in the step 3 above.

There are two cases.

* $S$ is not a zero-set.

Suppose $S\_1, S\_2, \cdots, S\_{P(S)}$ are disjoint subsets of $S$ that are zero-sets. If the union of all these subsets is $S$, then $S$ must a zero-set as well, which is not true. So there is a number $a\in S$ that is not in any of $S\_1, S\_2, \cdots, S\_{P(S)}$. That means all of $S\_1, S\_2, \cdots, S\_{P(S)}$ are subsets of $S\setminus\\{a\\}$. That is, $P(S) \le P(S\setminus\\{a\\})$. So, $p(S) = \max\_{a\in S} p(S\setminus\\{a\\}).$
* $S$ is a zero-set.

Let $a\in S$. Suppose we have disjoint subsets $S\_1, S\_2, \cdots, S\_d$ of $S\setminus\\{a\\}$ that are zero-sets. Let $S\_{d+1}$ be all the numbers in $S$ but not in any of those subsets. $S\_{d+1}$ contains $a$. $S\_{d+1}$ is also a zero-set since $\sigma(S\_{d+1})=\sigma(S)-\sigma(S\_1)-\sigma(S\_2)-\cdots-\sigma(S\_d)=0$. Since $S\_1, S\_2, \cdots, S\_{d+1}$ are disjoint subsets of $S$ that are zero-sets, $p(S) \ge 1 + d$. That means, $p(S)\ge 1 + \max\_{a\in S} p(S\setminus\\{a\\}).$ So, $p(S) = 1 + \max\_{a\in S} p(S\setminus\\{a\\}).$ $\quad\checkmark$.

# Answer
> 1 votes
This is just a rephrasing John L.'s excellent answer in layman's terms in case someone else comes to this and has trouble working through the proof like I did.

The key information we need to work with is the difference between the starting level and the finish/target level for each warehouse. d1,d2,...,dn. Also, the problem assumes that the start and finish total levels must match (ie. the sum of their differences should be zero).

k = # of steps (shipments). n = number of warehouses. For any given surplus/deficit pair (-di,dj),a shipment always results in *one* of them meeting their target level. So the maximum number of steps is n-1.

We only get less than n-1 steps if there are some subsets of warehouses that have perfectly matching surplus/deficits (ie. subsets of differences whose sum is zero). eg. {{8,-8},{-9,7,2}}. n = 5, but k=3.

So the best solution is the one that picks the maximum number of disjoint subsets that sum to zero (aka. zero-sets).

John defined an algorithm above and implemented it here.

The implementation begins with building the sum of the differences for all possible subsets.
And then returns the solution set with the maximum number of zero-sets.

His implementation is much more efficient than the solution that I was building upon that built every possible disjoint subset.

---
Tags: algorithms
---


# Question
Title: Serializable schedules but not view serializable
I know that to check if a given schedule is serializable we can test for either view serializability or conflict serializability. But do serializable schedules exist which are not view serializable?

# Answer
> 0 votes
No. There doesn't exist any serializable schedule which is not view serializable.

---
Tags: databases
---


# Question
Title: What are the implications of Homotopy Type Theory?
I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory.

Can anyone tell me, in functional programming terms or through practical examples, how exactly is HoTT going to change the way we view mathematics, and what are the implications of HoTT on proof assistants? Thanks!

# Answer
> 6 votes
I think the best way to understand why homotopy type theory related stuff is interesting from a computer science perspective is that is a more satisfying account of extensional equality than any prior version. Lots of attempts have been made previously to add extensionality features to type theory that have been missing relative to e.g. set theory, but they often have some kind of caveat to them that is kind of unsatisfying. One might say that HoTT solves these issues because the mathematics is appropriate for a proper computational interpretation of what equality is, and trying to follow orthodox mathematical practice was part of the problem with previous approaches.

So, what is the difference? Traditionally people think of equality as being like an intrinsic property. Two things are equal when they "are *actually* the same" or something. This shows up in approaches to equality wanting to make it computationally irrelevant. There's nothing interesting about a proof that two things are equal, because they just are equal, and the proof has nothing to record.

However, this is not how intensional Martin-löf type theory works, actually. Values of identity type are computationally relevant, and the eliminator only reduces when the value computes to `refl`. So in some sense, it leaves open the possibility that we can have non-trivial proofs that say *how* two things are equal, not just *that* they are equal. It just happens that there are no basic ways in the usual presentation to say how two things are eqal other than 'they just are.' In some ways, induction already introduces at least *open* terms of identity type that do not behave exactly like the 'these two things just *are* equal' term (`refl`). HoTT just wishes to add new closed terms (hence the difficulty with computational behavior).

In some ways, this notion of non-trivial ways of *how* two things are considered equal is no surprise computationally. In type theory we often consider two things 'actually the same' when they really aren't. $λx.x$ is the same as $λy.y$ when we are using the α rule, but they are clearly not exactly the same symbol strings. And we have different collections of rules we may use at any given time to determine which symbol strings we consider 'actually the same;' α vs. α-β vs. α-β-η. So it is clear that 'actually the same' is a fictional idea, not reality.

The thing that most easily allows us to pretend that these technically distinct things are actually the same is decidability. It's easy to test whether two lambda terms are α equivalent, so we don't really need to keep track of *how* they are α equivalent, since we can just test them whenever necessary. Of course, we also need to not be able to tell the difference between α equivalent things anywhere. But then we can just say that α equivalent things are equal via 'they just are.'

But, this doesn't work for extensional equality of things like functions or quotients. It may not be possible to automatically decide that two values of type `T` are related by relation `R` for the purpose of introducing equality in `T/R`. In set theory, this is explained by saying that values of `T/R` are 'equivalence classes' of `T`, but this is not really a sensible explanation computationally, *because* it may not be possible to compute that equivalence class.

Older approaches to adding quotients to type theory generally involve allowing you to prove equality explicitly via `R`, but then maintaining the fiction by throwing away the proof, and making sure no one can ever really ask for it. The HoTT approach is to *not* throw it away. There are actual values of the identity type that contain witnesses of `R`. When we define functions from `T/R`, we give values for inclusions from `T`, say `|x|` and `|y|`. And if `r : R x y`, we also give a case that receives `r`, explaining *how* `|x|` and `|y|` are related, so that we can use it to explain *how* to mediate between their images.

This essentially eliminates careful engineering necessary to avoid undecidable problems for these sorts of constructs, because we aren't just discarding the provided evidence. These content-ful mediations also give richer ways for constructions to 'respect' the equalities of other things, which is useful. The type theories that make all this work have pretty complex engineering of their own, but in a way it seems satisfying to take seriously the idea of computing explanations for *how* things may be interchanged, rather than merely ensuring that no one will care if they *are* interchanged.

A last aspect, and the genuine "homotopy" one arguably, is that it makes sense to consider two things to be equal in actually distinct ways. In fact, it makes sense to consider an actual *single* thing equal to *itself* in distinct ways. This shows up readily in extensional equality *of types*. Traditional equality of types is very intensional; only types defined the same way are equal. But, as long as we have invertible mappings between two types, we could imagine translating things written for one to the other. This is what univalence allows, making types with invertible mappings between them equal.

But, for instance, there are two distinct invertible mappings from `Bool` to itself: the identity function and `not`. So, even though every construction respects these mappings, and we are able to consider them equalities mediating from `Bool` to itself, they are themselves distinct. This suggests a couple things.

1. The essential feature of equality is preservation by all constructions, not that things are exactly the same in exactly one way.
2. It might be interesting to consider other proofs that things are equal to not necessarily be 'the same' proof as every other. For instance, perhaps the multiple ways of β reducing terms with multiple redexes might not be considered exactly the same proof. Of course, if we do want to consider them the same, HoTT also tells us that we can do so by having a non-trivial mediation between different reductions that explains how to reorder the individual reductions (say).

I think it's also reasonable to take the position that these should genuinely be called something different, like "path", while "equality" is reserved for situations where there are mediations 'all the way up', possibly becominge genuinely trivial above some level (although that isn't necessary). But this is a novel and potentially very useful notion of extensionality for types/the universe that was not (to my knowledge) being considered in type theory prior to HoTT.

Definitions that allow you to create types that work this way by fiat (like HITs, mentioned in the other answer) also seem potentially very interesting for programming. For instance, one could define the lambda terms with distinct proofs of β equivalence, although I'm unsure what exactly one would do with them.

# Answer
> 4 votes
I won't lie: I don't understand the homotopy part of homotopy type theory. But I have a decent grasp of Univalence, which is the axiom at the heart of Homotopy Type Theory (HoTT).

The main idea of univalence is that we treat equivalences (essentially, isomorphisms) as equalities. When two types are isomorphic, you have a way to get from one to the other and back, and the round-trip is the identity in both directions. But there's no way to lift *properties* between isomorphic types: if you have a proof that 2 is the only even prime for unary natural numbers, you can't automatically lift the proof of that property to binary natural numbers, even though you can convert 2 back and forth between the formats.

The eliminator for equality (sometimes also called the $J$ axiom) allows you to lift any property between equal things. So if we have an equality for every isomorphism, then we could transport the above property from unary to binary numbers. This is what univalence gives us: an axiomatic way to lift properties over isomorphisms.

The main implications of this are:

* For programming: univalence is specifically about equality types, which are dependent types, so it only really affects dependently typed languages. What it allows us to do in those languages is to write code using efficient data structures, show that those structures are isomorphic to simpler structures, prove things about the simpler structures, and automatically lift those proofs back to the automatic structures.
* For math, it makes formal something that has been implicit for a long time, which is that mathematicians tend to treat isomorphic things as if they were equal. Univalence provides a foundation that justifies this. So it brings the "formalized" math of proof assistants closer to the way mathematicians think of math.

There are also some cool things you can do with univalence. You can define Higher Inductive Types (HITs), where in addition to giving data constructors for inductive types, you give *path* constructors, which are equalities that must hold. When you pattern match, you then have to show that you preserve these equalities.

HITs allow you to do things like "define integers as a natural plus a sign but, but ensure that positive and negative 0 are truly equal.

However, there are some strange consequences to univalence. First, it means that we cannot have $Refl : x \equiv x$ as the sole way to construct an equality proof, because univalence lets us construct equalities between things that are definitely not syntactically identical. This means that univalence is incompatible with "Uniqueness of identity proofs" and axiom $K$. In practice, this means that the rules of dependent pattern matching must be weakened to be consistent with univalence. Jesper Cockx has a whole line of research on how to do this well.

The other problem is that we lose "canonicity" i.e. the idea that every term can be fully evaluated to a value in canonical form. For equality, Refl is the only canonical proof of equality. So this means that when running programs, sometimes we get "stuck" on the use of univalence as an axiom. This makes sense: we basically said "pretend I have a function that transforms isomorphisms into equalities". We never gave that function, so if we try to evaluate code that calls it, we'll get stuck.

The main effort to solve this problem is Cubical Type Theory. Cubical models equality in such a way that canonicity is preserved, but univalence can be proved *as a theorem* in the language. So univalence is now not an axiom, it's an actual function that can be applied.

If you're interested in this more, there are two main resources I'm familiar with. The HoTT Book is the canonical reference. There's also Univalent Foundations in Agda, which is less focused on the homotopy theory, and more on the implications that univalence has for logic. I'm sure there are also more books I'm not familiar with. The Cubical Agda paper is also good.

---
Tags: type-theory, functional-programming, mathematical-foundations, proof-assistants, homotopy-type-theory
---


# Question
Title: Early Deadline First (EDF) scheduling in real-time systems feasibility test proof
I am trying to prove **Theorem 6.2** on page 127 of the book *Real-Time Systems* by *Jane W. S. Liu*: http://www.cse.hcmut.edu.vn/~thai/books/2000%20\_%20Liu-%20Real%20Time%20Systems.pdf

It is based on Early Deadline First(EDF) scheduling.

It says the proof is similar to the proof for **Theorem 6.1** on page 124-126. However, I am still stuck.

Here is what I have so far:

Density of task $T\_j:\ \delta\_j=\frac{e\_j}{\min{\left(D\_j,p\_j\right)}}$

Density of the system: $∆=\sum\_{j=1}^{n}\delta\_j=\sum\_{j=1}^{n}\frac{e\_j}{\min{\left(D\_j,p\_j\right)}}$

$e\_j$ is the execution time for task $T\_j$

$D\_j$ is the deadline for task $T\_j$

$p\_j$ is the period for task $T\_j$

$\emptyset\_j$ is the phase for task $T\_j$

$r\_{j,b}$ is the release time for task $T\_j$ at period $b$

$J\_{j,b}$ is the job for task $T\_j$ at period $b$

$\emptyset\_j=r\_{j,1}$

$r\_{j,b}+p\_j=r\_{j,b+1}$

**THEOREM 6.2.** *A system $T$ of independent, preemptable tasks can be feasibly scheduled on one processor if its density is equal to or less than $1$.*

If $D\_j\<p\_j$ for some $j$, then $∆=\sum\_{j=1}^{n}\frac{e\_j}{\min{\left(D\_j,p\_j\right)}}\le1$ is only a sufficient condition so we can only say that the system may not be schedulable when the condition is not satisfied.

I try to prove the contrapositive just as **Theorem 6.1** on page 124-126. So what I try to prove is that if according to an EDF schedule, the system fails to meet some deadlines, then its density is larger than $1$.

Suppose that the system begins to execute at time $0$. And at time $t$, the job $J\_{i,c}$ of task $T\_i$ misses its deadline. Assume the case that the current period of every task begins at or after $r\_{i,c}$, the release time of the job that misses its deadline. We use $t$ to divide two types of task besides task $T\_i$ as in below figure: 1) tasks with deadline happens before $t$ in the current period just like $T\_f$, 2) tasks with deadline happens after $t$ in the current period just like $T\_k$.

$J\_{i,c}$ misses its deadline at $t$ tells us that any current job whose deadline is after $t$ is not given any processor time to execute before $t$ and that the total processor time required to complete $J\_{i,c}$ and all the jobs with deadlines at or before $t$ exceeds the total available time $t$. So we have

$t\<\left\lceil\frac{\left(t-\emptyset\_i\right)}{p\_i}\right\rceil e\_i+\sum\_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset\_k\right)}{p\_k}\right\rfloor e}\_k+\sum\_{f\neq i,f\neq k}{\left\lceil\frac{\left(t-\emptyset\_f\right)}{p\_f}\right\rceil e}\_f$

then

$t\<\left\lfloor\frac{\left(t-\emptyset\_i\right)}{p\_i}\right\rfloor e\_i+e\_i+\sum\_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset\_k\right)}{p\_k}\right\rfloor e}\_k+\sum\_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset\_f\right)}{p\_f}\right\rfloor e}\_f+\sum\_{f\neq i,f\neq k}\ e\_f}$

And it is

$=\left\lfloor\frac{\left(t-\emptyset\_i\right)}{p\_i}\right\rfloor e\_i+\sum\_{k\neq i,k\neq f}{\left\lfloor\frac{\left(t-\emptyset\_k\right)}{p\_k}\right\rfloor e}\_k+\sum\_{f\neq i,f\neq k}{{\left\lfloor\frac{\left(t-\emptyset\_f\right)}{p\_f}\right\rfloor e}\_f+\sum\_{f\neq k}\ e\_f}$

$\le \left(\frac{t}{p\_i}\right)e\_i+\sum\_{k\neq i,k\neq f}{\left(\frac{t}{p\_k}\right)e}\_k+\sum\_{f\neq i,f\neq k}{{\left(\frac{t}{p\_f}\right)e}\_f+\sum\_{f\neq k}\ e\_f}$

$=t\sum\_{h=1}^{n}\frac{e\_h}{p\_h}+\sum\_{f\neq k}\ e\_f$

$\le t\sum\_{h=1}^{n}\frac{e\_h}{\min{\left(D\_h,p\_h\right)}}+\sum\_{f\neq k}\ e\_f$

$=t∆+\sum\_{f\neq k}\ e\_f$

So I prove up to $t\<t∆+\sum\_{f\neq k}\ e\_f$

but I cannot prove $∆\>1$

# Answer
> 0 votes
I might be too focus on the algebra. I believe I only need to argue or proof a scenario that would give the least density of the system that will fail to meet a deadline. As shown in the figure below, all tasks start at the same time with same period and deadline. For each of period, each task only have time slot D=D1=D2=...=Dn to execute. In other words, they share exactly the same time slot to execute. If density \> 1 then obviously schedule will fail. If the below system has a density of $1^+$(greater than 1 by the smallest amount), then any changes on Di or Pi will only increase the density of the system or make the system feasible.

---
Tags: operating-systems, proof-techniques, scheduling, process-scheduling, real-time
---


# Question
Title: Indistinguishability of exponentially close distributions
Let $D\_{1}$ and $D\_{2}$ be two probability distributions over $n$-bit strings such that the total variation distance between them is $\mathcal{O}\left(1/{2^{n}}\right)$. Given as input a polynomial number of samples from any one of the distributions, the task is to output $1$ if the samples come from the first distribution and $0$ if they come from the second one. I am trying to show that no polynomial-time algorithm (even with bounded error) can do this task.

Intuitively, it should be very clear that two distributions that are exponentially close are indistinguishable. But how do I formalize the intuition?

# Answer
> 2 votes
Here is the key. Let $A \otimes B$ be the distribution corresponding to a sample from $A$ and an independent sample from $B$, and denote total variation distance by $d\_{TV}$. Then

$$d\_{TV}(A\_1 \otimes A\_2, B\_1 \otimes B\_2) \leq d\_{TV}(A\_1,B\_1) + d\_{TV}(A\_2,B\_2)$$

We can see this using the $L\_1$ formula for $d\_{TV}$: \begin{align} d\_{TV}(A\_1\otimes A\_2,B\_1\otimes B\_2) &= \frac{1}{2} \sum\_{x\_1,x\_2} |\Pr\[A\_1=x\_1\]\Pr\[A\_2=x\_2\] - \Pr\[B\_1=x\_1\]\Pr\[B\_2=x\_2\]| \\ &\leq \frac{1}{2} \sum\_{x\_1,x\_2} |\Pr\[A\_1=x\_1\]\Pr\[A\_2=x\_2\] - \Pr\[B\_1=x\_1\]\Pr\[A\_2=x\_2\]| \\ &+ \frac{1}{2} \sum\_{x\_1,x\_2} |\Pr\[B\_1=x\_1\]\Pr\[A\_2=x\_2\] - \Pr\[B\_1=x\_1\]\Pr\[B\_2=x\_2\]| \\ &= \frac{1}{2} \sum\_{x\_2} \Pr\[A\_2=x\_2\] \sum\_{x\_1} |\Pr\[A\_1=x\_1\] - \Pr\[B\_1=x\_1\]| \\ &+ \frac{1}{2} \sum\_{x\_1} \Pr\[B\_1=x\_1\] \sum\_{x\_2} |\Pr\[A\_2=x\_2\] - \Pr\[B\_2=x\_2\]| \\ &= \sum\_{x\_2} \Pr\[A\_2=x\_2\] d\_{TV}(A\_1,B\_1) + \sum\_{x\_1} \Pr\[B\_1=x\_1\] d\_{TV}(A\_2,B\_2) \\ &= d\_{TV}(A\_1,B\_1) + d\_{TV}(A\_2,B\_2). \end{align}

Now let $D^{\otimes n}$ denote $n$ independent samples from $D$. The above inequality shows that $$ d\_{TV}(D\_1^{\otimes m}, D\_2^{\otimes m}) \leq m d\_{TV}(D\_1,D\_2). $$ Let $E$ be the event that your algorithm outputs "$D\_1$". The definition of $d\_{TV}$ guarantees that $$ |\Pr\_{D\_1^{\otimes m}}\[E\] - \Pr\_{D\_2^{\otimes m}}\[E\]| \leq d\_{TV}(D\_1^{\otimes m}, D\_2^{\otimes m}) \leq m d\_{TV}(D\_1,D\_2). $$ Here $\Pr\_D$ denotes that the samples in the algorithm are generated from the distribution $D$.

We deduce that an algorithm with advantage $\delta$ must use at least $\delta/d\_{TV}(D\_1,D\_2)$ samples.

---
Tags: algorithms, probability-theory
---


# Question
Title: When do you use amortized time complexity and when to use unamortized?
This is my guess:

-Use `amortized` because we want to know the "averaged" complexity over `n` operations assuming the operation is going to be used frequently

-Use `unamortized` when you know the operation is going to be used rarely

# Answer
> 1 votes
You can find the motivation for the amortized analysis from this reference:

> The motivation for amortized analysis is that looking at the worst-case time per operation can be too pessimistic if the only way to produce an expensive operation is to "set it up" with a large number of cheap operations beforehand.

Hence, unamortized (asymptotic) analysis means considering time complexity of an algorithm (instead of each operation) when each operation can be counted in constant time.

---
Tags: time-complexity, amortized-analysis
---


# Question
Title: Why is the Mersenne Twister regarded as good?
The Mersenne Twister is widely regarded as good. Heck, the CPython source says that it "is one of the most extensively tested generators in existence." But what does this mean? When asked to list properties of this generator, most of what I can offer is bad:

* It's massive and inflexible (eg. no seeking or multiple streams),
* It fails standard statistical tests despite its massive state size,
* It has serious problems around 0, suggesting that it randomizes itself pretty poorly,
* It's hardly fast

and so on. Compared to simple RNGs like XorShift\*, it's also hopelessly complicated.

So I looked for some information about why this was ever thought to be good. The original paper makes lots of comments on the "super astronomical" period and 623-dimensional equidistribution, saying

> Among many known measures, the tests based on the higher dimensional uniformity, such as the spectral test (c.f., Knuth \[1981\]) and the k-distribution test, described below, are considered to be strongest.

But, for this property, the generator is beaten by a *counter* of sufficient length! This makes no commentary of *local* distributions, which is what you actually care about in a generator (although "local" can mean various things). And even CSPRNGs don't care for such large periods, since it's just not remotely important.

There's a lot of maths in the paper, but as far as I can tell little of this is actually about randomness quality. Pretty much every mention of that quickly jumps back to these original, largely useless claims.

It seems like people jumped onto this bandwagon at the expense of older, more reliable technologies. For example, if you just up the number of words in an LCG to 3 (much less than the "only 624" of a Mersenne Twister) and output the top word each pass, it passes BigCrush (the harder part of the TestU01 test suite), despite the Twister failing it (PCG paper, fig. 2). Given this, and the weak evidence I was able to find in support of the Mersenne Twister, what *did* cause attention to favour it over the other choices?

This isn't purely historical either. I've been told in passing that the Mersenne Twister is at least more proven in practice than, say, PCG random. But are use-cases so discerning that they can do better than our batteries of tests? Some Googling suggests they're probably not.

In short, I'm wondering how the Mersenne Twister got its widespread positive reputation, both in its historical context and otherwise. On one hand I'm obviously skeptical of its qualities, but on the other it's hard to imagine that it was an entirely randomly occurrence.

# Answer
> 11 votes
A recent paper by Vigna starts with an explanation of the history of Mersenne-Twister (MT), and why it has prevailed so far.

> The original paper about the Mersenne Twister was published by Makoto Matsumoto and Takuji Nishimura in 1997 \[22\]. At that time, the PRNG had several interesting properties. In particular, it was easy to build generators with a very large state space, and the largest version with 19937 bits of state became very popular. More importantly, many techniques used in the Mersenne Twister influenced later development, and helped F2-linear techniques to recover from the bad fame that followed the “Ferrenberg affaire”. \[9\]
>
> It is difficult for non-specialists to understand the intricacies of PRNGs, but period is easy to understand: the fact that the sequence generated would not repeat before 219937 − 1 32-bit integers had been emitted was met with enthusiasm, and quickly the Mersenne Twister was adopted as the standard generator in many environments. For example, the stock PRNG of the gcc compiler and of Python, as well of the Maple mathematical computing framework, is some version of the Mersenne Twister

The authors of MT also present the challenges of defining what is a good random number generator in their 2006 paper, Pseudorandom Number Generation: Impossibility and Compromise, which also argues in favour of using Mersenne Twister.

The original MT was not without issues. Perhaps the most troubling is that MT can go into a bad state for 100000s of numbers. This is more or less equivalent to the issue of correlated samples with close seedings. There is not a single MT, and more modern versions, such as Well19937a or Melg19997 have solved this issue.

Regarding state size or equivalently, memory consumption, this is partly an issue (does it make sense to worry about this for modern processors?). One can always use an MT with a smaller period such as Well512a or Well1024a. This period is still very large for practical applications.

Recently, Harase has shown some obvious linear relations present in the original Mersenne-Twister. This is in general less of a practical issue, and has again been addressed by the more recent Well or Melg algorithms.

Finally, while equidistribution looks like a nice property to have, with its connection to quasi Monte-Carlo simulations. It has obvious strong defects, stated in Vigna's paper above, and is not clear if it is desirable at all (see R.P Brent paper).

Good alternatives, although a little bit slower in general (but orders of magnitude faster to skip-ahead), are L'Ecuyer MRG32k3a (or the 53 bits version), or counter-based cryptographic generators such as AES (Intel and AMD processors have specific routine to generate those fast), or Salsa/Chacha possibly with fewer rounds. Some newer generators like Savvidy Mixmax-17, used for particle physics simulations in ROOT, look promising as well.

# Answer
> 23 votes
The initial Mersenne-Twister (MT) was regarded as good for some years, until it was found out to be pretty bad with the more advanced TestU01 BigCrush tests and better PRNGs.

This page lists the Mersenne-Twister features in detail:

## Positive Qualities

* Produces 32-bit or 64-bit numbers (thus usable as source of random bits)
* Passes most statistical tests

## Neutral Qualities

* Inordinately huge period of $2^{19937} - 1$
* 623-dimensionally equidistributed
* Period can be partitioned to emulate multiple streams

## Negative Qualities

* Fails some statistical tests, with as few as 45,000 numbers. Fails LinearComp Test of the TestU01 Crush and BigCrush batteries.
* Predictable — after 624 outputs, we can completely predict its output.
* Generator state occupies 2504 bytes of RAM — in contrast, an extremely usable generator with a huger-than-anyone-can-ever-use period can fit in 8 bytes of RAM.
* Not particularly fast.
* Not particularly space efficient. The generator uses 20000 bits to store its internal state (20032 bits on 64-bit machines), but has a period of only $2^{19937}$, a factor of $2^{63}$ (or $2^{95}$) fewer than an ideal generator of the same size.
* Uneven in its output; the generator can get into “bad states” that are slow to recover from.
* Seedings that only differ slightly take a long time to diverge from each other; seeding must be done carefully to avoid bad states.
* While jump-ahead is possible, algorithms to do so are slow to compute (i.e., require several seconds) and rarely provided by implementations.

**Summary**: Mersenne Twister is not good enough anymore, but most applications and libraries are not there yet.

# Answer
> 20 votes
I am the Editor who accepted the MT paper in ACM TOMS back in 1998 and I am also the designer of TestU01. I do not use MT, but mostly MRG32k3a, MRG31k3p, and LRSR113. To know more about these, about MT, and about what else there is, you can look at the following papers:

F. Panneton, P. L'Ecuyer, and M. Matsumoto, \`\`Improved Long-Period Generators Based on Linear Recurrences Modulo 2'', ACM Transactions on Mathematical Software, 32, 1 (2006), 1-16.

P. L'Ecuyer, \`\`Random Number Generation'', chapter 3 of the Handbook of Computational Statistics, J. E. Gentle, W. Haerdle, and Y. Mori, eds., Second Edition, Springer-Verlag, 2012, 35-71. https://link.springer.com/chapter/10.1007/978-3-642-21551-3\_3

P. L'Ecuyer, D. Munger, B. Oreshkin, and R. Simard, \`\`Random Numbers for Parallel Computers: Requirements and Methods,'' Mathematics and Computers in Simulation, 135, (2017), 3-17. http://www.sciencedirect.com/science/article/pii/S0378475416300829?via%3Dihub

P. L'Ecuyer, \`\`Random Number Generation with Multiple Streams for Sequential and Parallel Computers,'' invited advanced tutorial, Proceedings of the 2015 Winter Simulation Conference, IEEE Press, 2015, 31-44.

# Answer
> 9 votes
Somewhat like sorting algorithms in this regard, there is no "one size fits all" PRNG. Different ones are used for different purposes and there is a wide variety of design criteria and uses. It is possible to misapply PRNGs, such as using one for cryptography that it is not designed for. Wikipedia's entry on Mersenne Twister also mentions that it was not designed for "Monte-Carlo simulations that require independent random number generators".

As noted on Wikipedia, this PRNG is indeed used in a large number of programming languages and applications even as a default PRNG. It would take a near-sociological analysis to explain why one PRNG is favored. Some possible factors that may be contributing to this PRNG:

* The Author has good/ strong scientific credentials in area and has been working in PRNGs for decades.
* It was specifically designed to be superior to other methods at the time.
* The author is engaged in implementations and tracking them, also contributing to them. Some PRNGs are more theoretical and the authors do not always concern themselves with actual implementations.
* The system is well supported/updated on a web page.
* New versions of the PRNG have been developed to deal with weaknesses. There is not one single Mersenne Twister algorithm, its more like different versions and a family of variants which can handle different needs.
* It has been extensively analyzed/tested by standard randomness analysis software and passed, by independent authorities.
* There is a known effect measured with for web sites and many other contexts like scientific citations called "preferential attachment" which can be measured. It's basically where long established historical sources accrue further usage. Such an effect could explain PRNG choices over time.

In other words, you are asking about a phenomenon of "popularity" which is associated and interrelated with human choices and is not strictly tied to particular qualities, but is a sort of complex/emergent property and interplay between different algorithms, users, and environment/usage contexts.

Here is one such independent analysis of the algorithm Mersenne Twister – A Pseudo Random Number Generator and its Variants by Jagannatam (15p). The concluding paragraph is essentially an answer to your question. quoting only the 1st few sentences:

> Mersenne Twister is theoretically proven to be a good PRNG, with a long period and high equidistribution. It is extensively used in the fields of simulation and modulation. The defects found by the users have been corrected by the inventors. MT has been upgraded, to use and to be compatible with the newly emerging technologies of CPU’s such as SIMD and parallel pipelines in its version of SFMT.

# Answer
> 2 votes
I produced now a simple overview of most of the known RNG's, with its speed and quality, based on improved dieharder tests.

https://rurban.github.io/dieharder/QUALITY.html

For TestU01 and PractRand results see the linked https://github.com/lemire/testingRNG overview, but yields the same results. You just need to wait days for the same results.

Best and fastest are: wyrand, xoshiro128+, xoroshiro64\**, xoshiro128++, xoroshiro64\*, lxm, efiix64 plus the slow threefry2x64.

MT comes out as good (1 major weakness), ranked as 10th of the good rng's. Note that the SIMD optimized sfmt comes out as bad, which could point to an implementation error.

---
Tags: algorithms, randomness, sampling, pseudo-random-generators
---


# Question
Title: Algorithm for cyclic $n$-string Hamming distance with constant sized language $\Sigma$
Suppose we are given a language $\Sigma$ where, suppose, $|\Sigma| = O(1)$. Consider two fixed strings $A, B \in \Sigma^n$. Define the Hamming metric between these strings as $$d\_{H}(A,B) = \sum\_{i=1}^n \boldsymbol{1}\lbrace A(i) \neq B(i)\rbrace$$ If we define $B^{(k)}$ as the $k$-shift (to the right) cyclic permutation of $B$, then what I am looking to compute is $$d\_{\text{cyc},H}(A,B) = \min\_{k \in \lbrace 0, \cdots, n-1 \rbrace} d\_H\left(A, B^{(k)}\right)$$ So it is easy to see that we can compute $d\_H(A,B)$ for some length $n$ strings $A$ and $B$ in time $O(n)$, implying a trivial $O(n^2)$ algorithm for $d\_{\text{cyc},H}(A,B)$. So my goal is to see if we can do something better. If someone knows of an algorithm that generalizes to any constant value for $|\Sigma|$, I would be happy to know. For now, I will lay out some of my thoughts.

---

Suppose that $|\Sigma| = 2$, namely that $\Sigma = \lbrace \alpha, \beta \rbrace$. Let us define a map $h: \Sigma \rightarrow \lbrace -1, 1 \rbrace$ where, say, $h(\alpha) = -1$ and $h(\beta) = 1$. If we transform the strings $A$ and $B$ element-wise to strings $A'$ and $B'$ in $\lbrace -1, 1\rbrace^n$, we can then compute all of the $d\_H\left(A, B^{(k)}\right)$ values via a FFT of the concatenated string $B'B'$ and $A'$. We can see this by first considering the computation of $d\_H(A,B)$. Suppose $I\_{=} \subseteq \[n\]$ is the set of indices for characters where $A$ and $B$ are the same and make $I\_{\neq} = \[n\] \setminus I\_{=}$ the set of indices where $A$ and $B$ differ. Clearly $I\_{=}$ and $I\_{\neq}$ are disjoint, so $|I\_{=}| + |I\_{\neq}| = n$. Now let us compute the inner product of $A'$ and $B'$. Any element where $A$ and $B$ have the same character, $A'$ and $B'$ will have the same sign at that element. Any element where $A$ and $B$ differ, the signs will differ as well. Thus we find that $$(A' \cdot B') = \sum\_{i=1}^n A'(i) B'(i) = \sum\_{i \in I\_=} A'(i) B'(i) + \sum\_{i \in I\_{\neq}} A'(i) B'(i) = |I\_=| - |I\_{\neq}|$$ As $d\_H(A,B) = |I\_{\neq}|$ and $(A'\cdot B') = |I\_{=}| - |I\_{\neq}| = n - 2 |I\_{\neq}|$, this implies that we can find $d\_H(A,B)$ to be equal to $$d\_H(A,B) = |I\_{\neq}| = \frac{1}{2}\left(n - (A' \cdot B')\right)$$ Now if $\text{rev}(S)$ reverses a string $S$ of size $n$, implying that $S(i) = \text{rev}(S)(n-i)$, we can observe that if we define the string $C' = \text{rev}(B'B')$, we can find for any $k \in \[n\]$ that \begin{align} v\_k &:= \sum\_{i=1}^n C'((n-k+1)-i)A'(i)\\ &= \sum\_{i=1}^n (B'B')((k-1) + i)A'(i) \\ &= \sum\_{i=1}^n (B')^{(k-1)}(i) A'(i) \\ &= \left((B')^{(k-1)} \cdot A'\right) \\ &= n - 2 d\_H\left( A, B^{(k-1)} \right) \end{align}

This implies doing the convolution of the strings $C'$ and $A'$ give us a mechanism to compute all values for $d\_H\left(A, B^{(k)}\right)$, which can be done in $O(n \log(n))$ time using the Fast Fourier Transform (FFT). This sounds great for the special case that $|\Sigma| = 2$, but I am unsure about an efficient, exact way that generalizes to larger constant values for the size of $\Sigma$.

My initial thought as an approximation is to create, say, an $r$-wise independently family of hash functions $\mathcal{H} := \left\lbrace h: \Sigma \rightarrow \lbrace -1, 1 \rbrace \\,|\\, \forall c \in \Sigma, h(c) = 1 \text{ with prob } 1/2\right\rbrace$ for $r$ at least 2, uniformly sample some $h \in \mathcal{H}$, and then for a string $A \in \Sigma^n$ set $A'(i) = h(A(i))$. If we define the random variable $Y(A,B) = A' \cdot B'$ under this type of transformation, we can find that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum\_{i=1}^n \mathbb{E}\left(A'(i)B'(i)\right) \\ &= \sum\_{i \in I\_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum\_{i \in I\_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \end{align} Consider two characters $a, c \in \Sigma$. If $a = c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)^2) = \mathbb{E}(1) = 1$ since $h(a) = h(c)$. If $a \neq c$, then $\mathbb{E}(h(a) h(c)) = \mathbb{E}(h(a)) \mathbb{E}(h(c)) = 0$. This result implies that \begin{align} \mathbb{E}\left(Y(A,B)\right) &= \sum\_{i \in I\_{=}} \mathbb{E}\left( A'(i)B'(i)\right) + \sum\_{i \in I\_{\neq}} \mathbb{E}\left(A'(i)B'(i)\right) \\ &= |I\_{=}| \\ &= n - |I\_{\neq}| \end{align} Which means that technically we could use the estimator $\hat{d}\_H(A,B) = n - Y(A,B)$. Obviously we could then average across $k$ estimates to minimize variance, but at least initial calculations of the variance of this estimator seem to show that the variance satisfies $\text{Var}(\hat{d}\_H(A,B)) = \Theta(n^2)$, which kind of makes sense because there are hash functions that could completely get things wrong. Like if we happen to choose a hash function such that $h(c) = 1$ for all $c \in \Sigma$, then we will get an estimate that the strings are identical even if the strings have no overlap, e.g. $A = aaa$ and $B = bbb$. Thus, this randomized approach does not seem sound. If anyone has ideas of how things could be modified to improve the concentration properties, I would be happy to hear them!

---

**Edit 1** I made a separate realization on how to proceed with the randomized approach. We know by Markov's inequality that for some constant $c \> 0$ that $$\text{Pr}\left\lbrace \hat{d}\_H(A,B) \geq c d\_H(A,B)\right\rbrace \leq \frac{\mathbb{E}\left(\hat{d}\_H(A,B)\right)}{c d\_H(A,B)} = \frac{1}{c}$$ Now suppose we make $m$ iid estimates for $\hat{d}\_H(A,B)$ and choose the minimum one as being correct. The only way our minimum estimate will be larger than $c d\_H(A,B)$ is if all estimates are larger than this value. Thus, the probability we error is at most $(1/c)^m$. Setting $c = (1 + \epsilon)$ and $m = 2\epsilon^{-1} \ln(1/\delta)$ gives us that with probability at least $1 - \delta$, the minimum of the $m$ estimators is less than $(1 + \epsilon)d\_H(A,B)$. Using this fact, we can generate $m$ iid instances for $A'$ and $B'$ in $O(mn)$ time, use them to compute the necessary FFT data in $O(mn \ln(n))$ time to obtains estimates for the each $d\_H(A, B^{(k)})$ term across all samples, then compute the minimum of each estimate across all $m$ samples in $O(nm)$ time, and then compute the minimum across these final estimates in $O(n)$ time to obtain the estimate for $d\_{cyc,H}(A,B)$.

Putting this all together, setting $\delta = n^{-3}$, we have with probability at least $1 - \frac{1}{n^3}$ that we compute a $(1+\epsilon)$-approximate cyclic string Hamming distance in time $O(\epsilon^{-1} n \text{polylog}(n))$ time when $|\Sigma| = O(1)$.

Note that this is not necessarily great because if we get a bad hash function, we may incorrectly return a cyclic Hamming distance estimate of $0$ because the hash function may think the strings are equivalent. So it would be nice to figure out a way to get an estimate with high probability that is only a small amount less than the true value.

---

**Edit 2** As the above randomized approach was not too good, I went a different approach by considering things from a streaming model type of approach. Suppose we have a stream $S$ where the $i^{th}$ item from the stream is the tuple $(A\[i\], B\[i\])$ from the potentially large strings $A$ and $B$. The idea was to use reservoir sampling to get a $k$-sample of these tokens, form them into strings $A\_k$ and $B\_k$, and then computing the estimate of the cyclic Hamming distance of strings $A$ and $B$ by doing $$\hat{d}\_{\text{cyc},H}\left(A,B\right) = \frac{n}{k} d\_{\text{cyc},H}(A\_k, B\_k)$$

My analysis showed that for $0 \< \alpha \< 1$ that using this approach, we can get a $O(n^{\alpha})$-approximation with probability at least $1 - 1/n^{O(1)}$where the runtime serially is $O\left((n + n^{1-2\alpha} \ln(n))\ln(n)\right)$ and the space requirements are $O\left(n^{1-2\alpha}\ln(n)\ln|\Sigma|\right)$ bits.

# Answer
> 3 votes
Let $\alpha \in \Sigma$ and $d\_{\alpha, H}(A,B) = n - \sum1\\{A(i)=B(i)=\alpha\\}$. Then you can use your FFT technique to compute $d\_{\alpha, H}(A, B)$ for each $\alpha \in \Sigma$. It will take $O(n \cdot \log(n) \cdot |\Sigma|)$ time. So you will have an $|\Sigma| \times n$ table, where you should find a column with a minimum sum, which can be done in $O(|\Sigma| \cdot n)$ time.

---
Tags: algorithms, strings, randomized-algorithms, hamming-distance
---


# Question
Title: Perceptron and non linearly seprable data
I was asked in an interview question, can a perceptron classifier ever reach 100% accuracy on some kind of non linearly seprabale training data in 2D. I said that no it can't because the data is not linearly seprabale. We then proceed to the next question, but maybe its just me, but from the look of the interviewr, I'm not sure that was the right answer. Am I missing something or just paranoid? Can the perceptron reach 100% accuracy on any training data?

Thanks!

# Answer
A single-layer perceptron can only learn linearly separable patterns (with 100% accuracy), as noted in the Wikipedia article on perceptrons. (Advice for the future: check standard references before asking here.)

A multilayer feedforward neural network (sometimes called multilayer perceptron) can learn other patterns.

If someone just says "perceptron", in my eyes it is at least a little ambiguous whether that means a single-layer perceptron or possibly could encompass multi-layer networks.
> 0 votes

---
Tags: machine-learning, perceptron
---


# Question
Title: Data structure and structural relationships
> “Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values, they involve important structural relationship between the data elements.”
>
> Knuth, Art of Computer Programming, vol. 1 (Fundamental algorithms), 3rd edition, p. 252.

My question is what does “structural relationship between the elements” mean. How are these structures different from any mathematical structure?

# Answer
> 1 votes
Your citation is incorrect--this is on page 232 in 3rd edition, not 252 (first paragraph of "Information Structures", chapter 2.1.

Based on having the chapter available, Knuth is talking about data structures in general. I agree the with suggestions above--just ignore this paragraph if it doesn't make sense or seems obvious. I personally agree that it does not seem to define anything or communicate anything clear to me.

# Answer
> 0 votes
Structural relationship between data items deals directly with the architecture of machine under which we are exploring structural relationships so we can say that structural relationship is based on the architecture of machine. If it is a parallel architecture then we have parallel data structures ,if it is a sequential architecture then we have sequential data structures , but here we have mathematical models under which we can explain above types of data structures so we say that we are dealing with a class of structures which is based on architectural structures for exploring structural relationships between the data items.

---
Tags: data-structures
---


title: Given permutation $p$, compute $p^{-2}$

text:
# Question
Title: Given permutation $p$, compute $p^{-2}$
I'm now to problem solving, and I need some help and insight on the following problem from HackerRank:

> Given a sequence $p(1),\ldots,p(n)$ of distinct numbers from $1$ to $n$, find numbers $y\_1,\ldots,y\_n$ such that $p(p(y\_1))=1,\ldots,p(p(y\_n))=n$.

My approach was to perform a double index lookup on each element in the provided input: for each $i \in \\{1,\ldots,n\\}$, I find an index $z\_i$ such that $p(z\_i) = i$, and then an index $y\_i$ such that $p(y\_i) = i$.

Is there a more efficient way to solve this problem?

# Answer
The first step in answering your question is determining the complexity of your algorithm. Determining the index $z\_i$ takes time $\Theta(z\_i)$, and so determining all of $z\_1,\ldots,z\_n$ takes time $\Theta(1+\cdots+n) = \Theta(n^2)$. Determining the $y\_i$ from the $z\_i$ likewise takes $\Theta(n^2)$, which is the running time of your algorithm.

If we are willing to spend memory $O(n)$, then we can improve the running time to $O(n)$. The idea is to notice that $p$ is a permutation, and therefore has an inverse $p^{-1}$, which can be computed easily as follows: go over $i=1,\ldots,n$, and set $p^{-1}(p(i))=i$. Given that, we can simply compute $z\_i = p^{-1}(p^{-1}(i))$.

If you are really short on memory, there are algorithms for inverting a permutation in nearly linear time and small space, see for example Matthew Robertson, Inverting permutations in place. After inverting $p$, you need to square the result $p^{-1}$, which might be achievable using similar techniques (or even easier).
> 2 votes

---
Tags: algorithms, permutations
---


# Question
Title: Big O of multiple variables in a logarithm: is $(2n+m)\log(2n+m) = O((n+m)\log(n+m))$?
I am computing the count of the amount of intersections between disjoint horizontal line segments and disjoint vertical line segments. The algorithm I have come up with runs in $(2n+m)\log(2n+m)$ time. I was wondering if the Big-O for this is $O((n+m)\log(n+m))$? I don't know how constants in the interior of logs with multiple variables could be bounded, if at all. How would I prove this?

# Answer
> 2 votes
Classical way is same as when we consider double limit $\lim\limits\_{(n,m) \to \infty}f(n,m)=A$, which use intention to infinity by squares i.e. for $\forall \varepsilon\>0$ $\exists \delta\>0$ such that for $\forall n \> \delta$ and $\forall m \> \delta$ holds $|f(n,m)-A|\< \varepsilon$. Using maximum norm conception we can write $\left\Vert(m,n)\right\Vert = \max\\{n,m \\}\> \delta$. It is also known **Chebyshev norm** and the **infinity norm** terms for this conception and notation $\left\Vert \cdot \right\Vert\_\infty$. Let me say, that this is same as intention to infinity by rectangles i.e. when we require $\exists \delta\_1\>0, \exists \delta\_2\>0$ and consider $\forall n \> \delta\_1$ and $\forall m \> \delta\_2$.

Applying to big-$O$ we can write that $O(f(n,m)),(n,m) \to \infty$ is set of functions $g$, such, that $\exists C\_g\>0$ and $\exists M\_g\>0$ such that for $\forall \left\Vert (n,m)\right\Vert\_\infty \> M\_g$ holds $g(n,m) \leqslant C\_g f(n,m)$.

In your case $(2n+m)\log(2n+m) \leqslant 2(n+m)\log \[2(n+m)\] \leqslant 4(n+m)\log (n+m)$ using $1+\frac{\log 2}{\log (n+m)} \leqslant 2$, when $n\>1,m\>1$.

For completeness let me also note, that definition from one variable can be expanded to two or multi variables in different ways, for example, we can consider intention to infinity by circles i.e. when we consider $\sqrt{n^2+m^2} \to \infty$. Is known intention to infinity by triangles i.e. $n+m \to \infty $ etc.

# Answer
> 1 votes
The most reasonable definition for big O in several variables is: $f(n,m) = O(g(n,m))$ if there exist $n\_0,m\_0,C\>0$ such that $f(n,m) \leq Cg(n,m)$ for all $n \geq n\_0$ and $m \geq m\_0$. Now you can answer your own question.

As a hint, note that $\log(2n+m) \leq \log(2n+2m) = \log 2 + \log(n+m)$.

---
Tags: asymptotics
---


title: Time complexity of binary search

text:
# Question
Title: Time complexity of binary search
**Proposition**: The binary search algorithm runs in $O(\log n)$ time for a sorted sequence with $n$ elements.

When justifying this claim, first we say that with each recursive call the number of candidate entries still to be searched is given by the value $$ high - low + 1 $$

The middle index, $mid$, is given by $$ mid = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor $$

We say that the number of remaining candidates is reduced by at least one half with each recursive call. Hence the number of remaining candidates, $n$, when we shift our $high$ index to the $(mid - 1)$ index is given by:

$$ n = (mid - 1) - low + 1 $$ $$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - 1 - low + 1 $$ $$ n = \Biggl\lfloor\frac{high + low}2\Biggr\rfloor - low $$ $$ n \le \Biggl\lfloor\frac{high -low + 1}2\Biggr\rfloor $$ This is the part I don't understand how did we get from the equality equation to the inequality equation?

Again, when we are computing the maximum number of recursive calls performed, $r$, we say that $r$ is the smallest integer such that

$$ \frac{n}{2^r} \< 1 $$ So: $$ r \> \log n $$ $$ r = \lfloor \log n \rfloor + 1 $$

Similarly, how did we get from the inequality equation to the equality equation?

Any help will be appreciated to help me understand this proof.

# Answer
Let me start with the first question. Since $\lfloor x \rfloor \leq x$, $$ \left\lfloor \frac{\mathit{high}+\mathit{low}}{2} \right\rfloor - \mathit{low} \leq \frac{\mathit{high}+\mathit{low}}{2} - \mathit{low} \leq \frac{\mathit{high}-\mathit{low}}{2}. $$ To complete the proof, we use the inequality $\frac{x}{2} \leq \lfloor \frac{x+1}{2} \rfloor$, which holds for integer $x$. To see this, notice that for even $x = 2y$, the inequality reads $y \leq y$, and for odd $x = 2y+1$, it reads $y+1/2 \leq y+1$.

Now for the second question. We want to know what is the smallest integer $r$ such that $r \> \log n$. Since $\lfloor x \rfloor \> x-1$, we see that $\lfloor \log n \rfloor + 1 \> (\log n - 1) + 1 = \log n$. On the other hand, since $\lfloor x \rfloor \leq x$, we see that $\lfloor \log n \rfloor \leq \log n$, and in particular, it is not the case that $\lfloor \log n \rfloor \> \log n$. Therefore $\lfloor \log n \rfloor + 1$ is smallest integer $r$ such that $r \> \log n$.
> 1 votes

---
Tags: data-structures, proof-techniques, recursion, binary-search
---