07-16-2017, 09:25 AM
(This post was last modified: 08-10-2017, 03:20 AM by belevid.
Edit Reason: Error caught by Zijkhal in Section 4
)
Welcome to the first part of a math tutorial series I'm putting together. These tutorials will guide you through not only the knowledge needed for circuitry on this server, but can also serve as a guideline in any mathematical pursuit. However, the lessons will eventually be oriented towards application to redstone. This tutorial assumes a basic knowledge of binary but will visit binary as its own part later on. Please note that each part will be continuously updated as people make suggestions and I add more topics to each chapter. Also, in order to keep the tutorial short and simple, proofs are omitted (unless necessary). Consequently, it is up to the reader to convince themselves of the statements or to take them at face value.
In this first part, we will discuss modular arithmetic. The list of topics for the entire series is as follows:
(Subject to change as I add topics)
1. Modular Arithmetic
1.1 Inspiring Question
1.2 The %(Modulo) Operator
1.3 Basic Operations
1.4. Additional Topics
1.4.1 Multiplicative Groups
1.4.2 Divisibility with Modular Arithmetic
2. Boolean Algebra
2.1. Inspiring Question
2.2 Truth Tables
2.3. Basic Operations
2.3.1 NOT, AND, OR, etc.
2.3.2 Algebraic Logic
2.3.3 De Morgan's Laws
2.4 Writing Formal Statements in Boolean Logic
2.5 Logic Gates and Application to Binary
2.6. Additional Topics
2.6.1 The 3-SAT Problem
3. Number Bases
3.1 Inspiring Question
3.2 Revisiting Decimal
3.3 General Number Bases
3.4 Basic Operations
3.5. Binary
3.5.1 Binary as a Number System
3.5.2 Binary in Circuits
3.6. Hexadecimal
3.6.1 Hexadecimal as a Number System
3.6.2 Hexadecimal in Circuits
3.7. Additional Topics
3.7.1 Non-Constant Number Bases
4. Computation Theory
4.1 Computation and Universality
4.2 Models of Computation
4.3. Cellular Automata
4.3.1 Elementary Cellular Automata
4.3.2 Game of Life
4.3.3 Langton's Ant
4.4. Complexity
4.4.1 Big "O" Notation
4.4.2 Algorithmic Complexity
4.5. The Turing Machine
4.5.1 The Tape and Head
4.5.2 Symbols
4.5.3 States
4.5.4 Time-Space Trade-off
4.6. Additional Topics
4.6.1 Universal Turing Machine
4.6.2 Metasimulation
Chapter 1: Modular Arithmetic
Section 1: Inspiring Question
Modular arithmetic is, in the loosest sense, a way of doing normal arithmetic but with a limited set of numbers. This is useful to us as redstoners because, regardless of how much space we use, we can only ever represent a finite set of numbers. In order to perform the calculations that we want, we must have a way of modifying traditional algebra to suit our limitations while still preserving its familiar and convenient structures. To pique the interest of the reader, and in the interest of demonstrating the capabilities of modular arithmetic I pose the following question:
Notice that division is not mentioned. This is because it does not have very nice properties with the modulus (due, in part, to the fact that it is so closely related to division). Let's put these properties to use:
In this first part, we will discuss modular arithmetic. The list of topics for the entire series is as follows:
(Subject to change as I add topics)
1. Modular Arithmetic
1.1 Inspiring Question
1.2 The %(Modulo) Operator
1.3 Basic Operations
1.4. Additional Topics
1.4.1 Multiplicative Groups
1.4.2 Divisibility with Modular Arithmetic
2. Boolean Algebra
2.1. Inspiring Question
2.2 Truth Tables
2.3. Basic Operations
2.3.1 NOT, AND, OR, etc.
2.3.2 Algebraic Logic
2.3.3 De Morgan's Laws
2.4 Writing Formal Statements in Boolean Logic
2.5 Logic Gates and Application to Binary
2.6. Additional Topics
2.6.1 The 3-SAT Problem
3. Number Bases
3.1 Inspiring Question
3.2 Revisiting Decimal
3.3 General Number Bases
3.4 Basic Operations
3.5. Binary
3.5.1 Binary as a Number System
3.5.2 Binary in Circuits
3.6. Hexadecimal
3.6.1 Hexadecimal as a Number System
3.6.2 Hexadecimal in Circuits
3.7. Additional Topics
3.7.1 Non-Constant Number Bases
4. Computation Theory
4.1 Computation and Universality
4.2 Models of Computation
4.3. Cellular Automata
4.3.1 Elementary Cellular Automata
4.3.2 Game of Life
4.3.3 Langton's Ant
4.4. Complexity
4.4.1 Big "O" Notation
4.4.2 Algorithmic Complexity
4.5. The Turing Machine
4.5.1 The Tape and Head
4.5.2 Symbols
4.5.3 States
4.5.4 Time-Space Trade-off
4.6. Additional Topics
4.6.1 Universal Turing Machine
4.6.2 Metasimulation
Chapter 1: Modular Arithmetic
Section 1: Inspiring Question
Modular arithmetic is, in the loosest sense, a way of doing normal arithmetic but with a limited set of numbers. This is useful to us as redstoners because, regardless of how much space we use, we can only ever represent a finite set of numbers. In order to perform the calculations that we want, we must have a way of modifying traditional algebra to suit our limitations while still preserving its familiar and convenient structures. To pique the interest of the reader, and in the interest of demonstrating the capabilities of modular arithmetic I pose the following question:
(1) What is the last digit of 17^1139?
Even the most avid calculator will shudder at such a calculation! With the power of modular arithmetic, however, we can find the answer without calculations exceeding the calculator's limit. By the end of this chapter, not only will you have the knowledge to perform such a calculation, but I implore that you do so on your own.
Section 2: The %(Modulo) Operator
The % operator is known to any programmer or mathematician with adequate experience as the "modulo" operator. It works much like + or * in that it takes two numbers and returns a single number. Anyone who has done long division will be familiar with the concept of a remainder, that is, the quantity that is left after you've done the repeated subtraction. The modulo is exactly that quantity. For example, 35%4 = 3 because when you divide 35 by 4, the remainder is 3. The modulo operator has the following properties:
- For the operation a%b, a is called the dividend, b is called the divisor and the result is called the modulus.
- 0 <= a%b < b
- If a%b = n, then a-n is divisible by b
(2) a+nb mod b = a mod b
where n is any integer. If we restrict a so that 0 <= a < b, we obtain an easy way to calculate the modulus. For example, 43 mod 7 = 1 + 6(7) mod 7 = 1 mod 7 = 1. It's important to note that this property also allows us to define the modulo operator for negative dividends (though not for negative divisors). -3 mod 10 = 7 + (-1)(10) mod 10 = 7 mod 10 = 7. This fact will become very important when we discuss negative numbers in binary.
Section 3: Basic Operations
It's one thing to calculate the modulus, but most times we have an expression inside of the dividend such as 62+12 mod 5 or 43*2 mod 7. It would be useful if we had a way of simplifying dividend in order to calculate the modulus easier. To do that, we have the following operations:
- a+/-b mod n = ((a mod n)+/-(b mod n)) mod n
- a*b mod n = ((a mod n)*(b mod n)) mod n
- a^b mod n = ((a mod n)^b) mod n
Notice that division is not mentioned. This is because it does not have very nice properties with the modulus (due, in part, to the fact that it is so closely related to division). Let's put these properties to use:
- 53+27 mod 7 = (53 mod 7) + (27 mod 7) mod 7 = (4+6(7) mod 7)+(6+3(7) mod 7) mod 7 = 4+6 mod 7 = 3+1(7) mod 7 = 3
- 45*16 mod 9 = (45 mod 9)*(16 mod 9) mod 9 = (0+5(9) mod 9)*(5+1(9) mod 9) mod 9 = 0*5 mod 9 = 0
- 76^3 mod 35 = (6 + 2(35) mod 35)^3 mod 35 = 6^3 mod 35 = 216 mod 35 = 6 + 6(35) mod 35 = 6
Section 4: Additional Topics
Topic 1: Multiplicative Groups
Of the operations discussed in the previous section, the last two should be particularly surprising in that they took a potentially laborious calculation and turned it into simple mental math. It's clear that the modulo operator has the ability to simplify multiplication (which makes sense considering it's related to division) to a great degree. In studying the last property, a pattern emerges quickly. Let's look at the following operations. 3^0 mod 7 = 1, 3^1 mod 7 = 3, 3^2 mod 7 = 2, 3^3 mod 7 = 6, 3^4 mod 7 = 4, 3^5 mod 7 = 5, 3^6 = 1. We arrive back where we began and, according to the third property, this pattern repeats infinitely. Similar to the pattern we see from addition in equation (2), multiplication also has a similar equation.
(3) a^φ(n) mod n = 1
only if a and n don't share any factors. φ is called the Euler totient function. I won't be covering it in this tutorial but I urge the reader to read the Wikipedia article on it. This number φ(n) is like the "looping point" but for multiplication because clearly a^0 mod n = 1.
At this point, you should have the tools you need to tackle the problem I posed at the beginning of the chapter (if you're clever). In the next topic, we will solve the problem that I posed. At this point I'd advise the reader to try and solve it themselves and then return to read the next topic and see how their solution matches up.
Topic 2: Divisibility with Modular Arithmetic
To introduce the topic, I would like to give the reader a nice trick I've used many times in my life. If you want to tell if a number is divisible by 3, add up the digits and if the result is divisible by 3, then so is the original number (the same property applies to 9 but 3 is the easiest to explain and we will discuss how to prove it for the other numbers). Once you have sufficiently convinced yourself this is true, the question becomes "What causes this strange trick?". Luckily, modular arithmetic shows whats really going on, but to prove it will require everything we've talked about up to this point.
Using the third property discussed in Section 2, we know that if a mod b = 0, then a is divisible by b. Thus, if a mod 3 = 0, then a is divisible by 3. If a has the digits a0, a1, a2, ... where a0 is the rightmost digit (not a*0), then a = a0 + 10*a1 + 100*a2... 10^n+an. Now the properties discussed in Chapter 3 come into play. Our expression is currently a0 + 10*a1 + 100*a2... 10^n+an mod 3. If we notice, however, that 10^n mod 3 = (10 mod 3)^n mod 3 = (1+3(3) mod 3)^n mod 3 = 1^n mod 3 = 1, then our expression becomes a0 + a1 + a2... an mod 3. And thus we arrive at the result. If the sum of the digits is divisible mod 3, then so is the original number. Note that 3 could be any number we want and we can create a way to test any number's divisibility based on the sum of its digits.
Now, we are ready to tackle question (1). Let's look at the expression 17^1139. How do we tell what the last digit is? Well if any number can be expanded as a0 + 10*a1 + 100*a2... 10^n+an. Then if we take the expression modulo 10, we're just left with a0, the rightmost digit. Thus our question becomes "what is 17^1139 mod 10?". Here, we can notice that 17 and 10 don't share any factors, thus we can apply equation (3). If we change the the equation to 17^(3+284(4)) mod 10 = 17^3*17^(4(284)) mod 10 = 17^3*1^284 mod 10 = 17^3 mod 10. At this point we're close to an answer and one could easily give this to a calculator and get an answer. But in the pursuit of applying our knowledge and simplifying things, we can apply property 3 of Section 3 to get (17 mod 10)^3 mod 10 = 7^3 mod 10 = 7*49 mod 10 = 7*(49 mod 10) mod 10 = 7*9 mod 10 = 63 mod 10 = 3. So with some simple equations and mental math, we were able to answer the question fairly easily.
I hope that you enjoyed the first part of this tutorial and learned a lot. I wanted to start this because I've noticed both a lack of resources for new people and a large amount of misinformation filling the server. As a math major, I felt it was important to set some things straight and create such a resource. If you have any recommendations (anywhere from future subjects to additions to the current parts) please let me know in the replies. Thanks for reading!
