<jupyter_start><jupyter_text>M11. Binary Representation I've so far deferred any exposition of the binary system, mostly for reasons which come down to expedience. There is nothing remarkable about positional notation, much less its specific manifestation in base 2 (which is all binary really is). It's only on two counts that I'll qualify the treatment that was originally given in ECE 112. First, the binary representation of an integer is merely a *representation*, a mapping from the integers to the set of bit vectors. Even constraining these mappings to bijections, we are left with $n!$ distinct mappings between any two sets of cardinality $n$, this latter point being illustrated by a simple permutation argument. On an $n$-bit architecture with $2^n$ possible states, we could actually maintain $(2^n)!$ different schemes of representing any range of integers of size $2^n$. On a 2-bit system, for instance, I could map $$0 \mapsto 01$$$$1 \mapsto 11$$$$2 \mapsto 00$$$$3 \mapsto 10$$and these would constitute a perfectly valid representation of the integers $\{0,1,2,3\}$. For that matter, so too would$$0 \mapsto 10$$$$1 \mapsto 01$$$$2 \mapsto 00$$$$3 \mapsto 01$$and 22 other bijections. Of these, we prefer the one corresponding to what is called the *binary system*$$0 \mapsto 00$$$$1 \mapsto 01$$$$2 \mapsto 10$$$$3 \mapsto 11$$for the reason that it is amenable to extant systems of arithmetic for positional notation (as opposed to non-positional notation: for example, the Roman numerals that were used&mdash;probably to deleterious effect&mdash;by the Latinate peoples). To be absolutely clear, we *could* implement architectures with integer representations in bases other than two. The Soviets built a *ternary* computer in the late 60s (with some notable success). Babbage's *difference engines*, built in the early 19th century, were decimal machines. Here, too, we have a means of discriminating between different options. Those of you who took Professor <NAME>ang's ECE 101 might remember him having mentioned (in passing) that the 'best' base is actually $e$. This choice is indeed optimal, subject to a metric known as the *radix economy*. The argument is easily sketched as follows:The radix economy of an integer $n$ with respect to a radix (base) $r$ is defined as the number of symbols required to express $n$ in base $r$, counterweighted by $r$ itself:$$E(n,r) = r\log_r n.$$Thus, the radix economy punishes bases that are too large ($r \to \infty$) or too small ($\log_r n \to \infty$). Of course, for a fixed $n$ we can solve $$\hat{r} = \operatorname*{argmin}_r E(n,r) = \operatorname*{argmin}_r r\log_r n = \operatorname*{argmin}_r \frac{r}{\ln r}.$$Now notice\begin{align}& \frac{d}{dr}\frac{r}{\ln r} = \frac{-1}{(\ln r)^2} + \frac{1}{\ln r} = \frac{\ln r -1}{(\ln r)^2} = 0\\&\Rightarrow \ln r - 1 = 0 \\&\Rightarrow \hat{r} = e\end{align}which is the desired result. Since the notion of a non-natural (in fact, transcendental) base is somewhat troublesome, we invoke one of the corollaries of the Fundamental Theorem of Engineering,$$\sqrt{g} = \pi = e = 3,$$and pronounce that 3 is a 'close-enough' optimum. In practice, however, we still opt for base 2 owing to other considerations I will not be discussing in this memo. The point I'd like to illustrate is that the binary base is a *choice*, as is the decision to use positional notation.My second point concerns arithmetic. Notwithstanding the limits of space and memory, there are some things that we fundamentally cannot do with the integers $\mathbb{Z}$. In particular, the ring $\langle \mathbb{Z}, +, \times \rangle$ is not a *field*. The object does not contain a multiplicative inverse, with the consequence that we cannot find general solutions to equations even of the linear form$$ax = b.$$Division, correspondingly, is not tractable in $\mathbb{Z}$:<jupyter_code>import numpy as np

print(np.int8(np.int8(5)/np.int8(3)))<jupyter_output>1<jupyter_text>This is not the failing of any particular discipline of engineering; it is a limitation of an otherwise 'nice' mathematical object. The ring $\langle \mathbb{Z}, +, \times \rangle$ is not a field, but rather, an *integral domain*&mdash;within it, among other things, we can add, subtract, and multiply with familiar impunity. When we want to divide, we indulge in the rational numbers $\mathbb{Q}$ (which *are* a field). When we want to express the diagonal of a unit square ($\sqrt{2}$) we further indulge in the reals $\mathbb{R}$. In turn, when we want to find solutions to an equation of the form $x^2 = -1$, we refer to the complex numbers $\mathbb{C}$. Thus may the orthodox mathematical curriculum be traced, starting from the 'pre-school' numbers $\mathbb{N}$. Right now, we concern ourselves with the representation of the 'elementary-school' numbers $\mathbb{Z}$, otherwise known as the integers.Computers have finite states, so we immediately constrain ourselves to 'modeling' $\mathbb{Z}$ with a finite ring. The most natural way to do is to construct the ring of the integers modulo n: $\langle \mathbb{Z}_n, +_n, \times_n \rangle$. This is also known as 'clock arithmetic'. Suppose $n = 12$:$$1 + 2 = 3 \pmod{12} = 3$$$$5+8 = 13 \pmod{12}= 1$$$$3 \times 5 = 15 \pmod{12}= 3$$$$7 \times 1 = 7  \pmod{12}= 7.$$This preserves most of the behavior of $\mathbb{Z}$&mdash;in fact, if $n=p$ for some prime $p$, we obtain a *finite field*, but we do not need to go this far (if you find this sort of thing interesting, you may want to look into taking MTH 236). On a binary computer, $n$ is some power of $2$. NumPy allows us to explicitly work with unsigned 8-bit integers ($n = 2^8 = 256$), among others:<jupyter_code>myEightBitInteger = np.uint8(23)
print(myEightBitInteger)<jupyter_output>23
{'fraction_non_alphanumeric': 0.102915654286706, 'fraction_numerical': 0.02117320374869837, 'mean_word_length': 4.694664031620554, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '63474', 'license': 'Unlicense', 'n_tokens_mistral': 1691, 'n_tokens_neox': 1528, 'n_words': 850, 'path': 'M11_Binary_Representation.ipynb', 'repo_name': 'brekekekex/computer_organization_memoranda', 'size': '5766'}