# Question
Title: What is the computational complexity of this problematic code we had
Some of my colleagues introduced some code into our codebase that was causing some serious performance issues. The feature they were implementing involved displaying data in a hierarchical fashion, but if there were more than 20 or so nodes involved, there was a serious delay (multiple seconds) before the user could see their data. And in one of our scenarios, we had around 50 or so nodes, and in that situation it ran for hours before completing.

I had no trouble replacing the code with something sane, that ran on the order of microseconds, but when explaining runtime complexity to the individuals who had created the code, I realized I wasn't sure how to determine the complexity of the algorithm in question.

In JavaScript, the code look something like this:

```
function DoUnspeakableEvil(root, nodes) {
    root.children = [];
    nodes.forEach(function (node) {
        if (node.parentId === root.id) {
            root.children.push(node);
        }
        node.children.forEach(node => DoUnspeakableEvil(node, nodes));
        node.children.sort(/* sort based on one of the fields */);
    });
}

```

In pseudocode:

```
Procedure Inefficient_Tree_Procedure:
    Given the tree's nodes and the root of the subtree
    For each node in the tree:
        If the node's parent id is the id of the subtree root:
            Add the node to the sub tree root's children
        If the root has children:
            For each child of the root:
                Run Inefficient_Tree_Proceedure on child
            Sort the children

Main
    Run Inefficient_Tree_Proceedure on the nodes with the tree's root (known ahead of time) as the root

```

Essentially, what's going on here is that we have an array of nodes, and we're given the member of that array which is the root of our 'tree'. Each node is able to identify its parent. This hierarchical data is usually about 3 levels deep, so on this first pass root.children gets populated with a sizable portion of the nodes. There is no sorcery here either: This poorly designed code runs completely synchronously, so every time it evaluates another node, it recurses on every found child up to that point. It also sorts all of the found children up to that point, each time it evaluates a node.

*** Where I get lost ***

Obviously, iterating over the nodes and finding the ones that are immediate children of the 'root' is a Ө(n) task. Sorting is likely going to be O(n log(n)) (depending on the browser on which we run this, since they all have different implementation strategies and some may use insertion sort for small arrays). Based on my understanding, if the sort and the recursive step weren't erroneously placed inside of the loop, and it did these steps once for each value of 'root', we would be looking at some sort of O(n log(n) log(n)) algorithm. The part that confuses me is the fact that they WERE in fact put in the loop, which means for each root, its going to recurse once a few times, recurse twice a few times, recurse three times a few times, etc... and then do the same with sorting. Sort an array of length 1 a few times, sort an array of length 2 a few times, etc....And repeat this complex process for each of the children it recurses on.

Basically, out of curiosity and for understanding's sake at this point, I'm looking to figure out and understand the runtime complexity of this, since my undergraduate education has clearly met its limits here.

# Answer
> 1 votes
So this is basically doing - For each node in the tree; go through all the other nodes in the tree, add into children, and sort children each time.

Yes, very inefficient.

If we have n nodes then the time should be

* n - Each node in the tree
* \*n - go through all nodes in the tree
* \*(1 - add into children where relevant
* +s log s) - sort, where s is the current node's size.

That last term $\sum\_{i=1}^m i \log i$ comes to O($m^2 \log m$), so it depends on the shape of your tree. If the tree is very shallow (e.g., only the root is a non-leaf), this can therefore reach O($n^4 \log n$). If each node has up to m children, then it would be O($n^2 m^2 \log m$).

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: Minimum number of steps to sort 3x3 matrix in a given way
So I started practicing some algorithms and programming before university starts and I ran into this problem:

Given a 3x3 matrix containing the numbers from 0 to 8, find the minimum number of steps required to sort the matrix in the following format:

1 2 3
4 5 6
7 8 0

In one move it is only allowed to pick a cell that is adjacent to the cell which contains the 0 and swap those two cells.

Now, I am really stuck with this one and have no idea how to begin. Any tips and ideas to get me started are appreciated.

# Answer
Since you are looking for minimal number of moves without any tricks, there is old good pattern for small exact problems.

0) treat your starting matrix as root.
1) enumerate possible moves, and perform them (copy matrix, save steps etc.).
2) keep performing step one for every resulting matrix until you find them ordered. This is minimal number of moves.
1+) optimization possible is to ignore the same matrices that you already have, block sliding ply in direction it came from.
> 3 votes

---
Tags: algorithms, data-structures, logic, sorting
---


# Question
Title: Find an algorithm that sorts the nodes of a given graph acc. to distance from source node + value of the node's key
an unweighted connected graph $G=(V,E)$ all nodes of the graph contain a "serial number" between 1 to V. (V is an integer).

I am trying to come up with an algorithm that sorts all nodes firstly by distance (number of eadges) from source node 's' , secondly- if two nodes have same distance value sort them by value of thier serial number.

complexity required is $O (V+E)$

I tried to solve this via using bfs and then recieve a "bucket" array of distances - for each distance $1,2...$ all nodes within it are in its "bucket". the problem is, that in order to sort two nodes with same distance according to their serial number takes at least $O( nlogn)$ of sorting. I tried to come up with a use $v-1$ empty arrays and tried to send each "bucket" nodes acc. to their index in the graph and print it - that takes )$V^2$.

This is NOT homework, I really did try my best. Your comments are appreciated.

# Answer
Hint:

1. Use BFS to calculate the distances.
2. Calculate the scores (sums of distance to source and serial number).
3. Use counting sort to sort the scores.
4. Go over the list again and output the vertices in sorted order.
> 1 votes

---
Tags: algorithms, data-structures
---


# Question
Title: Need help understanding how to find big theta of a snippet of code
Say I have a snippet of code:

```
k = 5
i, j = 0

for i -> n
    if i == k
        for j -> k
            /* do something */
        end for
    k = k * 4/3
    end if
    /* do something */
end for

```

I can tell that the algorithm is worse than n but can't be worse than n^2. In fact it seems like it would be less than n log (n). Though I admit these are just guesses I'm making. Is there any methodology to figuring out what the big theta is for such algorithms?

# Answer
In order to estimate the running time of the code it is enough to count the number of times the two "do-somethings" are executed. Call them do-something 1 and do-something 2 (in their order of appearance). Do-something 2 is executed about $n$ times. As for do-something 1:

* If $n \< 5$, no times.
* If $5 \leq n \< (4/3)5$, $5$ times.
* If $(4/3)5 \leq n \< (4/3)^25$, $(4/3)5$ times.
* Generally, if $(4/3)^k5 \leq n \< (4/3)^{k+1}5$, $(4/3)^k5$ times.

Be creative and estimate the number of times that do-something 1 is executed in terms of $n$. Conclude the running time of the code snippet.
> 1 votes

# Answer
it can't be big theta because it has an escape clause, ie if this then don't do this. generally you would look for a loop through n values to be O(n) and two nested loops to be O(n^2), etc.
> -2 votes

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: How to prove if an algorithm is reentrant?
I think, maybe some formalism could exist for the task which makes it significantly easier.

My problem to solve is that I invented a reentrant algorithm for a task. It is relative simple (its pure logic is around 10 lines in C), but this 10 lines to construct was around 2 days to me. I am 99% sure that it is reentrant (which is not the same as thread-safe!), but the remaining 1% is already enough to disrupt my nights.

Of course I could start to do that on a naive way (using a formalized state space, initial conditions, elemental operations and end-conditions for that, etc.), but I think some type of formalism maybe exists which makes this significantly easier and shorter.

Proving the non-reentrancy is much easier, simply by showing a state where the end-conditions aren't fulfilled. But of course I constructed the algorithm so that I can't find a such state.

I have a strong impression, that it is an algorithmically undecidable problem in the general case (probably it can be reduced to the halting problem), but my single case isn't general.

I ask for ideas which make the proof easier. How are similar problems being solved in most cases? For example, a non-trivial condition whose fulfillment would decide the question into any direction, would be already a big help.

# Answer
> 2 votes
One approach is to design your code so it is "safe by construction", so re-entrant calls cannot happen. For instance, one way to do this is to use mutual exclusion to ensure that your method can't be invoked again while it is in the middle of running, to ensure you'll never have two instances running at the same time. For instance, this kind of approach is often used to ensure that interrupt handlers are correct: they often clear interrupts at the beginning and re-enable them at the end.

Another method is to take whatever code you already have and try to prove it will continue to function correctly even in the presence of re-entrant invocations. Here you can pick your favorite formal logic for reasoning about program correctness. For instance, you can use Hoare-style logic to specify the intended functionality and prove it correct. Then, you consider a tweaked version of your code, where before and after each statement, there is a (non-deterministic) possibility of a recursive invocation of the method being externally invoked; now you prove that the tweaked version continues to meet the spec. You can replace Hoare logic with any other method for program verification.

---
Tags: algorithms, concurrency, correctness-proof, software-verification
---


# Question
Title: counting binary, with moving position (turing machine)
I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It also has to have a runtime of O(N).

So I can prove that the number of "flips" (changing a 0 to a 1 or a 1 to a 0) that occur when counting from 1 to n in base 2 approaches 2n as n goes to infinity. meaning it's O(n) in terms of runtime, but i'm not sure how to factor in the movement of the head of the tape that is writing the binary. Near as I can tell, the head may have to move at most log(n) place to go from the 1s place to the last power of 2s place. For example, going from 11111 to 000001 requires moving from the 1s to the 64s place, or 6 places. It then has to move back to the ones to create the binary representation for 65.

How is this operation as a not O(nlogn)?

# Answer
> 0 votes
Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. Flip it to 1 and move back to LSB, stop. It is then clear that the total move distance is just double the number of flips.

---
Tags: turing-machines, counting
---


# Question
Title: Can a dynamic language like Ruby/Python reach C/C++ like performance?
I wonder if it is possible to build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++? From what I understand about compilers, take Ruby for instance, compiling Ruby code can't ever be efficient because the way Ruby handles reflection, features such as automatic type conversion from integer to big integer, and lack of static typing makes building an efficient compiler for Ruby extremely difficult.

Is it possible to build a compiler that can compile Ruby or any other dynamic languages to a binary that performs very closely to C/C++? Is there a fundamental reason why JIT compilers, such as PyPy/Rubinius will eventually or will never match C/C++ in performance?

Note: I do understand that “performance” can be vague, so to clear that up, I meant, if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y? Where X is everything from device drivers and OS code, to web applications.

# Answer
> 72 votes
To all those who said “yes” I’ll offer a counter-point that the answer is **“no”, by design**. Those languages will *never* be able to match the performance of statically compiled languages.

Kos offered the (very valid) point that dynamic languages have more information about the system at runtime which can be used to optimise code.

However, there‘s another side of the coin: this additional information needs to be kept track of. On modern architectures, this is a performance killer.

William Edwards offers a nice overview of the argument.

In particular, the optimisations mentioned by Kos can’t be applied beyond a very limited scope *unless* you limit the expressive power of your languages quite drastically, as mentioned by Devin. This is of course a viable trade-off but for the sake of the discussion, you then end up with a *static* language, not a dynamic one. Those languages differ fundamentally from Python or Ruby as most people would understand them.

William cites some interesting IBM slides:

> * Every variable can be dynamically-typed: Need type checks
> * Every statement can potentially throw exceptions due to type mismatch and so on: Need exception checks
> * Every field and symbol can be added, deleted, and changed at runtime: Need access checks
> * The type of every object and its class hierarchy can be changed at runtime: Need class hierarchy checks

*Some* of those checks can be eliminated after analysis (N.B.: this analysis *also* takes time – at runtime).

Furthermore, Kos argues that dynamic languages could even surpass C++ performance. The JIT can indeed analyse the program’s behaviour and apply suitable optimisations.

*But C++ compilers can do the same!* Modern compilers offer so-called profile-guided optimisation which, if they are given suitable input, can model program runtime behaviour and apply the same optimisations that a JIT would apply.

Of course, this all hinges on the existence of realistic training data and furthermore the program cannot adapt its runtime characteristics if the usage pattern changes mid-run. JITs can theoretically handle this. I’d be interested to see how this fares in practice, since, in order to switch optimisations, the JIT would continually have to collect usage data which once again slows down execution.

**In summary, I’m not convinced that runtime hot-spot optimisations outweigh the overhead of tracking runtime information in the long run**, compared to static analysis and optimisation.

# Answer
> 20 votes
> if you can do X in C/C++ with performance Y, can you do X in Ruby/Python with performance close to Y?

Yes. Take, as an example, PyPy. It is a collection of Python code that performs close to C in doing interpretation (not all that close, but not all that far away either). It does this by performing full-program analysis on the source code to assign each variable a static type (see the Annotator and Rtyper docs for details), and then, once armed with the same type information you give C, it can perform the same sorts of optimizations. At least in theory.

The tradeoff of course is that only a subset of Python code is accepted by RPython, and in general, even if that restriction is lifted, only a subset of Python code can do well: the subset that can be analyzed and given static types.

If you restrict Python enough, optimizers can be built that can take advantage of the restricted subset and compile it to efficient code. This is not really an interesting benefit, in fact, it's well known. But the whole point of using Python (or Ruby) in the first place was that we wanted to use interesting features that perhaps don't analyze well and result in good performance! So the interesting question is actually...

> Additionally, will JIT compilers, such as PyPy/Rubinius ever match C/C++ in performance?

Nah.

By which I mean: sure, maybe as code runs accumulate you can get enough typing information and enough hotspots to compile all of the code all the way down to machine code. And maybe we can get this to perform better than C for some code. I don't think that's hugely controversial. But it still has to "warm up", and performance is still a bit less predictable, and it won't be as good as C or C++ for certain tasks that require consistently and predictably high performance.

The existing performance data for Java, which has both more type information than Python or Ruby, and a better-developed JIT compiler than Python or Ruby, still doesn't match up to C/C++. It is, however, in the same ballpark.

# Answer
> 19 votes
The short answer is: **we don't know**, ask again in 100 years. (We might still not know then; possibly we'll never know.)

In theory, this is possible. Take all the programs that have ever been written, manually translate them to the most efficient possible machine code, and write an interpreter that maps source codes to machine codes. This is possible since only a finite number of programs have ever been written (and as more programs get written, keep up the manual translations). This is also, of course, completely idiotic on practical terms.

Then again, in theory, high-level languages might be able to reach the performance of machine code, but they won't surpass it. This is still very theoretical, because in practical terms, we very rarely resort to writing machine code. This argument does not apply to comparing higher-level languages: it doesn't imply that C must be more efficient than Python, only that machine code cannot do worse than Python.

Coming from the other side, on purely experimental terms, we can see that *most of the time*, interpreted high-level languages perform worse than compiled low-level languages. We tend to write non-time-sensitive code in very high-level languages and time-critical inner loops in assembly, with languages like C and Python falling in between. While I don't have any statistics to back this up, I think this is indeed the best decision in most cases.

However, there are uncontested instances where high-level languages beat the code that one would realistically write: special-purpose programming environments. Programs like Matlab and Mathematica are often far better at solving certain kinds of mathematical problems than what mere mortals can write. The library functions may have been written in C or C++ (which is fuel towards the “low-level languages are more efficient” camp), but that's none of my business if I'm writing Mathematica code, the library is a black box.

Is it theoretically possible that Python will get as close, or maybe even closer, to optimal performance than C? As seen above, yes, but we are very far from that today. Then again, compilers have made a lot of progress in the past decades, and that progress is not slowing down.

High-level languages tend to make more things automatic, so they have more work to perform, and thus tend to be less efficient. On the other hand, they tend to have more semantic information, so it can be easier to spot optimizations (if you're writing a Haskell compiler, you don't have to worry that another thread will modify a variable under your nose). One of several efforts to compare ~~apples and oranges~~ different programming languages is the Computer Language Benchmark Game (formerly known as the shootout). Fortran tends to shine at numerical tasks; but when it comes to manipulating structured data or high-rate thread commutation, F# and Scala do well. Don't take these results as gospel: a lot of what they are measuring is how good the author of the test program in each language was.

An argument in favor of high-level languages is that performance on modern systems is not so strongly correlated with the number of instructions that are executed, and less so over time. Low-level languages are good matches for simple sequential machines. If a high-level language executes twice as many instructions, but manages to use the cache more intelligently so it does half as many cache misses, it may end up the winner.

On server and desktop platforms, CPUs have almost reached a plateau where they don't get any faster (mobile platforms are getting there too); this favors languages where parallelism is easy to exploit. A lot of processors spend most of their time waiting for an I/O response; the time spent in computation matters little compared with the amount of I/O, and a language that allows the programmer to minimize communications is at an advantage.

All in all, while high-level languages start with a penalty, they have more room for improvement. How close can they get? Ask again in 100 years.

<sub> Final note: often, the comparison is not between *the most efficient program that can be written* in language A and the same in language B, nor between *the most efficient program ever written* in each language, but between *the most efficient program that can be written by a human in a certain amount of time* in each language. This introduces an element that cannot be analyzed mathematically, even in principle. In practical terms, this often means that the best performance is a compromise between much how low-level code you need to write to meet performance goals and how much low-level code you have time to write to meet release dates. </sub>

# Answer
> 11 votes
The basic difference between the C++ statement `x = a + b` and the Python statement `x = a + b` is that a C/C++ compiler can tell from this statement (and a little extra information that it has readily available about the types of `x`, `a`, and `b`) precisely what machine code needs to be executed. Whereas to tell what operations the Python statement is going to do, you need to solve the Halting Problem.

In C that statement will basically compile to one of a few types of machine addition (and the C compiler knows which one). In C++ it might compile that way, or it might compile to calling a statically known function, or (worst case) it might have to compile to a virtual method lookup and call, but even this has a fairly small machine code overhead. More importantly though, the C++ compiler can tell from the statically known types involved whether it can emit a single fast addition operation or whether it needs to use one of the slower options.

In Python, a compiler could theoretically do nearly that good if it **knew** that `a` and `b` were both `int`s. There's some additional boxing overhead, but if types were statically known you could probably get rid of that too (while still presenting the interface that integers are objects with methods, hierarchy of super-classes, etc). The trouble is a compiler for Python *can't* know this, because classes are defined at runtime, can be modified at runtime, and even the modules that do the defining and importing are resolved at runtime (and even which import statements are executed depends on things that can only be known at runtime). So the Python compiler would have to know what code has been executed (i.e. solve the Halting Problem) in order to know what the statement it is compiling will do.

So even with with most sophisticated analyses that are *theoretically possible*, you simply can't tell much about what a given Python statement is going to do ahead of time. This means that even if a sophisticated Python compiler were implemented, it would in almost all cases still have to emit machine code that follows the Python dictionary lookup protocol to determine the class of an object and find methods (traversing the MRO of the class hierarchy, which can also change dynamically at runtime and so is difficult to compile to a simple virtual method table), and basically do what the (slow) interpreters do. This is why there aren't really any sophisticated optimising compilers for dynamic languages. It's not merely hard to create one, the maximum possible payoff isn't as big as it is for languages like C/C++.

Note that this isn't based on what the code **is** doing, it's based on what the code *could* be doing. Even Python code that is a simple series of integer arithmetic operations has to be compiled *as if* it might be invoking arbitrary class operations. Static languages have greater restrictions on the possibilities for what the code could be doing, and consequently their compilers can make more assumptions.

JIT compilers gain on this by waiting until runtime to compile/optimise. This lets them emit code that works for what the code **is** doing rather than what it could be doing. And because of this JIT compilers have a much huger potential payoff for dynamic languages than for static languages; for more static languages much of what an optimiser would like to know can be known ahead of time, so you might as well optimise it then, leaving less for a JIT compiler to do.

There are various JIT compilers for dynamic languages that claim to achieve execution speeds comparable to that of compiled and optimised C/C++. There are even optimisations that can be by a JIT compiler that cannot be done by an ahead of time compiler for any language, so theoretically JIT compilation (for some programs) could one day outperform the best possible static compiler. But as Devin rightly pointed out, the properties of JIT compilation (only the "hotspots" are fast, and only after a warmup period) means that JIT-compiled dynamic languages are unlikely to ever be suitable for all possible applications, even if they become as fast or faster than statically compiled languages generally.

# Answer
> 9 votes
Just a quick pointer that outlines the worst case scenario for dynamic languages:

$\qquad$Perl parsing is not computable

As a consequence, (full) Perl can *never* be compiled statically.

---

In general, as always, it depends. I am confident that if you try to emulate dynamic features in a statically compiled language, well-conceived interpretors or (partially) compiled variants can come near or undercut performance of statically compiled languages.

Another point to keep in mind is that dynamic languages *solve another problem* than C. C is barely more than nice syntax for assembler while dynamic languages offer rich abstractions. Runtime performance is often not the prime concern: time-to-market, for instance, depends on your developers being able to write complex, high-quality systems in short timeframes. Extensibility without recompilation, for instance with plugins, is another popular feature. Which language do you prefer in these cases?

# Answer
> 5 votes
> Can you build compilers for dynamic languages like Ruby to have similar and comparable performance to C/C++?

I think that the answer's **"yes"**. I also believe that they can even **surpass** the current C/C++ architecture in terms of efficiency (even if slighly).

The reason is simple: **There's more information in run-time than in compile-time.**

Dynamic types are only a slight obstacle: If a function is always or almost-always executed with the same arguments types, then a JIT optimizer can generate a branch and machine code for that specific case. And there's so much more that can be done.

See Dynamic Languages Strike Back, a speech by Steve Yegge of Google (there's also a video version somewhere I believe). He mentions some concrete JIT optimisations techniques from V8. Inspiring!

I'm looking forward to what we're going to have in the next 5 years!

# Answer
> 5 votes
In an attempt to offer a more objectively scientific answer to this question, I argue as follows. A dynamic language requires an interpreter, or runtime, to make decisions at run time. This interpreter, or runtime, is a computer program and, as such, was written in some programming language, either static or dynamic.

If the interpreter/runtime was written in a static language, then one could write a program in that static language which (a) performs the same function as the dynamic program it interprets and (b) performs at least as well. Hopefully, this is self-evident, since to provide a rigorous proof of these claims would require additional (possibly considerable) effort.

Assuming these claims to be true, the only way out is to require that the interpreter/runtime be written in a dynamic language, as well. However, we run into the same issue as before: if the interpreter is dynamic, it requires an interpreter/runtime, which also must have been written in a programming language, dynamic or static.

Unless you assume that an instance of an interpreter is capable of interpreting itself at runtime (I hope this is self-evidently absurd), the only way to beat static languages is for each interpreter instance to be interpreted by a separate interpreter instance; this leads either to an infinite regress (I hope that this is self-evidently absurd) or a closed loop of interpreters (I hope this is also self-evidently absurd).

It seems, then, that even in theory, dynamic languages can perform no better than static languages, in general. When using models of realistic computers, it seems even more plausible; after all, a machine can only execute sequences of machine instructions, and all sequences of machine instructions can be statically compiled.

In practice, matching the performance of a dynamic language with a static language could require re-implementing the interpreter/runtime in a static language; however, that you can do that at all is the crux and point of this argument. It's a chicken and egg question and, provided you agree with the unproven (though, in my opinion, mostly self-evident) assumptions made above, we can actually answer it; we have to give the nod to the static, not dynamic, languages.

Another way to answer the question, in light of this discussion, is this: in the stored-program, control=data model of computing which lies at the heart of modern computing, the distinction between static and dynamic compilation is a false dichotomy; statically compiled languages must have a means of generating and executing arbitrary code at run time. It's fundamentally related to universal computation.

# Answer
> 2 votes
People who apparently think this is theoretically possible, or in a far future, are completely wrong in my opinion. The point lies in the fact that dynamic languages provide and impose a totally different programming style. Actually, the difference is twofold, even if both aspect are interrelated:

* Symbols (vars, or rather id\<-\>datum bindings of all kinds) are untyped.
* Structures (the data, all what lives at runtime) are untyped as well by the types of their elements.

The second point provides genericity for free. Note that structures here are composite elements, collections, but also types themselves, and even (!) routines of all kinds (functions, actions, operations)... We could type structures by their element types, but due to the first point the check would happen at runtime anyway. We could have typed symbols and still have structured ones untyped according to their element types (an array `a` would just be typed as an array not as an array of ints), but even this few is not true in a dynamic language (`a` could as well contain a string).

The best perf we can achieve in dynamic programming is, in my opinion, equivalent to the following: implement in C the *model* of a dynamic language, let's call it $L$, ie a kind of fictional machine, or a complete runtime lib. And then program (in C directly) using only the model, no plain C features. This means having:

* a totally polymorphic (C) `Element` type, which includes $L$ type annotations (or a ref to the actual representation of $L$'s type in the model)
* all symbols are of that type `Element`, they can hold elements of any $L$ type
* all structures (again, including model routines) receive only Element's

It is clear for me that this only is a huge perf penalty; and I don't even touch all consequence (the myriad of runtime checks of all kinds necessary to ensure program sensibility) well described in other posts.

# Answer
> 1 votes
I did not have the time to read all answers in detail ... but I was amused.

There was a similar controversy in the sixties and early seventies (computer science history often repeats itself): can high level languages be compiled to produce code as efficient as the machine code, well, say assembly code, produced manually by a programmer. Everyone knows a programmer is much smarter than any program and can come up with very smart optimisation (thinking actually mostly of what is now called peephole optimization). This is of course irony on my part.

There was even a concept of code expansion : the ratio of the size of the code produced by a compiler to the size of code for the same program produced by a good programmer (as if there had been too many of these :-). Of course the idea was that this ratio was always greater than 1. The languages of the time were Cobol and Fortran 4, or Algol 60 for the intellectuals. I believe Lisp was not considered.

Well there were some rumors that someone had produced a compiler that could sometimes get an expansion ratio of 1 ... until it simply became the rule that compiled code was much better than hand written code (and more reliable too). People were worried about code size in those times (small memories) but the same goes for speed, or energie consumption. I will not go into the reasons.

Weird features, dynamic features of a language do not matter. What matters is how they are used, whether they are used. Performance, in whatever unit (code size, speed, energy, ...) is often dependent on very small parts of programs. Hence there is a good chance that facilities that give expressive power will not really get in the way. With good programming practice, advanced facilities are used only in a disciplined way, to imagine new structures (that was the lisp lesson).

The fact that a language does not have static typing has never meant that programs written in that language are not statically typed. On the other hand it might be that the type system a program uses is not yet sufficiently formalized for a type checker to exist now.

There have been, in the discussion, several references to worst case analysis ("halting problem", PERL parsing). But worst case analysis is mostly irrelevant. What matters is what happens in most cases or in useful cases ... however defined or understood or experienced. Here comes another story, directly related to program optimisation. It took place a long time ago in a major university in Texas, between a PhD student and his advisor (who was later elected in one of the national academies). As I recall, the student was insistent on studying an analysis/optimisation problem the advisor had shown to be untractable. Soon they were no longer on speaking terms. But the student was right: the problem was tractable enough in most practical cases so that the dissertation he produced became reference work.

And to comment further on the statement that `Perl parsing is not
computable`, whatever is meant by that sentence, there is a similar problem with ML, which is a remarkably well formalized language. `Type
checking complexity in ML is a double exponential in the lenght of the
program.` That is a very precise and formal result in worst case complexity ... which does not matter at all. Afaik, ML users are still waiting for a practical program that will explode the type checker.

In many cases, as it was before, human time and competence is scarcer than computing power.

The real problem of the future will be to evolve our languages to integrate new knowledge, new programming forms, without having to rewrite all the legacy software that is still used.

If you look at mathematics, it is a very large body of knowledge. The languages used to express it, notations and concepts has evolved over the centuries. It is easy to write old theorems with the new concepts. We do adapt the main proofs, but do not bother for lots of results.

But in the case of programming, we might have to rewrite all the proofs from scratch (programs are proofs). It may be that what we really need is very high level and evolvable programming languages. Optimizer designers will be happy to follow.

# Answer
> 1 votes
A couple of notes:

* Not all high level languages are dynamic. Haskell is very high level, but is fully statically typed. Even systems programming languages like Rust, Nim, and D can express high-level abstractions succinctly and efficiently. In fact, they can be as concise as dynamic languages.
* Highly optomizing ahead-of-time compilers for dynamic languages exist. Good Lisp implementations reach half the speed of equivalent C.
* JIT compilation *can* be a big win here. CloudFlare's Web Application Firewall generates Lua code that is executed by LuaJIT. LuaJIT heavily optimizes the execution paths actually taken (typically, the non-attack paths), with the result that the code runs much faster than code produced by a static compiler on the actual workload. Unlike a static compiler with profile-guided optimization, LuaJIT adapts to changes in execution paths at runtime.
* *Deoptimization* is also crucial. Instead of JIT-compiled code needing to check for a class being monkeypatched, the act of monkeypatching triggers a hook in the runtime system that discards the machine code that depended on the old definition.

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


# Question
Title: Are combinatorial problems inherently NP-Complete?
Most combinatorial problems seem NP-complete. Is this inherent in the design of the problems themselves? Are there any combinatorial problems in "P" ?

# Answer
> 8 votes
No. Counterexamples (problems in $P$) include shortest path, max flow, minimum spanning tree,...

# Answer
> 5 votes
The "P" part of "NP" refers to the time on a nondeterministic TM being polynomial *in the size of the representation of the input*. This is an important point which sometimes gets lost when thinking about complexity theory.

One interesting consequence of this definition is that you can sometimes construct a problem in a higher complexity class by using a representation which is smaller.

Take any NP-complete problem using a "natural" representation, such as Hamiltonian circuit on a graph represented as an adjacency matrix. Note that the size of the representation of the graph is polynomial in $|V|$. Now let's suppose there is a compressed representation (e.g. a succinct circuit; I'll give a reference at the end) of the graph which is polylogarithmic in $|V|$, that is, a polynomial in $\log |V|$.

The compressed representation of the graph is exponentially smaller than the uncompressed representation. So any algorithm which solves the original problem on *this* input is exponentially more complex than an algorithm which solves the problem on the uncompressed representation! Specifically, the new problem is now NEXPTIME-complete which, by the time hierarchy theorem, is not in NP.

So to answer your question, no, combinatorial problems are not inherently NP-complete, because changing the representation of the input may change the complexity class of the problem. But in another sense they might be, because for a large class of problems, you may be able to choose a representation of the input which makes the problem NP-complete.

For more on succinct graphs and complexity theory: Galperin, *Succinct Representations of Graphs*, Information and Control, 56:183-198 (1983).

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


# Question
Title: BIT: Unable to understand update operation in Binary index Tree
I have just read this answer and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT.

But at the end, the second last paragraph is where I am struggling. It says,

> Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

But if I see, take some example, it does not work just as by simply switching 1's and 0's, according to me.

e.g. lets take we want to update value at node 5 = 101 Switching 1s and 0s, we get 010... Now applying the procedure they have given earlier, we will end up updating some other node or so.

I must be getting it wrong. Please correct me.

Thank you in advance.

# Answer
If you don't stick to the claim of "switching all 1's to 0's and 0's to 1's" (I am also confused) in that post, here is the simple *bitwise trick* for updating used in the original paper "A New Data Structure for Cumulative Frequency Tables" (Figure 5) by Peter Fenwick (`Ix` for index).

```
Repeat:
Tree[Ix] := Tree[Ix] + val;
Ix := Ix + BitAnd(Ix, -Ix);    // add the least-significant one
Until Ix >= TableSize

```

---

That is, the nodes accessed via a left link upward from the original node `i` can be calculated by
`i += i && -i.`

`i && -i` is the least significant bit of `i`. `i += i && -i` moves you to the ancestor that is closest to the right side of `i`. This is the next node you will need if you want to add all the nodes to the right of `i`.

In your example, `i = 5_(10) = 101_(2)`. The first `i && -i` gives `001` and `i + i && -i` moves you to node `i' = 110_(2) = 6_(10)`. The second `i' && -i'` on `i'` gives `010` and `i' + i' && i'` moves you to node `i'' = 1000_(2)` (which is too large).

For an example with 31 nodes and `i = 9 = 1001`, you will access the following nodes: `i' = 1001 + 0001 = 1010`, `i'' = 1010 + 0010 = 1100`, and `i''' = 1100 + 0100 = 10000` (which is too large).

---

By the way, in the case of query, the bitwise trick is simply modified to `i -= i && -i`. It is easy to verify that this trick agrees with the procedure of "Clearing the rightmost 1 bit". Also see the related post here.
> 1 votes

# Answer
I believe you should be switching the 1s and 0s in the algorithm, not the number itself. In other words:

> Given node n, the next node on the access path back up to the root in which we go left is given by taking the binary representation of n and removing the last 0.

So the algorithm for updating becomes:

* Write out node n in binary.
* Repeat the following while n ≠ 0:
    + Add your value to node n.
    + "Remove" the rightmost '0' bit from n.

But I'm not quite sure what "remove" means here. In the original case it just means 0:ing the bit, but that doesn't work here.
> 0 votes

# Answer
In BIT query, the trick is ***removing the last 1 bit***.

In BIT update is ***adding the last 1 bit***.

* Write out node n in binary.
* Set the counter to 0.
* Repeat the following while ***n \<= N (the largest value in BIT)***:
    + Add in the value at node n.
    + ***Get the rightmost 1 bit from n, and adding it to n***.

In languages supporting bit operation, it can be simply archived by $n \leftarrow n+(n\\&(-n))$

Take 11 for example: (suppose full range is 1~32) $$11=1011\_2 \to 1011\_2+1\_2=1100\_2$$ $$\to 1100\_2+100\_2=10000\_2$$ $$\to 10000\_2+10000\_2=100000\_2=32$$. So the path is $11\to12\to16\to32$
> 0 votes

---
Tags: algorithms, data-structures, trees, binary-trees
---


# Question
Title: How to calculate the size of a page in a two level paging CPU?
I am having difficulties with understanding the concept of paging.

As a result I've got no idea how I can solve the following exercise - I'm lacking one more equation to solve it.

I've read a lot about paging and watched a few tutorials, but I still cannot solve paging problems easily. I'll provide some of the resources I learnt from at the bottom of this question.

---

## Background:

The CPU has two level paging and the logical and physical addresses are of $34$ bits size each.

The sizes of the page table directory, the table directory and the page are equal.

The logical address $(12345678)\_{16}$ has been translated to the $(ba9678)\_{16}$ physical address.

**What's the size of a single page?**

---

## My attempt:

1. The logical address can be decoded to:
$$(00\ 0001\ 0010\ 0011\ 0100\ 0101\ 0110\ 0111\ 1000)\_2$$ The physical address can be decoded to: $$(00\ 0000\ 0000\ 1011\ 1010\ 1001\ 0110\ 0111\ 1000)\_2$$ So, as you can see, they share the last $14$ bits.
Hence, the number of bits representing offset is $\leq 14$.
2. The physical address looks like this:

```
+-----------+-----------+--------+
+-page-size-+-page-size-+-offset-+
+-----------+-----------+--------+

```

because page size = page table size = table directory size.
Therefore, we get the following equation: $$ 2\times \text{page size} + \text{offset} = 34 $$
However it is not sufficient to tell what is the page size. I'm stuck.

---

### Resources:

# Answer
# The thorough solution:

1. The virtual address looks like this:

```
+-------------+------------+--------+
+ table index + page index + offset +
+-------------+------------+--------+

```

where:

* *table index* is the index length of an entry in the page table directory. I'll call it $i\_t$.
    * *page index* is the index length of an entry in the page table. I'll call it $i\_p$.
    So we have such an equation now: $$ i\_t+i\_p+o=32 $$ where $o$ represents bits that we need for offset.
2. From the decoded addresses we know that offset cannot be greater than $14$, so: $$ o \leq 14 $$
3. We know that an entry in both page tables and page tables directories needs $i\_t + b\_d$ of bits where $b\_d$ is the number of bits for accounting information (such as dirty bits, protection bits and so on). So, $b\_d$ are accounting bits in the page table directory and $b\_t$ are are accounting bits in page table.

So, if $\text{page size} = 2^\text{offset}$ then $\text{page table size} = 2^\text{offset}$ and $\text{page table directory size} = 2^\text{offset}$: $$ \begin{cases} i\_t+b\_d = o\\ i\_s+b\_t = o\\ \end{cases} $$
4. We can say thatSince $\text{page table size} = \text{page table directory size}$ then $i:= i\_t = i\_s$ and $b :=b\_d=b\_t$, so we end up with a system of equations like this: $$ \begin{cases} i\_t+b\_d = o\\ i\_s+b\_t = o\\ i\_t+i\_p+o=32 \end{cases} $$ $$ o-b\_d+o-b\_t+o=32\\ $$ and finally because of $b :=b\_d=b\_t$: $$ 3o-2b=32\\ $$
5. Now we will test different values of $o$ (I'll not test odd $o$'s because $o$ must be dividable by $2$):
    * when $o=14$: $$ 42-32=2b=10\\ \implies b=5\\ \implies i = 14-5=11\\ \implies i\_t+i\_s+o=11+11+14=36 \neq 32 $$
    * when $o=12$: $$ 36-32=2b=4\\ \implies b=2\\ \implies i = 12-2=10\\ \implies i\_t+i\_s+o=10+10+12=32 = 32 $$ which seems to be the answer. Let's just make sure there are no other possibilities.
    * when $o=10$: $$ 30-32=2b=-2\\ \implies b=-1\\ $$ which cannot be true - you obviously cannot have a negative number of bits.

Therefore, the size of a page is equal $2^o=2^{12}$.
> 2 votes

# Answer
Your inference about the format of the physical address is not correct. A physical address looks like

```
+------------------+--------+
| page frame index | offset |
+------------------+--------+

```

I think you are getting virtual pages and physical pages confused. Refresh your understanding of how virtual memory and page tables works. I suggest you consult an operating systems textbook: Wikipedia is less than ideal and doesn't have thorough coverage.

Once you fix that confusion: You haven't fully used the information in "The sizes of a page table directory, a table directory and a page are equal."

Suppose the offset was 5 bits (say). This would let you figure out how many bits are needed for each entry in the page table, and thus let you figure out the size of the page tables. You should then be able to use this to determine whether it's possible that a 5-bit offset is feasible. You can then try each possible offset size from 1 to 14 to work out which ones are possible, given the statements in the exercise.

In the future, rather than asking how to solve your particular exercise, I suggest you try to use the exercise to diagnose what your conceptual confusion is (this might require additional self-study) and then ask a conceptual question.
> 1 votes

---
Tags: computer-architecture, memory-management, virtual-memory, paging, cpu
---


title: Computer Architecture - Von Neumann

text:
# Question
Title: Computer Architecture - Von Neumann
With regards to introductory (beginner) Von Neumann computer architecture, how does a program change the order in which instructions are executed?

I know the control unit is responsible for retrieving the instruction from memory and then decodes and executes the instruction. Their connected by a bus. The control unit and ALU are together in the CPU.

I'm guessing different lines of code are stored in different addresses in the RAM?

Is it a easy question, and I'm just thinking its difficult?

# Answer
You are getting into to much detail. You can think of a CPU as some kind of automaton which operates roughly as follows (ignoring pipelining). There is a register called (in x86) IP (Instruction Pointer). The CPU operates an infinite loop (ignoring interrupts):

1. Read the instruction $\iota$ at address IP; determine its length $\ell$, and increment IP by $\ell$.
2. Execute $\iota$; this might change IP.
3. Go back to 1.

This is implemented in some sophisticated way, but if you don't care about performance, it performs as if the CPU was actually running this infinite loop. Control instructions change IP and so control which instructions are executed.

Different programs are just collections of instructions. When you run a program, the operating system loads it into memory and then jumps to the first instruction (i.e., sets IP to the address of the first instruction). From there on, the program executes until it terminates and releases the token back to the operating system. (Modern operating systems, which are multitasking, are more complicated, but DOS ran much according to this description, ignoring interrupts.)
> 4 votes

# Answer
Memory in a computer can be thought of as one long string. You have position 1, position 2, position 3, etc.

Let's start with the simple case where every instruction occupies exactly one position in memory. Then the normal process for the computer is to execute the instruction at position 1, then to execute the instruction at position 2, then execute the instruction at position 3, etc.

Some instructions change this sequence. The simplest is a "jump" or "go to". This tells the computer that the next instruction to execute is not the one with the next higher position number, but some other instruction. So if at position 100 we have the instruction "JUMP TO 200", then instead of going to 101 next we'll go to 200.

Technically, there's a special register called the "instruction pointer" that says what the next instruction is to execute. Normally, after executing each instruction, the computer automatically adds 1 to this. A jump instruction replaces the value instead of doing the automatic add. (Some computers have relative jumps that add or subtract from the instruction pointer rather than replacing it, like JUMP +10 means add 10 to the IP.)

On many, probably most, modern computers instructions do not all have the same length. But this just adds a minor complexity. If an instruction takes 3 positions, then after executing it we add 3 to the instruction pointer instead of 1.

There can be additional complexities. Like "interrupts" can jump you out of the normal sequence. For example, on some computers, when a key is pressed this generates an interrupt, which takes the computer to a function that processes the keystroke. The current IP is saved somewhere, and when the interrupt processing is complete, we restore the IP and resume what we were doing before.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Comparing different implementations of genetic algorithms
I am looking up some material for my thesis in CS (development of a module to integrate a genetic algorithm in a system developed by other students).

My actual current task is to make a comparative analysis of several libraries for genetic algorithms. After this comparison I will choose one of these libraries and an algorithm.

I want to know if you can give me any tips or best practice to perform such comparison. Which approach to the task would you recommend?

# Answer
> 1 votes
Your first step, when doing a comparative analysis, is to identify your requirements. We can't tell you what the requirements should be; that's something you'll need to figure out on your own.

Then, you can try to evaluate the libraries to determine how well they meet your requirements. The particular style of evaluation depends upon what kind of requirement you want to evaluate. For instance, evaluating performance is very different from evaluating reliability.

---
Tags: algorithm-analysis, genetic-algorithms, experimental-analysis
---


# Question
Title: Efficiently finding $k$ smallest elements of Cartesian product
Given lists $A\_1, A\_2, \dots, A\_n$ of non-negative numbers, I want to find the $k$ smallest elements of the Cartesian product $A\_1 \times A\_2 \times \dots \times A\_n$ ordered by the value $x\_1 + x\_2 + \dots + x\_n$, where $x\_i\in A\_i$.

I can't simply create all combinations in memory and sort them because of large amount of data.

For example, I have 1000 drinks, 1000 main courses and 1000 desserts. I want to find the 100 cheapest meals but I can't store all 1,000,000,000 elements in memory.

**Additional details**

1. I have Drinks, Main Courses and Desserts already sorted.
2. I've found some solutions like Efficient sorted cartesian product of 2 sorted array of integers but only for 2 lists. For greater amount of sets it still memory-consuming.
3. Lazy generating next "sorted" value will be useful.
4. If no efficient exact algorithm, it could be heuristic or approximation algorithm.
5. It's similar to X + Y sorting problem , efficient faster than `O(n^2 * log n)` solution is unknown

**Question:**

Are there an efficient ways to get only $k$ cheapest(\*) elements of Cartesian product?
(\*) Price of the result element is sum of all numbers in that element.

# Answer
> 5 votes
If $k$ is known in advance, we can do the following. I will assume that each list $A\_j$ is sorted according to cost. What we will do is a weighted form of breadth-first exploration of index tuples $(i\_1,\dots,i\_n)$, storing the current candidates in a (bounded length) priority queue $Q$ according to their cost $A\_1\[i\_1\]+\dots+A\_n\[i\_n\]$. Initially $Q$ contains just the initial tuple $(0,\dots,0)$.

In each iteration, pop the first tuple $t=(i\_1,\dots,i\_n)$ off $Q$; this is a cheapest previously unexplored solution. Then generate its successors of the form $t^{(j)}=(i\_1,\dots,i\_j+1,\dots,i\_n)$, compute their cost, and insert them into $Q$ accordingly.

We can avoid creating duplicates by only creating the successors $t^{(j)}$ up to the first index $j$ for which $i\_j\>0$; e.g. for $t=(0,1,0,2)$ we would only create $(1,1,0,2)$ and $(0,2,0,2)$ (the other tuples $(0,1,1,2)$ and $(0,1,0,3)$ instead get created as successors of $(0,0,1,2)$ and $(0,0,0,3)$, respectively). This eliminates the need for a *closed list* of explored tuples. We still need to store the priority queue $Q$, but it can be bounded to length $k-j$, where $j$ is the current iteration, with any entries beyond that discarded.

For example, suppose we have $A\_1=(1,5,7),A\_2=(1,2,5),A\_3=(1,3,4)$, and $k=4$.

* Initially, $Q=\[(0,0,0)\]$.
* Pop $(0,0,0)$, with cost $3$, and push $(1,0,0),(0,1,0),(0,0,1)$. Their costs are $7,4,5$, respectively, and $Q$ is now $\[(0,1,0),(0,0,1),(1,0,0)\]$.
* Pop $(0,1,0)$ (cost $4$), and push $(1,1,0)$ (cost $8$) and $(0,2,0)$ (cost $7$). $Q$ is now $\[(0,0,1),(1,0,0),(0,2,0),(1,1,0)\]$; since we only need two more solutions, we can drop the last two, getting $\[(0,0,1),(1,0,0)\]$.
* Pop $(0,0,1)$ (cost $5$), and push $(1,0,1)$ (cost $9$), $(0,1,1)$ (cost $6$), and $(0,0,2)$ (cost $6$). $Q$ is now $\[(0,1,1),(0,0,2),(1,0,0),(1,0,1)\]$; again, we can drop unneeded entries since we only want one more, getting $\[(0,1,1)\]$.
* Pop $(0,1,1)$; done.

To see that this method is correct, we just need to prove the following:

1. Given the above restrictions, any index tuple $i=(i\_1,\dots,i\_k)$ (with $0\le i\_j\le size(A\_j)$) is reachable along the unique path $(0,\dots,0)\to\dots\to(0,\dots,0,i\_k)\to\dots\to(0,\dots,0,i\_{k-1},i\_k)\to\dots\to i$.
2. The cost of the tuples along that path is nondecreasing, since the weights are nonnegative.
3. If there is another tuple $i'$ with a higher cost, and $i'$ is popped off $Q$ during the algorithm, then so are all tuples along the path to $i$ (using induction).
4. If a tuple $i'$ is discarded due to the length restriction, then there are at least $k$ tuples whose cost is no greater than that of $i'$.

# Answer
> 2 votes
This is more of a median problem, so compared to sorting you may be able to shave some work off for large k (for small k, expanding from the origin is probably best).

Assuming all sets are sorted, the function $s(x) = \sum{}{x\_i}$ has nonnegative partial derivative in all dimensions, so if you pick a random pivot $p$ such that $0 \< p \<= \sum{max(A\_i)}$ then the boundary of $P(p) = \\{y: s(y) \<= p \\}$ has dimension $n-1$ and can be traced in that time (ie if $|A\_i| = a$ and there are $a^n$ tuples, you only have to evaluate $o(a^{n-1})$ points to count the volume of $P(p)$). During tracing it's a simple matter to keep a running count of $|P|$.

If you binary search on $p$ then I believe you have $o(a^{n-1}\log{a})$.

---
Tags: algorithms, sorting, sets
---


# Question
Title: Creating arrays of object of abstract class in statically-typed object-oriented languages
In statically-typed object-oriented languages (like Java, C++, C#, ...), suppose I declare an abstract class:

```
public abstract class myclass1 {
 .................
}

```

Most of these languages (like Java) wouldn't allow us to create an Object of an Abstract class, but they do allow us create an Array of Object of an Abstract class. Like,

```
myclass1 arr[] = new myclass1[10];

```

We can create an array of 10 objects.

I have some confusion about how this kind of array works. How do I use this array? What is the actual use of this array in real-life projects? Any explanation with an example will be very useful.

# Answer
> 5 votes
In statically-typed object oriented languages (like Java), you can not create an object of an abstract class. Abstract classes are (usually) not completely defined, so creating such an object wouldn't make any sense.

What you can create is a *reference* to an object instance of an abstract class. A reference is just a pointer to an object, not the object itself.

```
myclass1 arr[] = new myclass1[10];

```

Creates an array of 10 `null` references to objects of class `myclass1`.

Similarly

```
myclass1 x = null;

```

Creates a copy of the `null` reference and *casts* it to a reference to a `myclass1`.

You can always assign an object of a (non-abstract) subclass of `myclass1` to a reference to `myclass1`. So for example:

```
x = new ConcreteClass();

```

(where `ConcreteClass` is a subclass of `myclass1`).

Any element of `arr` is also a reference to `myclass1`. So:

```
arr[7] = new ConcreteClass();

```

---
Tags: programming-languages, compilers, type-checking, object-oriented
---


# Question
Title: How to determine approximability of a problem when we don't know how good a solution is?
As far as I have learned, an approximation algorithm for an optimization problem

1. Runs in polynomial time, and
2. Whose cost can be bounded by a function of input in terms of distance from the optimal cost.

If we consider the optimization version of subset-sum problem, it says

> Given a set $A$ of integers, what is the maximum value of $sum(B) \le t$ where $B \subset A$, $sum(B) = \sum{b\in B}$ and $t \in Z^+$

In this problem, we know that we search for a maximum value that is smaller than or equal to $t$. So, a solution $B\_1$ is better than another solution $B\_2$ if $\dfrac{sum(B\_1)}{sum(OPT)} \> \dfrac{sum(B\_2)}{sum(OPT)}$, $OPT$ being the optimal subset.

Now, let us consider the WSN localization problem, which is defined as:

We have a set $A = \\{1,2,\dots,n\\}$ of $n$ points in $d$-dimensions. We only know the coordinates of some points, let us denote them with $B = \\{b\_1, b\_2, \dots, b\_m\\}$ where $B \subset P$. By using the positions of the nodes in $B$, we aim to assign positions to the nodes in $A$. While doing this, we use the Euclidean distance graph $G = \<V,E,W\>$ that is given as input. In this graph, each node $i \in V$ corresponds to a point $i \in P$ and each edge $\\{i,j\\} \in E$ means that there is a distance measurement between the point $i$ and point $j$. The weights of an edge corresponds to the Euclidean distance between two points.

We use a unit disk graph (UDG) model. In a UDG, an edge $\\{i,j\\}$ exists if and only if the Euclidean distance $\delta\_{ij}$ between $i$ and $j$ is smaller than or equal to a specific value $R$. That indicates if there does not exist an edge $\\{i,j\\}$, then $\delta\_{ij} \> R$.

We aim to assign coordinates to each node $v \in V$ considering their Euclidean distances. This process is called *localization*.

As the motivation is wireless sensor nodes, we assume that we cannot measure distances with 100% accuracy. Therefore, each distance $\delta\_{ij}$ is altered by adding a value $\epsilon$ to model the environmental noise. For any two points $i,j$ whose pairwise distance is $\hat{\delta}\_{ij} \< R$, the given distance is $\delta\_{ij} = \hat{\delta}\_{ij} + \epsilon$.

$\epsilon$ is up to $\pm P\\%$ of the wireless range $R$ selected from a uniform random distribution. Let us assume that we always can localize %100 of the nodes i.e. the input graph is localizable. Our objective is to minimize the average localization error. This is computed by $\dfrac{\sum\limits\_{v \in V}||v\_{est} - v\_{act}||}{|V|}$, where $v\_{est}$ is the estimated position of node $v$, $v\_{act}$ is the actual position of node $v$ and $||v\_{est} - v\_{act}||$ denotes the Euclidean distance between two.

The optimal solution for any instance is clearly $\forall v \in V, v\_{est} = v\_{act}$ and the cost is $cost(OPT) = 0$.

In subset sum, we know how close we are to the value $t$ and can compare two solutions. In traveling salesman problem, we can compare the solutions by their costs. However, in localization problem, we cannot compare two solutions without knowing the actual positions, which is impossible by the definition of the problem.

My question is: Can we anyhow prove if WSN localization problem is approximable or not by not being able to know how good a solution is? Or is it completely irrelevant?

For further reading, here is the NP-hardness proof of the localization problem with noisy distances. This paper defines the formal theory of the same problem.

# Answer
> 2 votes
## Definition of a well-formed optimization problem

It seems to me the core problem you have here is that the problem you have defined is not what I'd call a well-formed optimization problem. Normally, an optimization problem looks something like this:

Input: $x$
Goal: find $y$ that maximizes $\Phi(x,y)$

where $\Phi$ is some objective function that's specified as part of the problem statement. The key point here is that the objective function has to be computable, as a function of the input and the proposed output.

Your proposed formalization of the WSN localization problem does not have this form: the objective function is not computable as a function of the information known to us. Therefore, it is not a well-formed optimization problem.

This explains the problem you're having. The reason you can't compare how good different solutions are is that you don't have a computable way to measure how good a single solution is, given the information available to you. Consequently, your problem does not fit into the standard framework of optimization problems and approximation algorithms. This means you can't take advantage of all that theory, and strange things can happen.

So, at this point you have two options. First, you can try to formulate your problem as a way that *does* qualify in this framework, i.e., where you do have a computable objective function. The other option is to accept that you don't fit into this framework and you'll have to develop everything from scratch without being able to use the existing framework as is.

Another way to put this: if your objective function depends on values that aren't known (aren't part of the input), then what you haven't is not purely an algorithmic problem. To make this an algorithmic task, you need a way to measure success. One candidate way to do this would be to establish some probability distribution on the locations of the sensors, then frame this as a statistical inference problem, where you want to find the maximum likelihood estimate, or something like that.

Another approach would be to choose a different objective function, that *is* computable. For instance, maybe you could evaluate the accuracy of a solution in terms of how closely it matches the givens: for what fraction of edges $\\{v,v'\\}$ do we have $||v\_\text{est}-v'\_\text{est}|| \< R+\varepsilon$, and what fraction of non-edges $v,v'$ do we have $||v\_\text{est}-v'\_\text{est}|| \> R-\varepsilon$; maybe the objective function is the sum of these two fractions, or something. Of course, this is a different objective function, so it's maximizing something different, and the solution to that optimization problem might or might not match what you're actually looking for.

---

For posterity, here's some feedback on an older version of the problem, which has now been addressed by the revised question.

I see some misconceptions in this question, both about how we measure the quality of approximations, and about when approximation algorithms are applicable. The best answer I can give is to clear up these confusions/misconceptions; that will help you think about this kind of problem more clearly.

## Definition of the approximation ratio

You have a confusion about how we normally measure the quality of an approximation, in the standard theory of approximation algorithms. This shows up in your discussion of approximation algorithms for subset sum.

With subset-sum, the objective function we are maximizing is $\text{sum}(B)$. In the standard theory of approximability, we measure the quality of an approximation by how good the value of $\text{sum}(B)$ is, compared to the optimal value of that for the optimal choice of $B$ -- *not* compared to $t$.

When we ask whether there is a $2$-approximation for subset-sum, we ask whether there's an algorithm that outputs a set $B\_\text{approx}$ such that

$${\text{sum}(B\_\text{approx}) \over \text{sum}(B\_\text{opt})} \ge 1/2,$$

where $B\_\text{opt}$ is the optimal solution (the one that maximizes $\text{sum}(B)$). The ratio on the left-hand-side is called the *approximation ratio*. Notice how $t$ doesn't appear in this quantity. The approximation ratio is defined with reference to the optimal solution, not with reference to $t$.

## When approximation algorithms are applicable

Approximation algorithms are only applicable to optimization problems.

The "WSN localization problem", as you have defined it, is not an optimization problem: it is a decision problem. Since it's not an optimization problem, the entire concept of an approximation algorithm doesn't enter into it.

Asking "is it approximable?" is a category error: it's like asking "Is 'flying' a mammal?" -- 'flying' isn't even a noun, let alone an animal.

You then talk about two metrics. If you pick *one* of those metrics, you could define an optimization problem that is based upon the "WSN localization problem", where you ask to find the placement of node positions that complies with all the constraints and that maximizes (or minimizes) that metrics. Then you *would* have an optimization problem.

However, when you have two metrics, we don't get a well-defined optimization problem, since it's not clear what would count as optimal. Indeed, there might be multiple solutions that each achieve a different tradeoff between these two metrics, and is "Pareto-optimal". (See also What is a bicriteria approximation algorithm?.)

So, to count as an optimization function, you have to be maximizing/minimizing a *single* objective function; the standard theory of approximation algorithms is only applicable when you have a problem that is of this form. If your problem isn't of this form, it probably doesn't make sense to ask if it is approximable, as standard definitions of approximability don't apply.

---
Tags: algorithm-analysis, proof-techniques, approximation
---


# Question
Title: How can I infer inputs to a function, given an output?
Is there a way to generate a set of inputs, for a given output of a function? This may be a common thing in lisp/haskell world, but I'm not aware of it. Is this what mini-kanren does?

I understand that there may not be a general solution to this problem, since the halting problem may apply here. Say the function implementation is constrained to remove unlimited recursion. Type inference engines obviously do something similar to figure out the types of variables, I would like to generate actual values.

I'm thinking of a couple of scenarios where this might be useful:

```
func blowup(x): 1/x

```

I would like some sort of static checker to figure out that this function will cause problems if x=0.

```
func launch(x): ...launch missle x miles...
func isSafe(y): if x > 10 then true else false
func main(): x=.1; if isSafe(x): launch(x)

```

In this case, I would like to not only infer values of launch, but I would like to take isSafe as a constraint and tell me at compile time (since all information is available) that x of .1 not a good value.

Btw, I'm not looking for a library to do this. What I would love is either the name of this concept (beyond the generic 'static checking') and reference material which describes this idea (easily read papers, books, etc.). I should also mention that I'm aware of tools such as quickcheck. I'm not looking for a probabilistic way of inferring values. I would like a deterministic way of inferring values as early as possible, even if that means that my solution limits the types of expressions I can express.

# Answer
In the worst case, this is impossible. However, there are techniques for inversion that can work on some programs. Of course, you shouldn't expect them to work on all programs given that the problem is hard.

Here are a few standard approaches:

* **Theorem proving.** Use the VCGen part of a theorem prover to generate a precondition formula, where if the formula is true, that implies that the function produces the desired output (or divides by zero, etc.). Then, use an automated solver to try to find a satisfying assignment to that formula.
* **Symbolic execution.** Execute the function symbolically, and build up a symbolic expression that represents the output of the function, in terms of a bunch of variables (unknowns) that represent the inputs to the function. Then build a formula by setting that expression equal to the desired output, feed that formula to a SMT solver and ask the solver to find a satisfying assignment for the formula.
* **Concolic execution.** Pick concrete values for the inputs to the function. Execute the function on those inputs and record what path it took. On the side, build up a symbolic expression that represents the output of the function, if it follows the same path. Build up a "path constraint", which is a formula that is the conjunction of all of the branch conditions followed: the path constraint is a formula over symbolic variables representing the inputs, where inputs that make the path constraint true will cause the function to execute the same path that was previously recorded. Then, write down a formula that represents the statement "the function takes that path, and its output is equal to the desired value", and feed this to a SMT solver or SAT solver and ask it to find a satisfying assignment. See concolic testing.

These approaches have different tradeoffs and perform differently, but as you can see, they are similar conceptually. Here are some significant differences:

* Theorem proving and symbolic execution can have problems with loops. For instance, theorem provers usually require you to supply a loop invariant for every loop. Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
* Theorem proving and symbolic execution can have problems with state space explosion, as the number of possible paths through the function can be exponentially (or even infinitely) large. Concolic execution circumvents this by not trying to reason about all possible paths; only a single one.
* Theorem proving can use more expressive logics, such as fist-order logic. Symbolic execution and concolic execution often use propositional logic or a SMT extension.

You can find lots of reference material on these approaches. For instance, today they're taught in a number of advanced (e.g., graduate) program analysis courses, and there are many publications in the research literature on these topics.
> 3 votes

# Answer
To find possible input values (or at least a superset) given a set of possible outputs is called *backward constraint propagation*. This is done inside many kinds of program analysis: formal verification, compiler optimizers, defect search, ...

It's more common for type checkers to do forward propagation. For example many languages require type annotations on function arguments and infer the types of expressions. Languages like ML that do full inference don't really distinguish between forward and backward propagation.

There's no general rule to tell when backward constraint propagation can be useful. To take just one example, consider a cryptographic hash function with a fixed-size input string. From a theory of computation point of view, each hash value has a finite set of preimages and you can run a Turing machine with an obvious termination argument to enumerate them all. But once you take complexity into account, this enumeration is impractically slow; in fact the very definition of a cryptographic hash requires that this computation be intractable.
> 2 votes

---
Tags: programming-languages, logic
---


# Question
Title: Algorithm that finds concise representations of sets of pairs using Cartesian products
I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.

Suppose as an input you have a list of two-dimensional data points (xi, yi). Your goal is to "simplify" this data by providing an output that is equivalent to the input, but grouped together using structures like this: ({x1, x2, .., xn}, {y1, y2, .., ym}), which denotes a set of all (xa, yb) where a ∈ {1, 2, .., n} and b ∈ {1, 2, .., m}. A perfect result is to have as few of these structures + remaining data points as possible.

Some points to consider:

* The output can be a combination of simple data points and such structures.
* The structures in the output should be mutually exclusive.
* It may as well be that there is no way to simplify a given input.

Example 1:

`Input: (1, 1), (1, 2), (2, 1), (2, 2), (4, 5) Output: ({1, 2}, {1, 2}), (4, 5)`

Example 2:

`Input: (1, 1), (1, 2), (1, 3), (4, 5) Output: ({1}, {1, 2, 3}), (4, 5)`

Example 3:

`Input: (1, 2), (2, 2), (3, 2), (2, 1), (2, 3) Output: ({1, 2, 3}, {2}), ({2}, {1, 3})`

# Answer
For a given set $S$ of points, we construct a bipartite graph $B=(X\cup Y,E)$ such that there is an edge $(x,y)\in E$ iff there is a point $(x,y)\in S$. The biclique decomposition problem asks for the minimum number of bicliques (complete bipartite subgraph) of $B$ whose edges partition the edge set $E$ of $B$. Since a biclique in $B$ corresponds to a structure defined in this problem, an algorithm that solves the biclique composition problem also solves this problem.

Conversely, we can also transform the biclique decomposition problem into this problem as follows. Given a bipartite graph $B=(X\cup Y,E)$, where $X=\\{x\_1,x\_2,\ldots x\_p\\}$ and $Y=\\{y\_1,y\_2,\ldots y\_q\\}$, we create a set $S$ of points such that $(x\_i,y\_j)\in E$ iff there is a point $(i,j)\in S$. Consequently, the problem is equivalent to the biclique decomposition problem. However, the biclique decomposition problem is NP-hard, and therefore it is unlikely to solve it efficiently on general bipartite graphs. Note that the problem is equivalent to \`\`biclique cover'' if the structures are allowed to be overlapped, i.e., a point can be in more than one structure.
> 1 votes

# Answer
EDIT : **bangye**'s answer above was correct. construct a bipartite graph where each edge is one of your points, each vertex on the left is one abscissa, and the vertices on the right are the ordinates. then apply some biclique decomposition algorithm.

---

if I understood your notation well, where $(\\{1,2\\},\\{5,6\\}),(3,3)$ means $2$ groups, the first with $4$ points ($x = 1$ or $2$ and $y = 5$ or $6$) and the second with $1$ point.

* input : $N$ points, all with integer coordinates
* output : $M$ groups, containing all the information (and no more) of the $N$ points, and we want to minimize $M$

the naive algorithm would be :

* simply start with $M = N$ groups, each containing only one $x$ and one $y$
* then, if possible, group $2$ of these $M$ groups to get $M-1$ groups
* repeat that while necessary

but unfortunately, this doesn't work, we won't minimize $M$ this way.

consider an entry of $3$ points, disposed as a right triangle $(1,1),(1,2),(2,1)$. you can divide it in $2$ groups in $2$ different ways : $$(\\{1,2\\},1),(1,2) \qquad\text{ or }\qquad (1,\\{1,2\\}),(2,1)$$
> 0 votes

# Answer
While there doesn't exist a non NP-Hard optimal algorithm, here is one way to solve it. I'm going to assume 0-based indexing of the $x\_i$s and $y\_j$s to simplify below.

Encode the $x$'s using $s+1=\lceil \log n\rceil$ Boolean variables; let's call these $a\_0...a\_s$ Encode the $y$'s using $t+1=\lceil \log m\rceil$ Boolean variables; let's call these $b\_0...b\_t$

Then (x,y) maps to a conjunction of literals: E.g. Assuming we have 16 x values, and 16 y values: x0 == 0000, x1=0001, etc. y0 = 0000, y1=0001, ... (x0,y1) = (0000,0001) or $\overline{a\_3a\_2a\_1a\_0b\_3b\_2b\_1}b\_0$.

Then you can represent all your values as a DNF. (x0,y1) OR (x1,y1) OR ... in literal form.

After that you then want to "compress" the output, that is you want to find the smallest equivalent DNF (this is called logic minimization). There are numerous ways to do this, see e.g. Espresso. From the resulting DNF you then need to go back to your desired output form. In your case, don't cares get expanded in terms of the sets. Thus if we had $\overline{a\_3}\overline{a\_2}b\_3b\_2b\_1$ this would be: {(0,1,2,3),(14,15)}

Note that when performing the logic minimization, the "out-of-range" values, should make up the Don't Care set. Thus, if there were 15 values for x and 15 values for y, the DC set would be {1111\*, \*1111}. This is because we don't care what the DNF value is for these inputs, since they are out of range anyway.
> 0 votes

---
Tags: algorithms, sets
---


# Question
Title: BSS-model Computational complexity of finding the roots of a polyomial
I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial with real coefficients.

Now, what exactly are the implications for my problem?

It is well-known that there is no *formula* that describes the roots of a polynomial of degree $\geq 5$ and, as far as I know, there is no general algorithm that computes the roots exactly. But are there results stating that the problem is computationally intractable in general? Or is it a common assumption? My question is not aiming at existence results or approximation algorithms but at the *computational* complexity of the problem and possible implications for my problem.

Note: My algorithm works in the Blum-Shub-Smale model, so the possibly infinite representations of the solutions don't bother me.

# Answer
> 6 votes
It's not too hard to find the real roots of a univariate polynomial, for example by using Sturm's theorem which allows you to easily identify the number of sign changes of a real-valued polynomial between two given bounds.

I believe it's not too hard to show that this technique, coupled with a simple divide-and-conquer technique or Newton's method and an elementary bound on the absolute value of the largest root as a function of the coefficients, gives a polynomial time algorithm for finding the roots of a polynomial, in the time of the degree $n$ and the desired precision $p$ (in digits).

For more information see the wikipedia article or this mathoverflow question.

---

Edit: The question was clarified to ask about **exact** solutions in the Blum-Shub-Smale model. In this situation, it is already impossible to get *square roots*, in particular to get exact solutions to the equation $$ X^2 - 2 = 0$$

This result (and a much more general one) is proven in this paper by Calvert, Kramer and Miller.

---
Tags: computability, reference-request, undecidability, polynomials
---


# Question
Title: Recursive definition of a language given the regular expression
Consider the language: $$ L\_1 = \\{ x \in \Sigma^\* : x \text{ does not contain the substring } 110\\} $$

I know that there is a DFA that accepts this language, and furthermore, that the regular expression is: $$ (0 \cup 10)^\* 1^\* $$

I'm asked to obtain a formal recursive definition of $L\_1$, that is, find a basis $B \subset \Sigma^\*$ and a finite set of functions on strings $\mathcal{F}$ such that $L\_1$ is the closure of $B$ under $\mathcal{F}$, i.e. $L\_1 = \langle B \rangle\_{\mathcal{F}}$

I'm not sure how to go about this. Every way I can think to "encode" the regular expression into "functions" that build the language they're really ugly or involve piecewise definitions (if $x$ doesn't end with 1, otherwise, etc.)

Is there a simple and clean way to do this?

# Answer
> 3 votes
Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction.

$B=\\{\epsilon\\}$

$\mathcal{F}=\\{X\to0X|10X|X1\\}$

$L\_1 = \langle B \rangle\_{\mathcal{F}}$

---
Tags: formal-languages, regular-languages, regular-expressions, recursion
---


title: Self-reducibility of Clique

text:
# Question
Title: Self-reducibility of Clique
I am trying to understand the following algorithm for Self reducibility of Clique.

Here we have a "MBClique" black box algorithm, which return yes/no for parameters where G is a graph and K is a natural number. It answers the question: "Does G has a clique of K size?" - Our aim is then to use this Decision algorithm to search what the actual Clique graph is.

Given this Graph below, we can see it has a clique of size 3.

The search algorithm is as follows (it was extracted from the CSE 200: Computability and Complexity @ UCSD lecture notes, page 4):

Ok, so now given an algorithm MBClique that returns yes/no we are trying to search the actual k-clique. Suppose the graph of the image above is sent as parameter and k=3.

1. In the first if it passes through.
2. In the immediate after For loop all edges that don't affect the size of the clique are removed.
3. Now my question: what is the Repeat...Until part of the algorithm for? In my understanding after the For loop I already have the respective Graph that I want as an answer.

Thanks.

# Answer
> 3 votes
The Repeat loop is not strictly necessary. The algorithm would still be correct without it. In fact, the Repeat loop actually has no effect, though proving this takes a little bit of work.

If the graph $G$ has no $K$-clique, then this procedure correctly halts. So assume the graph $G$ has at least one $K$-clique. The interesting case is where it has multiple $K$-cliques.

Associate each $K$-clique with a vector $(x\_1,x\_2,\dots,x\_K)$ representing the vertices of the clique, in increasing order. Now order these cliques by lexicographic order on the vectors. Let's focus on the $K$-clique whose corresponding vector is lexicographically largest; call this the "golden" $K$-clique. It is possible to prove that For loop removes everything but the "golden" $K$-clique: when the For loop terminates, all that remains is a subgraph containing exactly $K$ vertices, namely, the golden $K$-clique. Therefore, the Repeat loop does nothing.

In other words, you can remove the Repeat loop, and this procedure will always produce the same output. (In particular, you were worired that the Repeat loop might remove a vertex from an actual clique -- but the above reasoning shows that this can never happen.)

So, the Repeat loop is unnecessary. Why is it there? Maybe to make the proof of correctness for this algorithm a bit easier. But if you find the algorithm easier to understand if you omit the Repeat loop, go ahead and pretend it's been removed -- that will work, too.

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


title: How to extract randomness from a file?

text:
# Question
Title: How to extract randomness from a file?
I have a generator of files with approximately 7 bits /byte entropy. The files are about 30KB each in length. I'd like to use these as sources of entropy to generate random numbers. Theoretically I should be able to achieve about 26 KB (max) of randomness per file.

This is a hobby and I know about hashes, but they're primarily checksums. I'm looking for more sophisticated methods of extraction designed specifically for that purpose. I'm hoping to use this as a true random number generator.

Supplemental:

Following comments, and in order to solicit non hash based responses, I'm evaluating the following architecture...

It works like this:-

The entropy is the 30KB file

The compressor reduces the entropy to a target size of 26KB

A seed is derived from all of the bytes of the entropy

Some PRNG implementation produces 26KB of pseudo random output

The two outputs are xored together to produce true random numbers

So in summary, a 30KB file of 86% entropy is manipulated into a 26KB file of 100% entropy. Entropy is preserved throughout the extraction process, and all the output is totally dependant on the input. 26KB of full entropy goes in, and 26KB of full entropy comes out.

I suggest that this is a good method to extract entropy from complete files. Or not.

# Answer
> 6 votes
In practice, in about 95% of cases, the correct answer is probably going to be: forget about those files, use `/dev/urandom` or `CryptGenRandom()` (or equivalent). They provide very high quality random numbers -- That's what they're designed for. So this is the most pragmatic answer, and it will provide excellent quality randomness.

---

Let's say you can't do that, maybe because it's a headless embedded device with no access to entropy, or you want your random numbers to be a repeatable deterministic function of the files. Then in that case the best answer is likely to be -- guess what? -- hashing. In particular: concatenate all the files, take the SHA256 hash of the concatenation, and then use that as a key for AES-256-CTR; then use AES-256-CTR to generate as much output as you want. This is basically using a cryptographic hash to generate a seed for a cryptographic-quality pseudorandom generator, and it satisfies all your requirements. This is a solid answer, from the perspective of robust engineering and high quality random numbers.

---

OK, let's say you are a theorist. If you are a theorist, you won't like the last answer, because it relies upon cryptographic assumptions that have not been mathematically proven to hold. Pragmatically, you probably shouldn't worry about that -- you rely upon those assumptions every day (e.g., when doing e-commerce or entering your password into a website), and other issues are far more likely to affect you in practice -- but let's say you are a theorist.

From a theoretical perspective, the cryptographic solution is potentially unsatisfying, because it relies upon an unproven assumption, and that is... inelegant. So, it's interesting to ask what can be achieved that will provably work. If that's what you're interested in, you'll want to read about randomness extractors.

If you care about pragmatics, randomness extractors are probably not the best possible solution: extractors need stronger assumptions about the distribution of the data in your files, they are more limited in how much random output they can produce, and they are more fragile. But they *do* come with provably good properties, and they are mathematically elegant and beautiful.

# Answer
> 3 votes
OK, so the question has changed to "please review my construction for me". Let me try to help with a few principles first, and then some detailed analysis.

## Don't roll your own

If you're going to use this for anything serious, don't try to design it yourself. It's too easy to screw up. There's a long history of well-intentioned, smart people trying to design their own true random number generator, and messing up.

And what makes this worse is that if you get something wrong, you'll probably have no way of knowing: your algorithm will output numbers that have a bias, but how will you know? You won't know; your statistical algorithm will just give you bogus results that are slightly wrong, or your crypto algorithm will become insecure in a subtle and non-obvious way, or whatever.

## You probably don't actually need true random numbers

In my experience, 99% of people who think they want true random numbers don't actually need true random numbers. I often people look at pseudorandom generators, figure that the "pseudo" is bad, and figure "I want the best, so why would I mess with anything less than the best? obviously I want true not pseudo random numbers".

However that reasoning is flawed. Skepticism about garden-variety pseudorandom generators is healthy. But it's worth knowing that not all pseudorandom generators are created equal.

In particular, cryptographic-quality pseudorandom generators are special. The definition of "cryptographic-quality" is that no feasible adversary can distinguish their output from true random numbers (e.g., it takes exponential time to tell them apart from true random numbers). Thus, if you have a pseudorandom generator that *truly* is cryptographic-quality, it's every bit as good as true random numbers.

Now this does leave the question of whether a pseudorandom generator that's claimed to be cryptographic-quality, actually is. However, the good news is that there's been a lot of work on this in the crypto literature, and we have constructions that have been studied extensively and are widely believed to meet this requirement.

In contrast, anything you build yourself is not going to have been studied anywhere near as carefully. So, on the one hand we have well-vetted cryptographic pseudorandom generators that have been carefully studied by others. On the other hand we have a scheme you designed yourself that you think/hope outputs true random numbers. Which do you think is more likely to have a catastrophic flaw?

## Your scheme doesn't output true random numbers

With all those general principles out of the way, on to your specific scheme that you propose in the question. Unfortunately, your scheme is not guaranteed to output true random numbers.

In particular, let's be clear on what the requirement is. We want the output of your scheme to be uniformly distributed: each bit is a identically and independently distributed random bit, with equal probability of heads and tails. For a $n$-bit output, we want all $2^n$ possible outputs to be equally likely. And we want this to hold for every possible input distribution that has approximately 7 bits of entropy per byte.

Your scheme doesn't have this property. There are input distributions where your scheme falls apart.

For example, suppose that we compress the 30KB input file, and the output of the compressor is 30KB long. Then what are you going to do? Your specification doesn't actually say what to do, but it turns out that there is no good answer. If your answer is "truncate to 26KB, then xor with the output of the pseudorandom generator", that's a bad answer: the output might not be uniformly distributed. If your answer is "well, I'll just generate 30KB of pseudorandom numbers, xor them with the output of the compressor, and output all 30KB", that's a bad answer too: the output isn't uniformly distributed, and quite obviously cannot have more than 26KB of entropy, since no deterministic procedure can ever increase the entropy present in the input.

For instance, here's a simple input distribution you can think of, to hone your intuition. Imagine that each byte is generated using the following process: the low 7 bits are chosen uniformly at random, and the high bit is chosen deterministically as the parity of the previous 8 bytes of input. Then this has 7 bits of entropy per byte. However, no standard compressor is going to compress this stream of data; the output of the compressor will almost surely be about 30KB. Moreover, if you truncate the output of the compressor to 26KB, so the truncated result will probably have only about 23KB of entropy; the amount of entropy in the output of the PRNG is at most its seed length; so the xor of the two will have far less than 26KB of entropy and fails to be uniformly distributed.

Another problem with your scheme is that you haven't specified how the seed for the PRNG is chosen, nor what PRNG you'll use. Analysis of your scheme might depend heavily on these details.

There may well be more problems beyond this, but this is already enough to show that the scheme doesn't meet the requirements.

## What should you do instead?

Don't try to generate your own scheme. Re-assess whether you *really* need true random numbers (odds are you don't). Then, use an existing well-vetted high-quality source of random/pseudorandom numbers, e.g., `/dev/urandom` or `/dev/random` or similar.

---
Tags: randomness, entropy
---


# Question
Title: Will ternary computers be faster than binary?
If we had a computer in **base 3** which used the characters **`{0, 1, 2}`** instead of just **`{0, 1}`** (and we implemented a ternary logic on the hardware), will this computer be faster than computer using binary? Why or why not?

If we had a computer with even a higher base than **3** will it be more fast or slow? Which is the best base for fast processing and computation?

# Answer
It depends. A number represented in base 3 will have fewer digits than the same number in base 2. Perhaps this means computations will be faster, since you have to work with fewer digits. However, perhaps the operations will become slower (since they're more complicated) so there might be no net gain - or perhaps even worse performance! There's no way to tell how fewer, complicated operations will compare to more, but simpler operations.

Another consideration is arithmetic. If you are working in base 10, then division by 10 is really easy with divisions in other bases being more work. Similarly, in base 2, division by 2 is easy. In base 3, division by 3 would be easy. If your application requires frequent division by 3, then base 3 would be beneficial.
> 1 votes

---
Tags: computer-architecture
---