WEBVTT 00:00:00.000 --> 00:00:03.459 If I ask you to divide negative 5 by 2, what 00:00:03.459 --> 00:00:06.339 is the remainder? Just think about that for a 00:00:06.339 --> 00:00:08.990 second. Negative five divided by two. You'd probably 00:00:08.990 --> 00:00:12.009 think there's, you know, one universally correct, 00:00:12.369 --> 00:00:15.150 perfectly logical math answer to that question. 00:00:15.210 --> 00:00:18.230 Right. Exactly. But if you take that exact same 00:00:18.230 --> 00:00:21.589 math problem and hand it to a system built by 00:00:21.589 --> 00:00:24.609 Apple and then hand it to a server running Microsoft 00:00:24.609 --> 00:00:27.329 architecture and then, I don't know, ask a pure 00:00:27.329 --> 00:00:30.149 mathematician, you are going to get completely 00:00:30.149 --> 00:00:33.609 different answers. It really is wild. It completely 00:00:33.609 --> 00:00:36.469 shatters this illusion we all have that math 00:00:36.469 --> 00:00:39.549 inside a computer is this pristine absolute truth. 00:00:39.789 --> 00:00:41.549 It totally does. And that's exactly what we're 00:00:41.549 --> 00:00:43.549 getting into today. Welcome to the deep dive. 00:00:43.890 --> 00:00:46.350 We are looking at an operation that you probably 00:00:46.350 --> 00:00:48.409 learned in the fourth grade, assumed you fully 00:00:48.409 --> 00:00:50.229 understood, and just haven't thought about since. 00:00:50.350 --> 00:00:51.829 No, we're talking about the modulo operation. 00:00:51.869 --> 00:00:56.109 Oh. Or often just called mod. Right, mod. And 00:00:56.109 --> 00:00:58.390 it is secretly running the digital world you 00:00:58.390 --> 00:01:01.420 interact with every single day. Our mission today 00:01:01.420 --> 00:01:04.340 is to explore how a concept as basic as finding 00:01:04.340 --> 00:01:06.819 the remainder of a division problem actually 00:01:06.819 --> 00:01:10.120 breaks down in spectacular ways when it meets 00:01:10.120 --> 00:01:13.040 negative numbers. And I mean, it isn't just an 00:01:13.040 --> 00:01:15.519 academic work either. This breakdown has created 00:01:15.519 --> 00:01:18.819 massive philosophical debates, split programming 00:01:18.819 --> 00:01:22.840 languages into warring factions and caused incredibly 00:01:22.840 --> 00:01:26.159 subtle system crashing bugs in the software we 00:01:26.159 --> 00:01:28.620 all rely on. Yeah, the bugs are the crazy part. 00:01:28.659 --> 00:01:31.599 Yeah. So whether you are a seasoned programmer 00:01:31.599 --> 00:01:34.480 who deals with this daily or just someone listening 00:01:34.480 --> 00:01:36.040 on a smartphone right now who wants to know how 00:01:36.040 --> 00:01:38.599 the invisible digital gears actually turn, this 00:01:38.599 --> 00:01:40.819 is going to completely change how you view basic. 00:01:40.719 --> 00:01:43.640 division. Absolutely. So let's start at the absolute 00:01:43.640 --> 00:01:45.680 baseline, because we really have to build the 00:01:45.680 --> 00:01:48.379 foundation before we can break it. What exactly 00:01:48.379 --> 00:01:51.180 is modulo doing when we aren't dealing with negative 00:01:51.180 --> 00:01:54.500 numbers? Okay, so at its core, modulo is just 00:01:54.500 --> 00:01:56.900 an operation that asks for the remainder of a 00:01:56.900 --> 00:01:58.579 division problem. You have a dividend, that's 00:01:58.579 --> 00:02:00.480 the number you're dividing, and a divisor, which 00:02:00.480 --> 00:02:02.799 we call the modulus. So if you run the expression 00:02:02.799 --> 00:02:06.549 5 modulo 2, it evaluates to 1. Right, because 00:02:06.549 --> 00:02:09.069 two goes into five twice, which gets you to four, 00:02:09.169 --> 00:02:11.270 and then you have one left over. Exactly. Or, 00:02:11.270 --> 00:02:13.569 you know, nine modulo three, that evaluates to 00:02:13.569 --> 00:02:16.389 zero. Three goes into nine exactly three times. 00:02:16.729 --> 00:02:19.909 There's nothing left over. Makes sense. So mathematically, 00:02:20.069 --> 00:02:22.610 if you're doing a modulo operation with a positive 00:02:22.610 --> 00:02:26.030 divisor, let's just call it n, the result is 00:02:26.030 --> 00:02:28.150 always going to be locked in a specific range. 00:02:28.210 --> 00:02:30.819 It'll always be zero up to n minus one. Okay, 00:02:30.819 --> 00:02:34.139 so if I'm doing modulo 5, the only possible answers 00:02:34.139 --> 00:02:37.900 in the universe are 0, 1, 2, 3, or 4. Right. 00:02:37.939 --> 00:02:40.259 I mean, I can never have a remainder of 5, because 00:02:40.259 --> 00:02:43.139 if I had 5 left over, my divisor of 5 would just 00:02:43.139 --> 00:02:45.960 go into it one more time. Precisely. And in computing, 00:02:46.280 --> 00:02:48.900 this entire operation is held together by one 00:02:48.900 --> 00:02:52.460 strict, non -negotiable math equation. The dividend 00:02:52.460 --> 00:02:55.259 equals the divisor times the quotient, plus the 00:02:55.259 --> 00:02:56.979 remainder. Okay, let's make that concrete. The 00:02:56.979 --> 00:02:59.000 pizza analogy always works best for me. Oh yeah, 00:02:59.039 --> 00:03:02.889 go for it. If I have five leftover slices of 00:03:02.889 --> 00:03:05.590 pizza, that's my dividend. I have two friends, 00:03:05.610 --> 00:03:08.310 that's my divisor. How many slices do they each 00:03:08.310 --> 00:03:09.930 get? That's the question. They each get two. 00:03:10.069 --> 00:03:13.009 Right. So two times two is four. Exactly. Plus 00:03:13.009 --> 00:03:15.289 the remainder. I have one slice left in the box. 00:03:15.509 --> 00:03:18.090 So five equals two times two plus one. That is 00:03:18.090 --> 00:03:20.969 the perfect clean elementary school version. 00:03:20.990 --> 00:03:24.289 Yeah. But here is where the math hits a brick 00:03:24.289 --> 00:03:27.150 wall. What happens when exactly one of those 00:03:27.150 --> 00:03:29.180 numbers is negative? This is where I started 00:03:29.180 --> 00:03:31.659 losing my mind reading the source material. How 00:03:31.659 --> 00:03:33.960 do you calculate a remainder when someone owes 00:03:33.960 --> 00:03:36.460 you negative pizza slices? I mean, what does 00:03:36.460 --> 00:03:38.639 that even mean? Well, let's do the math out loud 00:03:38.639 --> 00:03:41.560 using that exact formula. The formula is, again, 00:03:41.819 --> 00:03:44.139 dividend equals divisor times quotient plus remainder. 00:03:44.419 --> 00:03:46.860 OK, I'm with you. Let's make the dividend negative 00:03:46.860 --> 00:03:49.759 5 and the divisor positive 2. Negative 5 divided 00:03:49.759 --> 00:03:52.180 by 2. We need to find the quotient and the remainder. 00:03:52.439 --> 00:03:56.379 Okay, so negative 5 equals 2 times something 00:03:56.379 --> 00:03:59.500 plus a remainder. Right. And here is the trap. 00:03:59.960 --> 00:04:02.759 Because we are dealing with integers, you know, 00:04:02.979 --> 00:04:05.520 whole numbers, there are actually two completely 00:04:05.520 --> 00:04:08.360 valid ways to solve this equation. Wait, two 00:04:08.360 --> 00:04:11.909 valid ways? Yeah. Path A... You could decide 00:04:11.909 --> 00:04:14.629 the quotient is negative 2. 2 times negative 00:04:14.629 --> 00:04:17.149 2 is negative 4. Okay. And to get from negative 00:04:17.149 --> 00:04:20.209 4 down to negative 5, your remainder has to be 00:04:20.209 --> 00:04:23.250 negative 1. Let me track that. So negative 5 00:04:23.250 --> 00:04:25.790 equals 2 times negative 2, which is negative 00:04:25.790 --> 00:04:29.089 4 minus 1. Yeah, the math works perfectly. The 00:04:29.089 --> 00:04:31.350 remainder is negative 1. But look at path B. 00:04:32.050 --> 00:04:33.949 What if you decide the quotient is negative 3? 00:04:34.139 --> 00:04:36.680 Oh, interesting. Right, because 2 times negative 00:04:36.680 --> 00:04:39.779 3 is negative 6. And to get from negative 6 up 00:04:39.779 --> 00:04:42.560 to negative 5, your remainder has to be positive 00:04:42.560 --> 00:04:45.839 1. Wait, let me think. Negative 5 equals 2 times 00:04:45.839 --> 00:04:49.180 negative 3, which is negative 6 plus 1. Wow, 00:04:49.319 --> 00:04:51.699 the math works perfectly there too. So the remainder 00:04:51.699 --> 00:04:54.420 is positive 1. You literally have two completely 00:04:54.420 --> 00:04:57.139 correct mathematical answers for a basic division 00:04:57.139 --> 00:05:00.310 problem. Yes. The choice of remainder entirely 00:05:00.310 --> 00:05:02.990 depends on which of two consecutive integers 00:05:02.990 --> 00:05:05.189 you pick for the quotient. Do you pick negative 00:05:05.189 --> 00:05:09.670 2 or negative 3? That is wild! And in pure number 00:05:09.670 --> 00:05:12.410 theory, mathematicians saw this ambiguity and 00:05:12.410 --> 00:05:15.649 just made a rule. They agreed to always choose 00:05:15.649 --> 00:05:17.990 the positive remainder. They wanted remainders 00:05:17.990 --> 00:05:21.110 to behave like distances, always zero or greater. 00:05:21.310 --> 00:05:23.350 But I'm guessing computer scientists didn't play 00:05:23.350 --> 00:05:26.110 along with the mathematicians. Not at all. Because 00:05:26.110 --> 00:05:27.990 hardware engineers and software developers have 00:05:27.990 --> 00:05:31.730 to actually build systems that store and process 00:05:31.730 --> 00:05:35.069 these numbers efficiently. They didn't just disagree 00:05:35.069 --> 00:05:37.230 with the mathematicians, they disagreed with 00:05:37.230 --> 00:05:39.769 each other. Oh, of course they did. Right. This 00:05:39.769 --> 00:05:42.810 ambiguity forced the invention of different computational 00:05:42.810 --> 00:05:45.230 rules, which basically split the programming 00:05:45.230 --> 00:05:48.189 world into distinct tribes. The tribal war is 00:05:48.189 --> 00:05:52.019 of modulo. I love this part. So break down these 00:05:52.019 --> 00:05:54.500 factions for me. If I'm writing code, whose rules 00:05:54.500 --> 00:05:56.660 am I actually following? Well, the first major 00:05:56.660 --> 00:05:59.259 tribe uses what is called truncated division. 00:05:59.720 --> 00:06:02.199 This was heavily favored by early hardware architects. 00:06:03.000 --> 00:06:05.040 In truncated division, when you calculate the 00:06:05.040 --> 00:06:07.319 quotient, you always round towards zero. Round 00:06:07.319 --> 00:06:09.959 towards zero. OK. Think of a number line. If 00:06:09.959 --> 00:06:14.279 the exact decimal answer is negative 2 .5, truncated 00:06:14.279 --> 00:06:16.980 division just chops off the decimal and rounds 00:06:16.980 --> 00:06:19.439 towards zero, giving you a quotient of negative 00:06:19.439 --> 00:06:22.000 2. Right, and as we just proved with Path A earlier, 00:06:22.220 --> 00:06:24.259 if your quotient is negative 2, your remainder 00:06:24.259 --> 00:06:27.180 has to be negative 1. Exactly. Because of how 00:06:27.180 --> 00:06:29.459 rounding towards zero works out mathematically, 00:06:30.040 --> 00:06:32.579 the remainder in truncated division will always 00:06:32.579 --> 00:06:35.199 take the exact same sign as the dividend. OK, 00:06:35.240 --> 00:06:37.399 so if the number you are dividing is negative, 00:06:37.699 --> 00:06:39.819 your remainder will be negative. You got it. 00:06:40.019 --> 00:06:42.600 And this tribe includes massive foundational 00:06:42.600 --> 00:06:47.220 languages like C, C++An, and Java. OK, so that's 00:06:47.220 --> 00:06:50.220 tribe one, the hardware purists, I guess. What's 00:06:50.220 --> 00:06:53.040 the second tribe? The second major tribe uses 00:06:53.040 --> 00:06:55.610 floor division. This is championed by Donald 00:06:55.610 --> 00:06:57.990 Knuth, who is one of the legendary figures in 00:06:57.990 --> 00:06:59.769 computer science. Yeah, definitely. Floor division 00:06:59.769 --> 00:07:01.750 doesn't round towards zero. It always rounds 00:07:01.750 --> 00:07:04.230 down toward negative infinity. So on a number 00:07:04.230 --> 00:07:07.230 line, negative 2 .5 rounds down to negative 3. 00:07:07.470 --> 00:07:10.490 Which takes us to path B. If the quotient is 00:07:10.490 --> 00:07:13.069 negative 3, the remainder has to be positive 00:07:13.069 --> 00:07:16.649 1. Right. In floor division, the remainder always 00:07:16.649 --> 00:07:19.790 takes the same sign as the divisor. If you are 00:07:19.790 --> 00:07:22.649 dividing by a positive two, your remainder will 00:07:22.649 --> 00:07:24.970 always be positive, no matter what number you 00:07:24.970 --> 00:07:26.709 started with. That makes a lot of sense. Yeah. 00:07:26.970 --> 00:07:29.029 And this approach was adopted by languages that 00:07:29.029 --> 00:07:31.430 were designed to be more mathematically intuitive, 00:07:31.550 --> 00:07:34.170 like Python and Ruby. OK. And just to be thorough, 00:07:34.350 --> 00:07:37.290 is there a third tribe? There is. Euclidean division, 00:07:37.689 --> 00:07:39.829 promoted by computer scientist Raymond T. Boot. 00:07:40.529 --> 00:07:43.209 He looked at both truncated and floored division 00:07:43.209 --> 00:07:47.290 and argued they were both flawed. Why? Because 00:07:47.290 --> 00:07:50.009 they allowed rematers to flip signs wildly, depending 00:07:50.009 --> 00:07:52.750 on the inputs. He argued that systems should 00:07:52.750 --> 00:07:54.889 force the remater to always be non -negative, 00:07:55.269 --> 00:07:58.860 zero or greater, period. just like the pure mathematicians 00:07:58.860 --> 00:08:01.920 wanted. Okay, so stepping back, C++ is doing 00:08:01.920 --> 00:08:04.720 truncated division. Python is doing floor division. 00:08:05.100 --> 00:08:07.439 This means if I have a massive tech stack, say 00:08:07.439 --> 00:08:10.420 I've got a backend server written in C++ A, and 00:08:10.420 --> 00:08:12.959 it's passing data to a machine learning script 00:08:12.959 --> 00:08:15.620 written in Python, they could process the exact 00:08:15.620 --> 00:08:18.180 same negative number with the exact same modulo 00:08:18.180 --> 00:08:20.620 operation and spit out two totally different 00:08:20.620 --> 00:08:23.860 results. Yes, and they will do it silently. The 00:08:23.860 --> 00:08:26.240 computer won't throw an error. It just assumes 00:08:26.240 --> 00:08:29.040 you, the programmer, know which tribe you are 00:08:29.040 --> 00:08:32.000 operating in. That is terrifying. How does the 00:08:32.000 --> 00:08:34.559 digital world even function if the foundational 00:08:34.559 --> 00:08:37.519 languages can't agree on what a remainder is? 00:08:37.860 --> 00:08:40.000 It feels like we build modern civilization on 00:08:40.000 --> 00:08:43.139 a fault line. It really does. And it leads to 00:08:43.139 --> 00:08:47.940 catastrophic, yet incredibly subtle, bugs. Let's 00:08:47.940 --> 00:08:50.059 look at the most famous pitfall from the source. 00:08:50.399 --> 00:08:52.279 It's something pretty much every programmer encounters, 00:08:52.519 --> 00:08:54.379 usually the hard way. I want to hear this, because 00:08:54.379 --> 00:08:56.799 up until now, this has felt a bit like an esoteric 00:08:56.799 --> 00:08:59.480 math debate. How does this actually break real 00:08:59.480 --> 00:09:01.919 -world code? Okay, imagine you were writing code 00:09:01.919 --> 00:09:04.460 for a bank or, I don't know, a video game, and 00:09:04.460 --> 00:09:06.740 you need to test if a number is odd or even. 00:09:06.879 --> 00:09:09.000 Okay, that is literally computer science 101. 00:09:09.100 --> 00:09:11.740 It's the first logic test anyone writes. You 00:09:11.740 --> 00:09:13.820 take your variable, let's call it n, and you 00:09:13.820 --> 00:09:16.600 do n modulo 2. If the answer is 1, the number 00:09:16.600 --> 00:09:19.259 is odd, because any odd number divided by 2 leaves 00:09:19.259 --> 00:09:21.659 a remainder of 1. It seems bulletproof, right? 00:09:22.570 --> 00:09:26.269 2 is 1. 7 mod 2 is 1. So you write the code, 00:09:26.409 --> 00:09:30.009 if n mod 2 equals 1, then trigger the logic for 00:09:30.009 --> 00:09:32.529 an odd number. But wait, we just established 00:09:32.529 --> 00:09:34.990 that if n is negative 5, and I'm writing this 00:09:34.990 --> 00:09:39.090 in C++ or Java, those languages belong to the 00:09:39.090 --> 00:09:41.830 truncated division tribe. The remainder takes 00:09:41.830 --> 00:09:43.970 the sign of the dividend. Exactly. Your dividend 00:09:43.970 --> 00:09:46.909 is negative 5. So negative 5 modulo 2 doesn't 00:09:46.909 --> 00:09:49.870 return 1. It returns negative 1. And what does 00:09:49.870 --> 00:09:52.110 your code say? Your code specifically checks 00:09:52.110 --> 00:09:54.629 if the result is exactly equal to positive 1. 00:09:54.830 --> 00:09:57.769 Oh, wow. So nmod 2 equals 1 evaluates to false. 00:09:58.070 --> 00:10:00.809 Yes. The system looks at negative 5, sees the 00:10:00.809 --> 00:10:02.970 remainder is negative 1, and incorrectly decides 00:10:02.970 --> 00:10:05.720 that negative 5 is not an odd number. That is 00:10:05.720 --> 00:10:08.240 a massive logic failure. Think about a financial 00:10:08.240 --> 00:10:11.039 algorithm flagging every odd -numbered transaction 00:10:11.039 --> 00:10:13.679 for audit, but it silently skips all the refunds 00:10:13.679 --> 00:10:16.159 or debts because they are negative numbers. Exactly. 00:10:16.379 --> 00:10:18.899 The logic just silently bypasses the odd numbers. 00:10:19.559 --> 00:10:21.879 To fix this, programmers have to train themselves 00:10:21.879 --> 00:10:25.139 out of their intuitive math habits. The mathematically 00:10:25.139 --> 00:10:27.860 safe way to check if a number is odd across any 00:10:27.860 --> 00:10:30.559 language is to test if the remainder does not 00:10:30.559 --> 00:10:33.139 equal zero. Because whether the system spits 00:10:33.139 --> 00:10:35.490 out a positive one or an negative one, neither 00:10:35.490 --> 00:10:37.990 of them is zero. Right. And mod two does not 00:10:37.990 --> 00:10:40.309 equal zero. Zero doesn't have a sign. Remainger 00:10:40.309 --> 00:10:42.169 zero means the number is perfectly divisible 00:10:42.169 --> 00:10:45.009 by two. So it completely bypasses the tribal 00:10:45.009 --> 00:10:47.269 wars of negative remaingers. That is brilliant, 00:10:47.269 --> 00:10:49.429 but also incredibly frustrating that we have 00:10:49.429 --> 00:10:52.190 to work around it. Okay, getting the math right 00:10:52.190 --> 00:10:55.029 is obviously a minefield. But in computing, getting 00:10:55.029 --> 00:10:57.850 it right isn't enough. It also has to be blisteringly 00:10:57.850 --> 00:11:01.009 fast. And division, which Modulo relies on, is 00:11:01.009 --> 00:11:04.700 famously slow, right? Oh, very slow. For a computer's 00:11:04.700 --> 00:11:06.960 central processing unit, operations like addition, 00:11:07.159 --> 00:11:09.720 subtraction, or shifting bits around take barely 00:11:09.720 --> 00:11:12.440 any effort, maybe one clock cycle. But division 00:11:12.440 --> 00:11:15.779 is computationally expensive. It requires the 00:11:15.779 --> 00:11:18.360 processor to grind through multiple steps, taking 00:11:18.360 --> 00:11:21.139 20, 30, or even 40 clock cycles to calculate 00:11:21.139 --> 00:11:23.960 a quotient and a remainder. Wow. So if I'm playing 00:11:23.960 --> 00:11:26.299 a video game rendering at 60 frames per second, 00:11:26.440 --> 00:11:28.500 and the physics engine is running millions of 00:11:28.500 --> 00:11:31.100 modulo operations to track bouncing particles 00:11:31.100 --> 00:11:33.450 or screen wraparounds, that division becomes 00:11:33.450 --> 00:11:36.570 a massive bottleneck. The game would stutter. 00:11:37.370 --> 00:11:40.370 How do systems speed this up? Hardware engineers 00:11:40.370 --> 00:11:43.450 and compiler writers devised a brilliant shortcut, 00:11:44.090 --> 00:11:46.029 but it only works for a special case when your 00:11:46.029 --> 00:11:48.970 divisor is a power of two. Things like 2, 4, 00:11:49.110 --> 00:11:52.120 8, 16, 32. Okay, powers of two. When you were 00:11:52.120 --> 00:11:54.840 doing modulo with a power of 2, you can completely 00:11:54.840 --> 00:11:57.080 skip the division and replace it with a lightning 00:11:57.080 --> 00:12:00.139 -fast operation called a bitwise AND. Okay, I 00:12:00.139 --> 00:12:01.559 have an analogy for this, but I need to make 00:12:01.559 --> 00:12:03.759 sure I'm mapping it right. If I asked you to 00:12:03.759 --> 00:12:08.820 divide a massive number, let's say 8 ,432 ,567 00:12:08.820 --> 00:12:11.100 by 10, and tell me the remainder, you wouldn't 00:12:11.100 --> 00:12:13.080 pull out a pencil and do long division. No, I 00:12:13.080 --> 00:12:15.320 would just look the last digit, the 7. Right. 00:12:15.539 --> 00:12:18.580 Because our human number system is base 10, so 00:12:18.580 --> 00:12:21.240 dividing by 10 or 100 or 1000 and finding the 00:12:21.240 --> 00:12:23.100 remainder just means looking at the end of the 00:12:23.100 --> 00:12:25.259 number. The digits themselves already give you 00:12:25.259 --> 00:12:27.240 the answer. Does the computer do the same thing? 00:12:27.500 --> 00:12:29.799 That is exactly what the computer is doing. But 00:12:29.799 --> 00:12:34.100 in base 2, computers think in binary 1s and 0s. 00:12:34.419 --> 00:12:36.720 Every position in a binary number represents 00:12:36.720 --> 00:12:39.240 a power of 2. Oh, I see where this is going. 00:12:39.360 --> 00:12:41.320 So if you ask a computer to calculate modulo 00:12:41.320 --> 00:12:44.230 8, it doesn't need to do long division? 8 is 00:12:44.230 --> 00:12:46.409 a power of 2, the computer just needs to look 00:12:46.409 --> 00:12:48.610 at the last three digits of the binary numbers. 00:12:48.889 --> 00:12:50.470 Because anything beyond the last three digits 00:12:50.470 --> 00:12:53.509 is a multiple of 8. So how does the bitwise NND 00:12:53.509 --> 00:12:56.629 operation actually do that? A bitwise NND literally 00:12:56.629 --> 00:12:59.539 acts like a physical mask. You take your massive 00:12:59.539 --> 00:13:01.980 tinary number and you apply a mask that says 00:13:01.980 --> 00:13:04.759 force all the higher bits to zero and only keep 00:13:04.759 --> 00:13:07.200 the bits at the very end. That's so cool. It 00:13:07.200 --> 00:13:08.879 happens instantaneously at the hardware level. 00:13:09.019 --> 00:13:11.700 No math required, just a clean chop. The formula 00:13:11.700 --> 00:13:14.919 is x modulo 2 to the power of n equals xand2 00:13:14.919 --> 00:13:17.820 to the power of n minus 1. Okay, so if I want 00:13:17.820 --> 00:13:20.519 to do modulo 4, the compiler secretly rerates 00:13:20.519 --> 00:13:24.019 my code to say xand3. It just masks out everything 00:13:24.019 --> 00:13:26.679 except the last two bits. That is so elegant. 00:13:26.879 --> 00:13:31.019 It is a massive performance hack. Modern compilers, 00:13:31.820 --> 00:13:34.000 the software that translates your human readable 00:13:34.000 --> 00:13:36.600 code into raw machine instructions, will actively 00:13:36.600 --> 00:13:39.080 hunt through your code for this. Really? If they 00:13:39.080 --> 00:13:41.240 spot you doing modulo with the power of two, 00:13:41.539 --> 00:13:43.460 they will automatically swap out your slow division 00:13:43.460 --> 00:13:46.779 for this fast bitwise A &D operation. You get 00:13:46.779 --> 00:13:49.019 the speed without having to write weird binary 00:13:49.019 --> 00:13:51.870 logic yourself. But wait. I'm sensing a trap. 00:13:51.990 --> 00:13:53.950 We just spent 10 minutes talking about the chaos 00:13:53.950 --> 00:13:56.649 of negative numbers. How does this bitwise hack 00:13:56.649 --> 00:13:58.649 handle negative numbers? You've hit the exact 00:13:58.649 --> 00:14:01.570 issue. The compiler optimization fails completely 00:14:01.570 --> 00:14:04.470 if you are using signed integers in a language 00:14:04.470 --> 00:14:07.690 that uses truncated division, like C or C++AT. 00:14:08.029 --> 00:14:11.269 Why? What breaks? Think about what a bitwise 00:14:11.269 --> 00:14:13.850 AND operation actually does. It's looking at 00:14:13.850 --> 00:14:16.960 raw bits. ones and zeros. It doesn't understand 00:14:16.960 --> 00:14:20.159 the concept of a negative value. Oh, right. To 00:14:20.159 --> 00:14:22.440 a bitwise operation, the sign of a number is 00:14:22.440 --> 00:14:24.340 just another bit, usually the first bit in the 00:14:24.340 --> 00:14:27.100 sequence. When you apply that mask to chop off 00:14:27.100 --> 00:14:29.100 the higher bits, you are also stripping away 00:14:29.100 --> 00:14:33.559 the sign bit. Oh. Which means a bitwise A &D 00:14:33.559 --> 00:14:36.860 will always, 100 % of the time, spit out a positive 00:14:36.860 --> 00:14:39.799 number. Exactly. But remember the rule of the 00:14:39.799 --> 00:14:41.940 truncated tribe. If the dividend is negative, 00:14:42.139 --> 00:14:45.080 the remainder must be negative. So if the compiler 00:14:45.080 --> 00:14:47.539 tried to be helpful and secretly swapped my slow 00:14:47.539 --> 00:14:51.600 modulo operation for a fast bitwise AND, a negative 00:14:51.600 --> 00:14:54.039 dividend would suddenly start returning a positive 00:14:54.039 --> 00:14:56.600 remainder. It would literally change the mathematical 00:14:56.600 --> 00:14:59.759 output of my program just to save a few CPU cycles. 00:15:00.159 --> 00:15:02.519 Precisely. It would corrupt the data. So to prevent 00:15:02.519 --> 00:15:05.320 this, compilers for languages like C are forced 00:15:05.320 --> 00:15:08.740 to abandon the simple, elegant bitwise AND if 00:15:08.740 --> 00:15:10.620 there's any chance the variable could be negative. 00:15:10.700 --> 00:15:12.779 That is so frustrating. Or they have to inject 00:15:12.779 --> 00:15:15.590 a much more comp - sequence of bitwise ORs and 00:15:15.590 --> 00:15:17.590 NOTs just to manually preserve that negative 00:15:17.590 --> 00:15:20.129 sign which eats into the performance gains. It 00:15:20.129 --> 00:15:22.929 is wild how an arbitrary decision made by hardware 00:15:22.929 --> 00:15:25.269 architects decades ago to round towards zero 00:15:25.269 --> 00:15:28.169 is actively preventing modern compilers from 00:15:28.169 --> 00:15:31.500 optimizing code today. Okay, we have zoomed way, 00:15:31.659 --> 00:15:34.059 way in on the microscopic level of binary bits. 00:15:34.460 --> 00:15:36.799 Let's zoom out. Because understanding modulo 00:15:36.799 --> 00:15:39.340 isn't just about avoiding coding bugs, it is 00:15:39.340 --> 00:15:42.000 actually the foundational math that secures the 00:15:42.000 --> 00:15:44.980 modern internet. Yes. When you elevate modulo 00:15:44.980 --> 00:15:47.740 beyond basic arithmetic, you enter the realm 00:15:47.740 --> 00:15:50.320 of cryptography. The idea here is that modulo 00:15:50.320 --> 00:15:52.720 creates a wraparound effect. Modular arithmetic 00:15:52.720 --> 00:15:55.000 is essentially clock math. Right. That is the 00:15:55.000 --> 00:15:57.200 perfect way to visualize it. Think of a standard 00:15:57.200 --> 00:16:01.159 12 -hour clock. If it is 10 .000 a .m. and I 00:16:01.159 --> 00:16:04.019 add 5 hours, the time doesn't become 15 .00 o 00:16:04.019 --> 00:16:06.259 'clock. Right. It hits 12 and wraps back around 00:16:06.259 --> 00:16:09.059 to 3 .0 p .m. You just did modulo 12 in your 00:16:09.059 --> 00:16:12.940 head. 10 plus 5 is 15. 15 modulo 12 leaves a 00:16:12.940 --> 00:16:15.879 remainder of 3. Modular arithmetic forces numbers 00:16:15.879 --> 00:16:18.500 to wrap around a fixed boundary over and over 00:16:18.500 --> 00:16:20.879 again. So it just keeps spinning? Exactly. No 00:16:20.879 --> 00:16:22.919 matter how infinitely large your starting number 00:16:22.919 --> 00:16:25.460 is, the modular operation instantly snaps it 00:16:25.460 --> 00:16:27.700 back onto the clock face. So how does snapping 00:16:27.700 --> 00:16:30.620 a number onto a clock face secure my credit card 00:16:30.620 --> 00:16:33.059 transactions? It creates a mathematical trapdoor, 00:16:33.360 --> 00:16:35.919 a one -way function. In cryptography, protocols 00:16:35.919 --> 00:16:38.000 like the Diffie -Hellman key exchange computers 00:16:38.000 --> 00:16:41.059 take massive prime numbers and raise them to 00:16:41.059 --> 00:16:44.259 massive powers. We're talking numbers with hundreds 00:16:44.259 --> 00:16:48.120 of digits. Unimaginably huge. Right. Then they 00:16:48.120 --> 00:16:50.820 apply a modulo operation using another massive 00:16:50.820 --> 00:16:53.740 prime number as the modulus. So they are taking 00:16:53.740 --> 00:16:56.159 a galaxy -sized number and wrapping it around 00:16:56.159 --> 00:16:58.759 a galaxy -sized clock face. Yes, and here is 00:16:58.759 --> 00:17:00.840 the trapdoor. If I tell you the final answer, 00:17:01.379 --> 00:17:03.139 let's say I tell you the clock hand is currently 00:17:03.139 --> 00:17:05.839 pointing at three, you have absolutely no way 00:17:05.839 --> 00:17:07.880 of knowing how many times that hand spun around 00:17:07.880 --> 00:17:09.839 the clock to get there. Did it spin around once? 00:17:10.119 --> 00:17:12.799 A billion times. A trillion times. Oh wow. Because 00:17:12.799 --> 00:17:15.279 the quotient is completely discarded? Modulo 00:17:15.279 --> 00:17:17.079 only gives you the remainder? The history of 00:17:17.079 --> 00:17:20.259 how you got there is erased? Exactly. It is mathematically 00:17:20.259 --> 00:17:22.960 very easy for a computer to spin the clock forward 00:17:22.960 --> 00:17:25.180 and find the remainder. But it is practically 00:17:25.180 --> 00:17:27.259 impossible for a hacker to look at the remainder 00:17:27.259 --> 00:17:29.500 and reverse engineer the original mass of numbers. 00:17:30.079 --> 00:17:32.339 The information has been locked behind the modulo 00:17:32.339 --> 00:17:35.470 operation. So the exact same mathematical quirk 00:17:35.470 --> 00:17:37.690 that forces a college freshman to tear their 00:17:37.690 --> 00:17:40.170 hair out over a negative one in a basic parity 00:17:40.170 --> 00:17:43.109 test is the same foundational property that allows 00:17:43.109 --> 00:17:46.730 humanity to securely transmit state secrets across 00:17:46.730 --> 00:17:50.049 a public Wi -Fi network. It is the exact same 00:17:50.049 --> 00:17:52.509 underlying mechanism, the destruction of the 00:17:52.509 --> 00:17:55.049 quotient. That is incredible. Before we wrap, 00:17:55.089 --> 00:17:57.170 there is one last real -world application I want 00:17:57.170 --> 00:18:00.029 to touch on, the concept of modulo with offset. 00:18:00.220 --> 00:18:03.279 because a clock starts at 12 or zero, but not 00:18:03.279 --> 00:18:05.779 everything in life starts at zero. Right. Often 00:18:05.779 --> 00:18:08.140 we need a cyclic pattern, but we need the boundary 00:18:08.140 --> 00:18:10.680 shifted. We need the remainder to lie between 00:18:10.680 --> 00:18:13.940 a specific offset, let's call it D, and D plus 00:18:13.940 --> 00:18:16.619 N minus one. The classic example of this is a 00:18:16.619 --> 00:18:18.519 calendar. Think about the days of the week. We 00:18:18.519 --> 00:18:20.920 operate on a seven -day cycle, module of seven, 00:18:21.279 --> 00:18:23.519 but we don't call Monday day zero and Sunday 00:18:23.519 --> 00:18:26.950 day six. We number them one through seven. Exactly. 00:18:27.210 --> 00:18:29.950 If you are a programmer, writing a date calculation 00:18:29.950 --> 00:18:32.789 script, say, figuring out what day of the week 00:18:32.789 --> 00:18:36.549 a bill is due, 45 days from now, a standard Modulo 00:18:36.549 --> 00:18:39.009 7 operation will occasionally spit out a zero. 00:18:39.190 --> 00:18:42.049 But there is no day zero on your calendar. Your 00:18:42.049 --> 00:18:45.190 program will crash. Exactly. So you apply an 00:18:45.190 --> 00:18:47.990 offset of 1. You adjust the formula, usually 00:18:47.990 --> 00:18:50.549 incorporating the floor function, to shift the 00:18:50.549 --> 00:18:52.750 mathematical boundaries so the output cleanly 00:18:52.750 --> 00:18:55.670 wraps around from 1 to 7 instead of 0 to 6. That 00:18:55.670 --> 00:18:58.130 makes total sense. It is a perfect example of 00:18:58.130 --> 00:19:01.150 how pure math has to be wrestled and nudged to 00:19:01.150 --> 00:19:04.000 actually mirror human reality. Which brings us 00:19:04.000 --> 00:19:06.259 to the end of our deep dive. And honestly, my 00:19:06.259 --> 00:19:09.480 brain is slightly spinning. We started with the 00:19:09.480 --> 00:19:12.160 simplest concept imaginable, dividing leftover 00:19:12.160 --> 00:19:15.019 pizza slices to find a remainder. But the exact 00:19:15.019 --> 00:19:16.900 second we introduced the reality of negative 00:19:16.900 --> 00:19:19.460 numbers, we uncovered a full -blown mathematical 00:19:19.460 --> 00:19:22.000 crisis. Yeah, we navigated the tribal wars of 00:19:22.000 --> 00:19:24.640 computing. The hardware purists using truncated 00:19:24.640 --> 00:19:27.319 division, the mathematical idealists using floor 00:19:27.319 --> 00:19:30.259 division, and the chaos of them disagreeing silently. 00:19:30.480 --> 00:19:33.140 We saw how failing to understand those tribes 00:19:33.140 --> 00:19:36.200 leads to the infamous negative one logic trap 00:19:36.200 --> 00:19:39.140 that breaks even the simplest code. We dug into 00:19:39.140 --> 00:19:42.519 the binary hardware to see how bitwise and Dmasks 00:19:42.519 --> 00:19:45.319 can hyper optimize performance unless the ambiguity 00:19:45.319 --> 00:19:48.400 of negative signs forces the compiler to abandon 00:19:48.400 --> 00:19:51.359 the shortcut entirely. And finally, we saw how 00:19:51.359 --> 00:19:53.640 the wraparound information destroying nature 00:19:53.640 --> 00:19:56.539 of modulo forms the one way trap doors that make 00:19:56.539 --> 00:19:59.059 modern cryptography possible. It really highlights 00:19:59.059 --> 00:20:01.509 that in computer science, nothing is quite as 00:20:01.509 --> 00:20:03.750 clean as it appears on a chalkboard. So I want 00:20:03.750 --> 00:20:05.569 to leave you with the final thought to mull over. 00:20:06.109 --> 00:20:08.930 We open by talking about the expectation of absolute 00:20:08.930 --> 00:20:11.549 precision. We assume that when we type an equation 00:20:11.549 --> 00:20:14.509 into a calculator, the answer we get is a universal 00:20:14.509 --> 00:20:16.930 truth. But today we saw that something as fundamental 00:20:16.930 --> 00:20:19.509 as dividing by 2 and finding a remainder doesn't 00:20:19.509 --> 00:20:22.119 actually have a single objective answer. Right. 00:20:22.119 --> 00:20:24.920 It has tribes. It has hardware constraints. It 00:20:24.920 --> 00:20:27.660 has compromises. So the next time you look at 00:20:27.660 --> 00:20:30.359 a seemingly basic rule or a standard interface 00:20:30.359 --> 00:20:33.440 in the technology you use every single day, ask 00:20:33.440 --> 00:20:35.519 yourself what edge case did the creators have 00:20:35.519 --> 00:20:38.940 to argue over to make this work? If basic arithmetic 00:20:38.940 --> 00:20:41.539 itself has to compromise to fit inside a computer 00:20:41.539 --> 00:20:44.740 processor, what other absolute truths in our 00:20:44.740 --> 00:20:46.799 digital world are really just tribal agreements 00:20:46.799 --> 00:20:49.319 in disguise? It forces you to question the foundation 00:20:49.319 --> 00:20:51.650 of every system you use. It really does. Thanks 00:20:51.650 --> 00:20:53.309 for joining us on this deep dive. See you next 00:20:53.309 --> 00:20:53.450 time.