January 2021, The Art of Code

Bits: Beyond Numbers

January 4, 2021January 28, 2021 alex1 Comment

The atom has taught me that the little things do count – most
Sri Chinmoy

A bit (short for binary digit) is the smallest unit of data in a computer. A bit has a single binary value, either 0 or 1

As promised in my last post, we will dig into the theoretical knowledge required more directly, and I will only reference history once in a while. I will separate the first two posts into another series that I do plan to continue at some point. If interest is high in the history-driven version, I will reconsider continuing the story earlier than “at some point”.

(computing) bit synonyms: boolean, binary value

A bit

How do we represent a bit? In modern computing, depending on the programming language used, it is either something called a boolean type (false/true) or a numeric type taking only the values 0 and 1. We can arbitrarily choose hilarious alternatives of representation in our theories. For now, let’s stick to known conventions and examine the numeric version to study their properties.

How is a single bit used? Bits are values; they don’t perform actions. However, as we have for millennia, we can assign meaning to things. Values are easy targets for this approach. We know bits can take the value of 0 or 1, so we can assign names/meaning to these two states.

We can, for example, store answers to yes/no questions: Does Mary have a little lamb? Is this number prime? Is this pixel white? The way we would do this is to designate “1” as representing “yes” and “0” as representing “no.” So if Mary sold her little lamb for profit and no longer has it, the answer to the question “Does Mary have a little lamb?” in its bit form would be “0.”

Boooring! Wait, there’s more. Can we use more than one bit? We sure can. Modern programs use more than thousands of millions of bits in their operations. But let’s start small.

Multiple bits

What could we do with two bits? We can answer two yes and no questions, but that’s still not exciting. We know that each bit can be either 0 or 1, so let’s list all the possible pairs of bits that wecan represent:

If one bit can have the values:
0
1

One way to obtain all the possible pairs by first putting a 0 and then a 1 in front of the possible values of a bit (we will learn other methods later).
[0, 0]
[0, 1]
[1, 0]
[1, 1]

(we will use this [] notation for grouping things together, other common notations use {} or even ())

If we were interested in all the possible values for a group of 3 bits, we could repeat the same process, to put a 0 and then a 1 in front of the possibilities for 2 bits:
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

Try listing all the possible 16 pairs of 4 bits on your own. Another thing to remember is that a group of n bits can represent 2ⁿ values, as we can observe that the number of possible values doubles with each addition of a bit. (more theory on that later)

Sticking to two bits, it appears that adding a bit has increased our storage space to 4 possible states (2²).

The natural/conventional mathematical meaning of the bit groupings mentioned above comes from base-2 to base-10 conversions (Details in the previous post):

[0, 0] is 0
[0, 1] is 1
[1, 0] is 2
[1, 1] is 3

However, on top of answering yes/no questions or assigning numbers to these states as shown above, we can also, for example, assign this meaning to our states in an attempt to encode the spelling of “mary” like this:

[0, 0] is m
[0, 1] is a
[1, 0] is r
[1, 1] is y

Using this substitution, we can spell ‘mary’ with groups of two bits from this encoding like:

[0, 0] [0, 1] [1, 0] [1, 1]

And ‘army’ would be encoded like:

[0, 1] [1, 0] [0, 0] [1, 1]

Even more, we could instead assign these meanings to have the two bits store the answer to questions with 4 possible answers. For example, we could describe whether a given colour is red, white, blue, or another colour:

[0, 0] is red
[0, 1] is white
[1, 0] is blue
[1, 1] another colour

By further expanding the storage space to more than two bits, the sky is the limit for how many states you can represent.

For example, when talking about a digital image, one measure of the quality of the image is the colour depth of the image, measured by something called bpp (bits per pixel). That is, as you might have guessed, how many bits of storage are used to represent one pixel in the image. So for a 32-bpp ARGB(more on that later) image, 32 bits for each pixel are used, with 8 bpp used to numerically represent each colour channel (red, green, and blue) and 8 bpp used to numerically describe the degree of transparency for that pixel.

[move to Boolean Logic/functionality/decisions based on bits] Is there anything else we can do with two bits? We said bits are values. We need to introduce a few simple concepts before we can do that fully.

Logical Operators

Operators are rules that bind terms together. Terms are either values or variables. Operators can be unary or binary depending on whether they apply to a single term or are used to combine two terms into a single term. When a unary operator occurs, it takes precedence over any binary operator involving that bit. Just like in mathematics, statements can be chained and parentheses can be used to group operations.

To start, we’ll introduce the unary operator NOT and the two most common binary operators: AND and OR.

AND

The AND operator is a binary operator that combines two bits into one bit and is only 1 when both bits are 1. So: 1 AND 1 is true, every other pair is 0.

Typical use: Evaluating if all requirements out of a list of mandatory requirements are met.

OR

The OR operator is a binary operator that combines two bits into one and is 1 when any of the two bits is 1. So: 0 OR 0 is false, every other pair is 1.

Typical use: Evaluating if any requirement out of a list of possible requirements is met.

NOT

The NOT operator is a unary operator that inverts the state of a bit. In other words, NOT 1 is 0, and NOT 0 is 1.

Typical use: TBD

Variables and Assignment

I promised we’re not focusing on any programming languages in this series, but we do need to develop a pseudo-code language to move things forward.

Let’s define “variable” as something which has a name and can hold a value, like x in mathematics. Also, let’s define the operator “:” as a binary operator between a variable and a value. The rule is:

x:0

means “x takes/stores the value of 0”. Whenever you mention x after this statement, you can think of it as “getting the value that x has.”

Multiple Bits in Practice, with variables and operators

Operators make it possible for us to find new uses for multiple bits. Let’s say George is trying to get a driver’s license. Then, instead of grouping our bits, we can use multiple “individual” bits to store answers to some questions:

medicalExamPassed: the answer to Did George pass the medical exam?
theoreticalExamPassed: the answer to Did George pass the theoretical exam?
roadTestPassed: the answer to Did George pass the road test?
feesPaid: the answer to Did George pay the required fees?

So finally, by using the AND operator, we can answer the question “Will George receive his license soon?” with:

licenseOnTheWay: medicalExamPassed AND theoreticalExamPassed AND roadTestPassed AND feesPaid

Let’s design a system combining all that we have learned today (bits, variables, assignment and logical operators):

taxesOverdue: the answer to "Is the tax deadline overdue?"
paidTaxes: the answer to "Did George pay his taxes?"
isTaxExempt: the answer to "Is George tax-exempt?"
shouldGeorgeBeWorried: taxesOverdue AND NOT(paidTaxes OR isTaxExempt)

Of course, the possibilities are endless here, and I invite you to think of more examples and uses on your own. I am working on having some interactive parts through the series to facilitate the learning. Meanwhile, text is all we have ?

Hope you enjoyed this session! The next part of our journey will be to look at how groups of bits are used to encode numbers. Until next time!

Bits: Numbers as Bits (Part I)

January 3, 2021January 28, 2021 alex1 Comment

If you think dogs can’t count, try putting three dog biscuits in your pocket and then giving Fido only two of them.
Phil Pastoret

In mathematics, a base or radix is the number of different digits that a system of counting uses to represent numbers. the most common base used today is the decimal system. Because “dec” means 10, it uses the 10 digits from 0 to 9.
Wikipedia

As promised, we’re taking a step back from the historical approach for now. Our journey continues with some context which will make it easier to work with and reason about bits and binary numbers.

There is a lot of information online covering numerical bases and their properties. Here, we will focus on demystifying the basics by presenting them in a more straightforward language.

What is a Bit?

The bit is a basic unit of information in computing and digital communications. The name is a portmanteau of binary digit.^[1] The bit represents a logical state with one of two possible values. These values are most commonly represented as either “1”or”0″, but other representations such as true/false, yes/no, +/−, or on/off are common.
https://en.wikipedia.org/wiki/Bit

A bit is functionally a two-state switch. Think of an ordinary “mechanical” one-button lightswitch. Just the lightswitch, not tied to anything else. It can only have two states, which you can observe visually: up or down, pushed or not pushed, etc. A bit is a lot like that: it can hold either a value of 0 or a value of 1.

Of course, you can assign more meaning to a bit than just 0 and 1, and we will discuss this possibility in one of our next posts. In this article, we will look at 0 and 1 as numbers.

What is Counting?

Counting is the process of determining the number of elements of a finite set of objects. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for every element of the set, in some order, while marking (or displacing) those elements to avoid visiting the same element more than once, until no unmarked elements are left; if the counter was set to one after the first object, the value after visiting the final object gives the desired number of elements.
https://en.wikipedia.org/wiki/Counting

Everyone is familiar with counting. It’s part of our everyday lives. However, much of this happens automatically through memorized patterns, so we’re not usually aware of the details of what is going on when we count.

I find the above-mentioned definition, while correct, possibly confusing to some people. What is counting? Just count, use numbers.

In layman’s terms, you start with a pile of things that you need to count, and start moving them to another pile. As you do that, you use a mental or physical counting board/abacus to keep track of how many objects you have moved so far.

Hypothetically, if you had an abacus with a single column, with the same number of beads as the objects you are trying to count, then that single column would be enough to “physically count”, without putting names to numbers. But (natural) numbers, though countable, are infinite. So we need to reason about them in more abstract ways.

As a practical totally fabricated example, let’s say you are an ancient-times merchant and you own a single column, ten-bead abacus, and each week you know you have to receive ten animal skins as part of a trade agreement. With little instruction, you’d for sure be able to know whether there are ten animal skins in a pile or to take ten animal skins from a pile using this method, never knowing about numbers.

When the number that you need to count increases, it becomes impractical to use that single column method. How would you come up with the number if there were, say 3000 beads on the single-column without recounting? How would you deal with interruptions?.

Assigning a name or symbol for that quantity also becomes paramount. That’s where numerical systems, or thinking of quantities as “piles of piles” come into play (more on that below). In a sense, numerical systems are there to help us communicate by naming quantities.

There are some … who think that the number of the sand is infinite in multitude … again there are some who, without regarding it as infinite, yet think that no number has been named which is great enough to exceed its multitude … But I will try to show you [numbers that] exceed not only the number of the mass of sand equal in magnitude to the earth … but also that of a mass equal in magnitude to the universe.
Archimedes, 3rd century B.C., The Sand-Reckoner

Archimedes made a surprisingly accurate prediction for the number of m grains of sand that would fit in the universe in his writing The Sand-Reckoner. And this approximation was fueled by trying to name some “mass equal in magnitude to the universe”. He needed to know what the universe’s “mass” would be, to exceed it Even as far back as the 3rd century B.C. naming big quantities was important, and to this day mathematicians fight about who can name the biggest number.

Counting in Base 10 (Decimal Base)

Let’s take a trip down memory lane to refresh our memories and break down the counting process into its integral parts.

We count in piles of 10, even if we don’t always think about it. An example of these piles are the columns of the counting board below;
Our piles each represent a digit from 0 up to 9;
The pile on the left of another pile “stands for” an amount 10 times bigger. In other words, in our counting board below, the rightmost column stands for digits, the middle column stands for tens and the leftmost column stands for hundreds;
The thought process for going beyond 9 within any pile while counting is: “I have reached the maximum amount I can make in this pile. I need to start a new pile here and add one to the pile on the left”; If the pile on the left had also reached its maximum, we apply the same rule to that pile, and so on;
In reality, we don’t have a hard limitation on the number of digits; we can always add one more pile to the left, following the same rule.

You can use the numerical input box to play around with the board see these concepts in action:

A few observations about the board:

There are three columns on the board, each one representing a digit. Thus, the board can represent numbers from 0 to 999.
Columns each have 9 beads that can be moved around to represent a digit. In other words, we have a "name" for each of the ten states of a column;

Counting in Base 2 (Binary Base)

What about counting in binary? Let's copy-paste our rules from the previous section and adapt them to having only 0 and 1 as digits. You can adapt these rules, in a similar fashion and apply them to any other base of your choosing.

We count in piles of 10 2, ~~even if we don't always think about it~~. It will get some getting used to. An example of these piles are the columns of the counting board below;
Our piles each represent digits from 0 up to 9 1;
The pile on the left of another pile "stands for" an amount 10 2 times bigger. In other words, in our counting board below, the rightmost column stands for digits, the middle column stands for ~~tens~~ twos and the leftmost column stands for ~~hundreds~~ fours;
The thought process for going beyond 9 1 within any pile while counting is: "I have reached the maximum amount I can make in this pile. I need to start a new pile here and add one to the pile on the left"; If the pile on the left had also reached its maximum, we apply the same rule to that pile, and so on;
In reality, we don't have a hard limitation on the number of digits; we can always add one more pile to the left, following the same rule.

You can use the numerical input box to play around with the board see these concepts in action:

A few observations about the board:

There are three columns on the board, each one representing a binary digit. Thus, the board can represent numbers from 0 to 111 (in binary). corresponding to 0 to 7 (in decimal);
Columns each have 9 1 beads that can be moved around to represent a digit. In other words, we have a "name" for each of the ~~ten~~ two states of a column;

So how do we know that 7 is the largest number with 3 binary digits? Well, we know the maximum for each column is 1. We also know that the columns' values per unit are 4, 2, and 1, respectively. Remember that each time we "move left" through the "binary" piles the column's value per unit doubles. Adding 4 * 1 , 2 * 1 , and 1 * 1, we get 7.

We'll cover this in more detail in the next post when we will cover base conversions. Afterward, we will dive deeper into the particularities of bits and the binary numerical system.

I hope you've enjoyed this small math reminder on numerical bases, and I hope to see you next time!

The History: Finding a 0

January 2, 2021January 28, 2021 alex4 Comments

A zero itself is nothing, but without a zero you cannot count anything; therefore, a zero is something, yet zero.
(a) Dalai Lama

“Zero began its career as two wedges pressed into a wet lump of clay, in the days when a superb piece of mental engineering gave us the art of counting. For we count, after all, by giving different number-names and symbols to different sized heaps of things: one, two, three …”
“Whoever it was, in the latter days of Babylon, that first gave to airy nothing a local habitation and a name, has left none himself. Perhaps that double wedge fittingly commemorates his place in history.”
Robert Kaplan, The Nothing That Is: A Natural History of Zero

Welcome back! We are continuing our journey towards finding a worthy zero.

In part 1, we’ve uncovered a numerical system developed by the Sumerians and improved by Babylonians around 3-6000 BCE containing something resembling a concept of 1. However, that system was lacking a crucial element: the element of 0 in a numerical and positioning sense.

A More Familiar Representation for 0

Greeks under Alexander the Great (331 BCE) took us one step closer to the 0 we know today, if only in notation. They carried over a zero with the rest of the booty after invading what remained of the Babylonian Empire. Following that, some astronomical papyri began using ‘O’ to denote “nothing.”

In Almagest (150 AD), Ptolemy used Ō to represent “nothing,” with some evidence of positional intent. Still, his use and the need to decorate the symbol to distinguish it from other numbers, denotes that this symbol was still treated as punctuation rather than a digit or a number. Sadly, the symbol did not surface in ancient Greece ouside of writings on astronomy, and the further development of a concept of zero stopped in its tracks.

Robert Kaplan, in his book The Nothing That Is: A Natural History of Zero, includes an interesting quote and additional insight into the Greek’s lack of zero:

The courtiers who surround kings are exactly like counters on the lines of a counting board, for, depending on the will of the reckoner, they may be valued either at no more than a mere chalkos, or else a whole talent (Polybius, 2nd century BC)

The author brings to our attention the fact that the quote did not State “valued at nothing” because the counting boards did not contain a column for zero. A chalkos was the lowest known financial value and a talent was of a much larger value. So instead of “no value” or “valued at nothing” Polybius used the lowest known value: a chalkos.

So far, no sign of a true zero being used in ancient Greece, Babylon, Egypt. Not even the mighty Romans had a symbol for or an understanding of zero.

A Worthy Zero

Between the 3rd to the 10th history AD, when developments started to emerge towards the concept we know today, zero’s history becomes blurred, possibly doctored, and heavily contested between Greek and Indian origins. To summarize, it took a lot of physical traveling of the concept to many parts of the world for people to further refine the concept.

I recommend reading the above-mentioned book if you are interested in the subject and want to find more details. It’s very interesting and I do want to develop the subject further in the future, even if the sources are hard to trace and blurry.

Here, we’ll focus on the most “widely believed fact” on the emergence of a true 0. The earliest writing that proves an understanding of zero close to our definition today is Brahmagupta’s Brahmasphuṭasiddhānta (628 AD):

(Extract from Algebra, with Arithmetic and Mensuration from the Sanscrit of Brahmegupta and Bhascala translated by Henry Thomas Colebrooke, 1817)

I believe we’ve found our zero. This is the first documented use of zero as a mathematical concept with functioning as a full-blown number and digit rather than just a placeholder or punctuation.

But as I gaze upon this discovery, still humbled by the amount of understanding present in this 7th-century mathematics book, I find my plan of gradual discovery towards the bit was flawed. We were looking for ones and zeroes, but now I realize that a bit is conceptually closer to a light switch than to ones and zeroes. A bit is something that is either on or off (true or false). I can continue the dig through history, probably having to take a step back towards logicians or multiple steps forward towards George Boole’s time, but I feel that would take more than the allocated number of posts, either way.

I don’t think going down the historic roots benefits the target audience for this series, which is supposed to be people starting out with programming. If there is feedback towards continuing this history-driven approach, let me know and I’ll be pleased to oblige. I will continue that series at some point, but building the Dojo remains a priority.

I’ll switch to a more practical approach starting from my next post.

The History: Finding a 1

January 1, 2021February 4, 2021 alex1 Comment

“If I have seen further it is by standing on the shoulders of Giants.”
Isaac Newton, 1675

“The journey of however many miles starts with a single cliche”
Anonymous

We’re starting our journey into the “art of code” with a brief history of computing up to the first written evidence of humans encoding something resembling a bit, with or without the context of a full-blown computer. A bit is the smallest unit of data in a computer, which can only have two values: 0 or 1 (false or true). The plan is to scan documented history and get to that point in time in at most three posts including this one.

Early Symbols

The word code carries a few meanings depending on the context. One of the meanings has to do with transmitting a message in a synthesized or transformed form (sometimes called an encoding of the message), often in the interest of keeping the message secret. Consider Morse Code and its assignment of dots and lines instead of letters. Someone who knows Morse Code can easily encode or decode a message using the code’s substitution table.

By definition, speech is (an) encoding because it servers the purpose of conveying information (words, context, meaning, thought, emotion) through the careful arrangement of sounds. There are some estimates and speculation around the timeline of the appearance of speech. For this story, we’ll only consider being “code” or “encoding” that which can be seen or touched.

Oldest known cave art was made by Neanderthals, not humans - art ...

As early as 50-60 thousand years ago, early humans (and Neanderthals?) have created cave paintings depicting recognizable stylized animals, notable events, and places. I imagine that these creations had the purpose of mementos, capturing and communicating emotion, and perhaps community building. I speculate that this early form of mimesis, using the world as its canvas, contains the earliest known form of encoding. Cave building has to have been an essential step towards the birth of letters and digits as we know them today.

I find it mesmerizing and comforting that so many years ago, our species (I wish “specieses” were a word) had this need for communication and connection. I do imagine other forms of art and code have manifested without resisting the test of time as long as cave paintings did. As it could probably be the subject of a whole book, I am not mentioning astrology, star gazing, and calendar making as forms of “coding.” Of course, the best method to do that is to mention it, as observed here.\

Should we discard the different numbers of objects present in cave paintings as an understanding of numbers? It feels like there’s some inherent intuition on numbers in all species. We’re looking for that proven intuition that goes beyond animal instinct, beyond fight or flight, beyond purely imitating the world around. We’re looking for the first use of numbers as an abstract concept, some evidence of giving them a name or a description.

The first 1

At around 3-6000 BCE, there’s evidence of Sumerians (overly simplifying the involvement and advances of other civilizations in this story) having invented a sexagesimal (base 60) numerical system, probably a necessity in managing their administrative needs. So, to anyone wondering, the decimal (base 10) system was not always “the norm”:

This table is remarkable. Remember, the table contains what we would call digits today. In other words, the first two-digit number would occur for them while counting when they reached 60. These digits followed a pattern that made digits “look like” their respective “real-life” “numbers.” In other words, not only their numbers but also their digits followed the same rules and principles as our numbers do. They seemed to have symbols for 1 and 10 together with a rule for composing them into their symbols for “digits.”

You might also observe that there is not something resembling 0 in this table, which probably made for much confusion. Imagine not being able to tell the difference between 5 and 50; 101 and 11; 1 and 10000; and many others.

The Babylonians later on tried to work around this shortcoming of this system by and even later a slanted double wedge symbol for “nothing.” (circa 3rd-6th century BCE ) They understood “nothing,” but they did not see “nothing” as a number; instead, they saw it as the absence of something. Another quirk in this workaround was that they only used the “nothing” symbols in the middle of the number. Thus, there was no way other than the context for them to differentiate between 1 and 60 and 3600; and so on.

To keep things brief, I’m skipping detailed depictions of their use of a single-hand 12-counting system, ties to base 60, and why base 60 was so thriving for them in general.

Let’s get back to numbers. Imagine you see a number like 637 (magic, right?); you immediately know the scale of it and, well, that it’s 637. That’s because your brain’s wiring is for base 10. You don’t have to consciously calculate (in any given order): 7 ones plus 3 tens plus 6 hundreds.

10²	10¹	10⁰
6	3	7

Now let’s do something similar in sexagesimal. I’ll use numbers instead of the symbols in the table above since I found no easy way to use them in this text at this time. Similarly to our example above, in the Sumerian system, a number like 357 would mean to them: 7 ones plus 3 sixties plus 6 thirtisixhundreds.

60²	60¹	60⁰
6	3	7

Their brains wiring was for (their) base-60, maybe it was just as natural to them as it is to us to interpret decimal numbers? Things that keep me up at night ?

There’s plenty of material out there about Sumerian, Babylonian, and Egyptian math. Fire up google and look it up if you want to. For now, I’ll mention one more thing very relevant to the birth of computing but not necessarily to our story: the Sumerian abacus (est. 2700-2300 BCE).

Filteq - Sumerian Abacus - Around 2500 BC Sumerian Abacus ...

An abacus is a “manual” calculator, with columns or rows of beads typically strung on wires representing the digits of the number: ones, tens, hundreds, thousands, etc) – or in the case of Sumerians: ones, sixties, thirtysixhundreds, etc). The operator of these early computers would calculate subtractions and additions by sliding the desired number of beads on each of the corresponding digits rows or columns. To my knowledge, the abacus is the earliest form of deliberate computing: devising a set of symbols and rules and then designing tools to operate on that set of symbols and rules.

This was a very roundabout way to say: the earliest form of “1” appeared in written form as part of a mathematical system somewhere around 5-8 thousands of years ago.

In our next post, we will continue our search for the first clear signs of “0” as a number or digit.