proxy.golang.org : github.com/nikolaydubina/go-hackers-delight
For better performance, it is advisable to avoid branches in simple functions. Right-to-Left Computability — a function mapping words to words can be implemented with word-parallel `add`, `substract`, `and`, `or` and `not` instructions if and only if each bit of of the result depends only on the bits at and to the right of each input operand. All these operands themselves depend only on right bits, so any of their composition also depends on the right bits. It can be shown that in the ordinary addition of binary numbers with each bit independently equally likely to be 0 or 1, a carry occurs at each position with probability about 0.5. If instruction set includes an instruction for each of 16 Boolean functions of two variables, then any Boolean function of three variables can be implemented with four or fewer instructions (and four variables with seven instructions). Comparison functions are a couple branch-free instructions that store result in the most significant bit. Overflow means result of operation is too large or too small to fit into the variable. Many hardware supply bits for overflow, but high-lever languages may not have access to it (rejected Go overflow proposal). Any multiplication can be decomposed in a summation of left shifts. For example, For every multiplication there are multiple paths possible that utilize registers and shifts. These paths can have fewer or more instructions and registers to accomplish this. In general, it is nontrivial to find minimum number instructions required and which these instructions are. Following theorem gives upper bound: "Multiplication of a variable x by an n-bit constant m, m >= 1, can be accomplished with at most n instructions of the type add, subtract, and shift left by any given amount." On many computers, division is very time consuming and is to be avoided. A value of 20 or more elementary Add instructions is usually needed and execution time is usually large. When the divisor is a constant, the division can be replaced by faster operations. Certain divisors have repetitive patterns in binary representation which allows to use few (~20) shift, add, subtract instructions to approximate residual and get quotient. It is not trivial how to generate such optimal code. Standard binary representation of an non-negative integer number is base 2. However, there are alternative bases, including complex numbers. Which base is the most efficient? It can be argued that under standard assumptions of hardware design (e.g. "cost of b-state circuit" is proportional to b) the most efficient base is 𝑒. However, it is not practical. Meanwhile, base 2 is only 5% more costly than base 3 and only 6% more costly than base 𝑒. Which is an interesting result, given base 2 is both convenient to use and is theoretically optimal. It is known, that there is no polynomial f(n) that produces a prime for every n.
Registry
-
Source
- Documentation
- JSON
purl: pkg:golang/github.com/nikolaydubina/go-hackers-delight
Keywords:
assembly
, binary
, bits
, book
, c
, logic
, risc
, showcase
License: MIT
Latest release: 8 months ago
First release: over 1 year ago
Namespace: github.com/nikolaydubina
Stars: 1 on GitHub
Forks: 0 on GitHub
See more repository details: repos.ecosyste.ms
Last synced: 4 days ago