1 00:00:00,000 --> 00:00:00,090 2 00:00:00,090 --> 00:00:01,800 The following content is provided 3 00:00:01,800 --> 00:00:04,040 under a Creative Commons license. 4 00:00:04,040 --> 00:00:06,880 Your support will help MIT OpenCourseWare continue 5 00:00:06,880 --> 00:00:10,740 to offer high quality educational resources for free. 6 00:00:10,740 --> 00:00:13,360 To make a donation or view additional materials 7 00:00:13,360 --> 00:00:17,237 from hundreds of MIT courses, visit MIT OpenCourseWare 8 00:00:17,237 --> 00:00:17,862 at ocw.mit.edu. 9 00:00:17,862 --> 00:00:21,560 10 00:00:21,560 --> 00:00:23,410 PROFESSOR: Everything make sense? 11 00:00:23,410 --> 00:00:25,928 Are you guys good with Newton? 12 00:00:25,928 --> 00:00:27,420 AUDIENCE: [INAUDIBLE]. 13 00:00:27,420 --> 00:00:28,880 PROFESSOR: Yes, really? 14 00:00:28,880 --> 00:00:29,380 I'm done. 15 00:00:29,380 --> 00:00:30,570 I'm going home. 16 00:00:30,570 --> 00:00:34,412 Are you guys good with Karatsuba? 17 00:00:34,412 --> 00:00:35,360 AUDIENCE: [INAUDIBLE]. 18 00:00:35,360 --> 00:00:36,234 PROFESSOR: Kara-what? 19 00:00:36,234 --> 00:00:41,300 [LAUGHTER] 20 00:00:41,300 --> 00:00:46,090 OK, so who is happy with Karatsuba? 21 00:00:46,090 --> 00:00:47,100 Good. 22 00:00:47,100 --> 00:00:48,220 Who is happy with Newton? 23 00:00:48,220 --> 00:00:53,190 24 00:00:53,190 --> 00:00:53,690 Wait. 25 00:00:53,690 --> 00:00:56,150 I need to ask the other ones, because not enough people-- 26 00:00:56,150 --> 00:01:01,860 who is not happy with Newton and wants to look over it? 27 00:01:01,860 --> 00:01:05,471 Who wants to look over Karatsuba? 28 00:01:05,471 --> 00:01:06,970 Oh, so you guy are paying attention. 29 00:01:06,970 --> 00:01:07,570 Good. 30 00:01:07,570 --> 00:01:08,770 OK. 31 00:01:08,770 --> 00:01:09,270 All right. 32 00:01:09,270 --> 00:01:10,520 So Newton and Karatsuba. 33 00:01:10,520 --> 00:01:11,130 Let's start. 34 00:01:11,130 --> 00:01:19,130 35 00:01:19,130 --> 00:01:21,240 So Karatsuba real fast, and then we'll 36 00:01:21,240 --> 00:01:24,120 spend more time having fun with Newton. 37 00:01:24,120 --> 00:01:26,260 So suppose we don't know Karatsuba. 38 00:01:26,260 --> 00:01:27,920 We want to multiply two numbers. 39 00:01:27,920 --> 00:01:32,946 What's the method that we learned in elementary school? 40 00:01:32,946 --> 00:01:35,750 AUDIENCE: You take the first digit of the first number, 41 00:01:35,750 --> 00:01:39,446 and then you multiply it by the second number. 42 00:01:39,446 --> 00:01:40,890 And then you take the second digit 43 00:01:40,890 --> 00:01:44,285 and multiply it by the second number, but then you add a 0. 44 00:01:44,285 --> 00:01:47,260 And so on and so forth. 45 00:01:47,260 --> 00:01:49,790 PROFESSOR: So I'll take this digit 46 00:01:49,790 --> 00:01:53,330 and multiply it with this number and write the result down here, 47 00:01:53,330 --> 00:01:54,400 right? 48 00:01:54,400 --> 00:01:58,360 So whatever this thing happens to be, 1, 2, 3, 4 times 8, 49 00:01:58,360 --> 00:01:59,150 write the result. 50 00:01:59,150 --> 00:02:05,440 Then I take 1, 2, 3, 4 times 7 and add the result here 51 00:02:05,440 --> 00:02:07,430 and the last digits are 0. 52 00:02:07,430 --> 00:02:11,790 1, 2, 3, 4 times 6, two 0s. 53 00:02:11,790 --> 00:02:19,380 1, 2, 3, 4 times 5, three 0s. 54 00:02:19,380 --> 00:02:22,280 Then I add these up and I know that I'm 55 00:02:22,280 --> 00:02:25,206 going to get the right result. 56 00:02:25,206 --> 00:02:26,580 What's the running time for this? 57 00:02:26,580 --> 00:02:30,285 58 00:02:30,285 --> 00:02:31,607 AUDIENCE: [INAUDIBLE]. 59 00:02:31,607 --> 00:02:32,190 PROFESSOR: OK. 60 00:02:32,190 --> 00:02:37,690 61 00:02:37,690 --> 00:02:39,899 So why is it n squared? 62 00:02:39,899 --> 00:02:42,024 AUDIENCE: Because you go through every single thing 63 00:02:42,024 --> 00:02:43,716 for every digit below. 64 00:02:43,716 --> 00:02:44,340 PROFESSOR: Yup. 65 00:02:44,340 --> 00:02:48,560 So I'll have these partial products here, 66 00:02:48,560 --> 00:02:50,390 and I have as many partial products 67 00:02:50,390 --> 00:02:51,780 as digits in the second number. 68 00:02:51,780 --> 00:02:56,250 So if I have n digits here, I have n partial products. 69 00:02:56,250 --> 00:02:59,220 Each partial product is this first number here multiplied 70 00:02:59,220 --> 00:03:00,520 by a digit. 71 00:03:00,520 --> 00:03:03,070 So if this guy has n digits, then there 72 00:03:03,070 --> 00:03:06,170 are n digits everywhere here. 73 00:03:06,170 --> 00:03:09,250 And this thing will be 2 n insides actually, 74 00:03:09,250 --> 00:03:11,630 but we're doing asymptotic, so we don't really 75 00:03:11,630 --> 00:03:13,450 care about constant factors. 76 00:03:13,450 --> 00:03:15,730 So in the end, you have to add up n numbers. 77 00:03:15,730 --> 00:03:17,890 All of them are order n in size. 78 00:03:17,890 --> 00:03:20,530 So n times order n squared. 79 00:03:20,530 --> 00:03:23,540 This is plain old multiplication. 80 00:03:23,540 --> 00:03:25,790 Does anyone know why Karatsuba's better? 81 00:03:25,790 --> 00:03:29,575 82 00:03:29,575 --> 00:03:30,075 Yes? 83 00:03:30,075 --> 00:03:32,288 AUDIENCE: You do three multiplications 84 00:03:32,288 --> 00:03:33,719 or something like that? 85 00:03:33,719 --> 00:03:34,680 PROFESSOR: OK. 86 00:03:34,680 --> 00:03:37,472 So, let's go for a simple answer. 87 00:03:37,472 --> 00:03:38,388 AUDIENCE: It's better. 88 00:03:38,388 --> 00:03:45,350 89 00:03:45,350 --> 00:03:48,893 PROFESSOR: So the simpler answer is it's faster. 90 00:03:48,893 --> 00:03:49,780 AUDIENCE: OK. 91 00:03:49,780 --> 00:03:52,854 PROFESSOR: n, n log 2-- 92 00:03:52,854 --> 00:03:55,870 AUDIENCE: I said better, it's faster. 93 00:03:55,870 --> 00:03:58,120 PROFESSOR: I mean, some algorithms have the same speed 94 00:03:58,120 --> 00:03:59,200 but are simpler. 95 00:03:59,200 --> 00:04:00,770 We like this one because it's faster. 96 00:04:00,770 --> 00:04:02,550 It's definitely not simpler. 97 00:04:02,550 --> 00:04:04,210 So, it has this running time here. 98 00:04:04,210 --> 00:04:06,090 Log 2 of 3 is a weird number. 99 00:04:06,090 --> 00:04:08,050 It's somewhere between 1.5 and 2. 100 00:04:08,050 --> 00:04:13,250 So not revolutionary, but it's better than this guy. 101 00:04:13,250 --> 00:04:15,420 OK, why do we get to this? 102 00:04:15,420 --> 00:04:16,959 How do we get to this? 103 00:04:16,959 --> 00:04:18,880 Does anyone remember the recurrence for it? 104 00:04:18,880 --> 00:04:21,630 105 00:04:21,630 --> 00:04:22,895 Yes? 106 00:04:22,895 --> 00:04:24,289 AUDIENCE: It's 3 times 2-- 107 00:04:24,289 --> 00:04:25,830 PROFESSOR: You're not remembering it. 108 00:04:25,830 --> 00:04:26,794 You're cheating. 109 00:04:26,794 --> 00:04:27,710 AUDIENCE: No, I'm not. 110 00:04:27,710 --> 00:04:29,686 [LAUGHTER] 111 00:04:29,686 --> 00:04:35,460 112 00:04:35,460 --> 00:04:37,460 PROFESSOR: So, let's see why it looks like this. 113 00:04:37,460 --> 00:04:48,590 Karatsuba takes 2 numbers that have n digits, splits both 114 00:04:48,590 --> 00:04:57,310 of them up into two-- n over 2n, n over 2, n over 2, n over 2-- 115 00:04:57,310 --> 00:05:00,300 and then is able to compute the product of these two numbers 116 00:05:00,300 --> 00:05:03,830 by only using three multiplications, and then 117 00:05:03,830 --> 00:05:05,160 some additions. 118 00:05:05,160 --> 00:05:08,360 Multiplications are expensive, additions are cheap. 119 00:05:08,360 --> 00:05:15,830 So it does three multiplications that are of the form 120 00:05:15,830 --> 00:05:18,710 some number of n over 2 digits multiplied 121 00:05:18,710 --> 00:05:24,310 by some number of n over or 2 digits. 122 00:05:24,310 --> 00:05:27,370 And exactly what the multiplications and what 123 00:05:27,370 --> 00:05:31,200 the additions are is, it's interesting to look over it. 124 00:05:31,200 --> 00:05:35,160 You can look over it, convince yourself that this is correct. 125 00:05:35,160 --> 00:05:39,780 Chances are you'll remember for the exam and forget afterwards. 126 00:05:39,780 --> 00:05:41,190 Please remember this. 127 00:05:41,190 --> 00:05:43,090 This is the essence of Karatsuba. 128 00:05:43,090 --> 00:05:49,532 And remember Karatsuba, because if you google this, 129 00:05:49,532 --> 00:05:50,240 you get the rest. 130 00:05:50,240 --> 00:05:52,604 131 00:05:52,604 --> 00:05:54,270 So the multiplications are in the notes. 132 00:05:54,270 --> 00:05:57,040 I don't think it makes sense to spend some time on them 133 00:05:57,040 --> 00:05:58,670 and convince you that, yeah, there 134 00:05:58,670 --> 00:06:01,180 are three multiplications that will get you that. 135 00:06:01,180 --> 00:06:08,740 Instead, suppose I labeled these as a, b, c, d. 136 00:06:08,740 --> 00:06:12,130 If I evaluate the multiplication as using brute force, 137 00:06:12,130 --> 00:06:21,940 it's a times n over 2b plus c-- sorry, a plus-- no, 138 00:06:21,940 --> 00:06:23,000 this isn't good. 139 00:06:23,000 --> 00:06:29,300 10 to the power n over 2a plus b times 10-- assuming the base 140 00:06:29,300 --> 00:06:35,400 is ten, if it's not, you replace it-- n over 2 c plus d. 141 00:06:35,400 --> 00:06:46,030 And you get 10 to the n times, I think, ac plus 10 142 00:06:46,030 --> 00:06:54,030 to the n over 2 times ad plus bc plus bd. 143 00:06:54,030 --> 00:06:57,820 144 00:06:57,820 --> 00:07:00,486 The problem with this is this is a multiplication, 145 00:07:00,486 --> 00:07:04,190 multiplication, multiplication, multiplication. 146 00:07:04,190 --> 00:07:07,000 So this uses four multiplications 147 00:07:07,000 --> 00:07:11,120 of size n over 2 to evaluate the answer one 148 00:07:11,120 --> 00:07:13,040 multiplication of size n. 149 00:07:13,040 --> 00:07:14,800 And if I have four multiplications, 150 00:07:14,800 --> 00:07:21,500 then the recursion becomes 4t of n over 2 plus o of n. 151 00:07:21,500 --> 00:07:25,600 152 00:07:25,600 --> 00:07:27,570 So this is t bad of n. 153 00:07:27,570 --> 00:07:29,690 So if you do this using the recursion tree, 154 00:07:29,690 --> 00:07:35,790 you're going to see that-- yup, I hear whispers. 155 00:07:35,790 --> 00:07:36,970 n squared. 156 00:07:36,970 --> 00:07:39,590 So this isn't useful. 157 00:07:39,590 --> 00:07:41,470 This will give you insight on how to do it, 158 00:07:41,470 --> 00:07:44,060 but if you try to implement it this way, 159 00:07:44,060 --> 00:07:46,360 you don't get any speed up. 160 00:07:46,360 --> 00:07:48,971 The insight in Karatsuba is that the guy figured out 161 00:07:48,971 --> 00:07:50,720 how to do this with three multiplications. 162 00:07:50,720 --> 00:07:55,420 163 00:07:55,420 --> 00:07:56,260 OK, makes sense? 164 00:07:56,260 --> 00:07:59,050 Is everyone happy with Karatsuba now? 165 00:07:59,050 --> 00:08:02,605 So that multiplying by 10 to the n over 2 is just shifting a? 166 00:08:02,605 --> 00:08:03,230 PROFESSOR: Yup. 167 00:08:03,230 --> 00:08:03,804 OK. 168 00:08:03,804 --> 00:08:04,470 Very good point. 169 00:08:04,470 --> 00:08:06,750 So this isn't an actual multiplication. 170 00:08:06,750 --> 00:08:14,590 If you have your number, say stored in a python list-- 171 00:08:14,590 --> 00:08:16,430 so if these are your digits, then 172 00:08:16,430 --> 00:08:18,940 in order to multiply by 10 to the n, 173 00:08:18,940 --> 00:08:21,960 you append 10 to the n 0s at the end. 174 00:08:21,960 --> 00:08:25,630 0, 0, 0, 0, 0. 175 00:08:25,630 --> 00:08:34,409 So, this is append of 0 n times. 176 00:08:34,409 --> 00:08:37,200 So this is order n, so it counts as an addition, not as 177 00:08:37,200 --> 00:08:39,020 a multiplication. 178 00:08:39,020 --> 00:08:41,440 So, these are free. 179 00:08:41,440 --> 00:08:43,870 These are expensive. 180 00:08:43,870 --> 00:08:46,358 1, 2, 3, 4. 181 00:08:46,358 --> 00:08:51,320 182 00:08:51,320 --> 00:08:51,820 OK. 183 00:08:51,820 --> 00:08:54,030 Who's happy with Karatsuba now? 184 00:08:54,030 --> 00:08:56,744 Let me feel like I did something useful today. 185 00:08:56,744 --> 00:08:57,910 AUDIENCE: I have a question. 186 00:08:57,910 --> 00:08:58,535 PROFESSOR: Yes. 187 00:08:58,535 --> 00:09:00,820 AUDIENCE: I didn't fully understand what [INAUDIBLE]. 188 00:09:00,820 --> 00:09:05,820 189 00:09:05,820 --> 00:09:08,100 PROFESSOR: So, I have this number 190 00:09:08,100 --> 00:09:11,310 and I'm splitting it up into 2 halves. 191 00:09:11,310 --> 00:09:15,950 The way split up is I say this is a number of size n over 2, 192 00:09:15,950 --> 00:09:17,420 and I have to shift it to the left. 193 00:09:17,420 --> 00:09:21,870 So n 10 to the power of n over 2 shifts 194 00:09:21,870 --> 00:09:23,960 it left by n over two digits. 195 00:09:23,960 --> 00:09:24,946 And then I add it to b. 196 00:09:24,946 --> 00:09:26,320 So this in a sense is just saying 197 00:09:26,320 --> 00:09:28,554 that this is the left half, this is the right half. 198 00:09:28,554 --> 00:09:30,520 AUDIENCE: This is actually that same number. 199 00:09:30,520 --> 00:09:30,775 PROFESSOR: Yup. 200 00:09:30,775 --> 00:09:32,100 It's exactly the same number. 201 00:09:32,100 --> 00:09:37,820 202 00:09:37,820 --> 00:09:41,439 OK, so who is happy with Karatsuba now? 203 00:09:41,439 --> 00:09:43,730 AUDIENCE: Wait, but that's four multiplications though. 204 00:09:43,730 --> 00:09:44,500 PROFESSOR: Exactly. 205 00:09:44,500 --> 00:09:45,260 AUDIENCE: That's not three. 206 00:09:45,260 --> 00:09:45,640 PROFESSOR: Exactly. 207 00:09:45,640 --> 00:09:47,560 AUDIENCE: But we said there were three. 208 00:09:47,560 --> 00:09:49,570 PROFESSOR: So, I was saying that this, 209 00:09:49,570 --> 00:09:52,410 if you;re doing it the brute force way, you get four, 210 00:09:52,410 --> 00:09:54,240 and that is slow. 211 00:09:54,240 --> 00:09:56,120 So what Karatsuba did is he figured out 212 00:09:56,120 --> 00:09:58,580 the way to do this with just three multiplications. 213 00:09:58,580 --> 00:09:59,580 So it's not these three. 214 00:09:59,580 --> 00:10:01,520 You have to think a little bit more. 215 00:10:01,520 --> 00:10:03,877 But you google it, or you look at the lecture notes, 216 00:10:03,877 --> 00:10:05,710 or you think a little bit, then you find out 217 00:10:05,710 --> 00:10:09,700 the three multiplications that do the trick. 218 00:10:09,700 --> 00:10:12,720 So the difference between this 4 here and this 3 219 00:10:12,720 --> 00:10:13,470 here is important. 220 00:10:13,470 --> 00:10:19,337 221 00:10:19,337 --> 00:10:20,920 All right, anything else on Karatsuba? 222 00:10:20,920 --> 00:10:25,400 223 00:10:25,400 --> 00:10:26,500 Cool. 224 00:10:26,500 --> 00:10:27,740 Let's talk about Newton. 225 00:10:27,740 --> 00:10:30,150 That's the hard stuff. 226 00:10:30,150 --> 00:10:33,500 And let me see how we're doing on time. 227 00:10:33,500 --> 00:10:35,287 OK, doing well. 228 00:10:35,287 --> 00:10:37,120 So does anyone remember the point of Newton? 229 00:10:37,120 --> 00:10:42,170 230 00:10:42,170 --> 00:10:44,590 OK, so I heard an application that 231 00:10:44,590 --> 00:10:46,590 lets you compute square roots. 232 00:10:46,590 --> 00:10:47,820 What else does it let you do? 233 00:10:47,820 --> 00:10:52,760 234 00:10:52,760 --> 00:10:54,250 AUDIENCE: [INAUDIBLE]. 235 00:10:54,250 --> 00:10:57,685 PROFESSOR: OK, we have Karatsuba for multiplication. 236 00:10:57,685 --> 00:10:59,310 You might be able to do it with Newton. 237 00:10:59,310 --> 00:11:00,740 Probably not going to be faster. 238 00:11:00,740 --> 00:11:03,810 But division, definitely. 239 00:11:03,810 --> 00:11:05,380 So square roots and division. 240 00:11:05,380 --> 00:11:07,990 So this is why we care about it. 241 00:11:07,990 --> 00:11:10,460 Now what does it do from a mathy perspective? 242 00:11:10,460 --> 00:11:13,380 So what's the mathy definition of Newton. 243 00:11:13,380 --> 00:11:15,356 AUDIENCE: Estimates-- 244 00:11:15,356 --> 00:11:16,230 PROFESSOR: Estimates? 245 00:11:16,230 --> 00:11:17,120 AUDIENCE: The value-- 246 00:11:17,120 --> 00:11:18,002 PROFESSOR: OK. 247 00:11:18,002 --> 00:11:18,960 So, we have a function. 248 00:11:18,960 --> 00:11:22,270 249 00:11:22,270 --> 00:11:24,770 Suppose it looks like this. 250 00:11:24,770 --> 00:11:26,840 So, what Newton helps us do is it 251 00:11:26,840 --> 00:11:29,230 helps us find a root of the function. 252 00:11:29,230 --> 00:11:37,990 And the root is a value x 0 so that f of x 0 equals 0. 253 00:11:37,990 --> 00:11:39,060 So this is what it does. 254 00:11:39,060 --> 00:11:40,518 So when you want to use Newton, you 255 00:11:40,518 --> 00:11:42,640 have to set up your function in such a way 256 00:11:42,640 --> 00:11:43,900 that your answer is a root. 257 00:11:43,900 --> 00:11:52,670 258 00:11:52,670 --> 00:11:54,840 OK. 259 00:11:54,840 --> 00:11:55,965 How does Newton work? 260 00:11:55,965 --> 00:11:59,220 261 00:11:59,220 --> 00:11:59,720 Yes? 262 00:11:59,720 --> 00:12:02,185 263 00:12:02,185 --> 00:12:03,560 AUDIENCE: You start at some point 264 00:12:03,560 --> 00:12:05,268 where you actually know the answer to it, 265 00:12:05,268 --> 00:12:08,462 and then you kind of draw a approximation. 266 00:12:08,462 --> 00:12:10,837 So you're just drawing a line from the point to the root, 267 00:12:10,837 --> 00:12:13,567 and then just incrementing down that line. 268 00:12:13,567 --> 00:12:14,150 PROFESSOR: OK. 269 00:12:14,150 --> 00:12:15,970 So we start at some point, right? 270 00:12:15,970 --> 00:12:17,580 How do we call that point? 271 00:12:17,580 --> 00:12:18,500 Initial guess. 272 00:12:18,500 --> 00:12:19,360 Fancy name. 273 00:12:19,360 --> 00:12:22,980 So we have an initial guess for what the root might be. 274 00:12:22,980 --> 00:12:25,510 It's not going to be the right answer, because otherwise 275 00:12:25,510 --> 00:12:26,718 why am I bothering with this? 276 00:12:26,718 --> 00:12:28,119 But it can be too far off. 277 00:12:28,119 --> 00:12:29,660 We'll say that if you're too far off, 278 00:12:29,660 --> 00:12:31,409 you're not going to converge or you're not 279 00:12:31,409 --> 00:12:32,870 going to converge fast enough. 280 00:12:32,870 --> 00:12:37,800 So say we start somewhere here and, we think, you know, 281 00:12:37,800 --> 00:12:38,810 this is pretty close. 282 00:12:38,810 --> 00:12:41,160 It's not quite there, but it's pretty close. 283 00:12:41,160 --> 00:12:43,050 What I do from here on is, you said 284 00:12:43,050 --> 00:12:45,736 I approximate this function-- 285 00:12:45,736 --> 00:12:46,670 AUDIENCE: The line. 286 00:12:46,670 --> 00:12:47,460 PROFESSOR: Yep. 287 00:12:47,460 --> 00:12:49,214 So what's of the best line? 288 00:12:49,214 --> 00:12:50,880 The best way to approximate the function 289 00:12:50,880 --> 00:12:53,230 with the line is to use is the tangent, right? 290 00:12:53,230 --> 00:12:57,130 So here, it sort of looks like this. 291 00:12:57,130 --> 00:12:58,690 And if the function were linear, this 292 00:12:58,690 --> 00:13:00,490 would be a perfect approximation and we'd 293 00:13:00,490 --> 00:13:02,791 get answer in one step. 294 00:13:02,791 --> 00:13:03,290 OK. 295 00:13:03,290 --> 00:13:04,400 So this is the tangent. 296 00:13:04,400 --> 00:13:07,441 And then what we do with this tangent? 297 00:13:07,441 --> 00:13:09,482 AUDIENCE: Well, after we get the equation for it, 298 00:13:09,482 --> 00:13:13,766 then we find the root, right? 299 00:13:13,766 --> 00:13:14,767 Or no? 300 00:13:14,767 --> 00:13:16,850 PROFESSOR: Well, I can't find the root right away. 301 00:13:16,850 --> 00:13:17,730 AUDIENCE: The root of that line. 302 00:13:17,730 --> 00:13:18,610 Of our tangent line. 303 00:13:18,610 --> 00:13:19,193 PROFESSOR: OK. 304 00:13:19,193 --> 00:13:20,922 So we find the root of the tangent, which 305 00:13:20,922 --> 00:13:22,505 is the point where it hits the x-axis. 306 00:13:22,505 --> 00:13:25,230 307 00:13:25,230 --> 00:13:28,805 And what happens with this point? 308 00:13:28,805 --> 00:13:30,740 AUDIENCE: [INAUDIBLE]. 309 00:13:30,740 --> 00:13:32,710 PROFESSOR: OK, so this is our next guess. 310 00:13:32,710 --> 00:13:33,460 And then we trade. 311 00:13:33,460 --> 00:13:37,100 312 00:13:37,100 --> 00:13:38,990 So then we draw another tangent, and the idea 313 00:13:38,990 --> 00:13:41,300 is that eventually, you're going to get there. 314 00:13:41,300 --> 00:13:42,879 And if we go through the maths, we 315 00:13:42,879 --> 00:13:44,920 will see that you actually get there pretty fast. 316 00:13:44,920 --> 00:13:47,880 So that's why we like this method. 317 00:13:47,880 --> 00:13:52,980 So let's see how we convert this drawing thing into an equation 318 00:13:52,980 --> 00:13:54,900 that you can write into python. 319 00:13:54,900 --> 00:13:56,730 Let's label these quantities. 320 00:13:56,730 --> 00:14:01,694 So, x2, x1-- actually let's not use 1 and 2, 321 00:14:01,694 --> 00:14:03,360 because these are the first two guesses. 322 00:14:03,360 --> 00:14:08,830 Let's say our current guess is x and the next guess is x prime. 323 00:14:08,830 --> 00:14:19,170 So this line and is x1 minus x, so this guy over here. 324 00:14:19,170 --> 00:14:20,470 And what's this guy over here? 325 00:14:20,470 --> 00:14:25,400 326 00:14:25,400 --> 00:14:27,070 f of x. 327 00:14:27,070 --> 00:14:27,900 Don't be shy. 328 00:14:27,900 --> 00:14:29,330 It's the right answer. 329 00:14:29,330 --> 00:14:33,840 So I have f of x here, x 1 minus x here. 330 00:14:33,840 --> 00:14:37,750 I also have this angle here, and this angle here 331 00:14:37,750 --> 00:14:39,330 is the same angle as the angle here 332 00:14:39,330 --> 00:14:41,790 because both of these lines are horizontal, 333 00:14:41,790 --> 00:14:43,900 so they're parallel. 334 00:14:43,900 --> 00:14:46,572 So what do I know about this angle? 335 00:14:46,572 --> 00:14:47,530 AUDIENCE: It's tangent. 336 00:14:47,530 --> 00:14:48,530 PROFESSOR: It's tangent. 337 00:14:48,530 --> 00:14:50,510 338 00:14:50,510 --> 00:14:51,080 OK. 339 00:14:51,080 --> 00:14:52,890 The tangent, that's called the angle alpha. 340 00:14:52,890 --> 00:14:56,170 What's the tangent of the angle? 341 00:14:56,170 --> 00:14:57,086 AUDIENCE: [INAUDIBLE]. 342 00:14:57,086 --> 00:15:02,280 343 00:15:02,280 --> 00:15:04,280 PROFESSOR: Sorry? 344 00:15:04,280 --> 00:15:07,940 AUDIENCE: F of x over x [INAUDIBLE]. 345 00:15:07,940 --> 00:15:10,549 346 00:15:10,549 --> 00:15:12,340 PROFESSOR: I think you're trying to give me 347 00:15:12,340 --> 00:15:15,040 the formula for x prime. 348 00:15:15,040 --> 00:15:15,970 Just the tangent. 349 00:15:15,970 --> 00:15:16,940 Just the tangent. 350 00:15:16,940 --> 00:15:20,735 351 00:15:20,735 --> 00:15:22,070 AUDIENCE: Oh. 352 00:15:22,070 --> 00:15:24,630 PROFESSOR: Right? 353 00:15:24,630 --> 00:15:25,770 Can someone reassure me? 354 00:15:25,770 --> 00:15:26,770 This is right, right? 355 00:15:26,770 --> 00:15:27,940 [AUDIENCE AGREES] 356 00:15:27,940 --> 00:15:29,987 AUDIENCE: I was thinking the slope of the line. 357 00:15:29,987 --> 00:15:30,570 PROFESSOR: OK. 358 00:15:30,570 --> 00:15:31,980 So, yeah, you're going to give me 359 00:15:31,980 --> 00:15:34,570 the slope of the line which lets me compute this. 360 00:15:34,570 --> 00:15:36,730 OK, I was looking for this. 361 00:15:36,730 --> 00:15:37,230 OK. 362 00:15:37,230 --> 00:15:39,430 So now, let's get what you're saying. 363 00:15:39,430 --> 00:15:40,730 So this is the tangent, right? 364 00:15:40,730 --> 00:15:43,320 365 00:15:43,320 --> 00:15:45,710 So, the tangent at a point of a function 366 00:15:45,710 --> 00:15:48,440 is the function's derivative. 367 00:15:48,440 --> 00:15:51,960 So now we're going to write all these things down and hope 368 00:15:51,960 --> 00:15:54,740 that we get an equation that make sense. 369 00:15:54,740 --> 00:15:58,730 So we have the tangent of this guy, 370 00:15:58,730 --> 00:16:01,881 also happens to be this over this. 371 00:16:01,881 --> 00:16:02,380 Right? 372 00:16:02,380 --> 00:16:06,830 This is a right angle triangle, so the tangent 373 00:16:06,830 --> 00:16:09,290 is f of x over-- this is what you 374 00:16:09,290 --> 00:16:11,890 were trying to tell me, right? 375 00:16:11,890 --> 00:16:13,790 x1 minus x. 376 00:16:13,790 --> 00:16:16,980 So now I know that this is f prime of x. 377 00:16:16,980 --> 00:16:22,830 378 00:16:22,830 --> 00:16:23,330 OK. 379 00:16:23,330 --> 00:16:26,220 380 00:16:26,220 --> 00:16:30,420 So, we look at the picture, we put in everything we know, 381 00:16:30,420 --> 00:16:32,420 and then we write an equation here. 382 00:16:32,420 --> 00:16:38,560 And we solve for-- sorry, this is x prime. 383 00:16:38,560 --> 00:16:40,720 So, if we solve for x prime, we're 384 00:16:40,720 --> 00:16:43,720 going to get x prime as a function of x. 385 00:16:43,720 --> 00:16:46,850 And this tells us, given a guess here, 386 00:16:46,850 --> 00:16:48,856 how do we compute the next guess? 387 00:16:48,856 --> 00:16:50,230 So once we have an initial guess, 388 00:16:50,230 --> 00:16:52,104 this lets us make the guess better and better 389 00:16:52,104 --> 00:16:55,680 and better, closer and closer and closer to x0. 390 00:16:55,680 --> 00:16:58,860 So, let's solve this equation reasonably quickly. 391 00:16:58,860 --> 00:17:04,210 392 00:17:04,210 --> 00:17:10,945 x prime minus x equals f prime of x over f of x, so 393 00:17:10,945 --> 00:17:13,800 x prime is-- 394 00:17:13,800 --> 00:17:18,165 AUDIENCE: Does it matter if it's x minus x prime or [INAUDIBLE], 395 00:17:18,165 --> 00:17:20,269 because technically it's x minus x prime. 396 00:17:20,269 --> 00:17:22,060 PROFESSOR: Yeah, it matters, because you're 397 00:17:22,060 --> 00:17:24,079 going to get the wrong sign. 398 00:17:24,079 --> 00:17:26,346 Which is exactly what I'm about to do here. 399 00:17:26,346 --> 00:17:27,514 AUDIENCE: Oh, OK. 400 00:17:27,514 --> 00:17:29,430 PROFESSOR: So, I'm not going very well, right? 401 00:17:29,430 --> 00:17:36,060 402 00:17:36,060 --> 00:17:36,660 This is wrong. 403 00:17:36,660 --> 00:17:41,088 AUDIENCE: Yeah, it's because you flipped your x at your prime-- 404 00:17:41,088 --> 00:17:44,084 AUDIENCE: x minus x prime instead of x prime-- 405 00:17:44,084 --> 00:17:46,500 AUDIENCE: No, I think it's because f prime of x is on top. 406 00:17:46,500 --> 00:17:47,715 It should be on the bottom. 407 00:17:47,715 --> 00:17:51,040 In the second-- no, third equation. 408 00:17:51,040 --> 00:17:52,465 Shouldn't those be flipped? 409 00:17:52,465 --> 00:17:55,814 Because if you move the subtraction, 410 00:17:55,814 --> 00:17:57,758 x prime to the left-- 411 00:17:57,758 --> 00:18:03,104 412 00:18:03,104 --> 00:18:04,080 PROFESSOR: f what? 413 00:18:04,080 --> 00:18:06,576 414 00:18:06,576 --> 00:18:08,200 AUDIENCE: f of x over f minus x instead 415 00:18:08,200 --> 00:18:12,380 of f prime x over f of x. 416 00:18:12,380 --> 00:18:15,677 Yeah, there you go. 417 00:18:15,677 --> 00:18:17,010 PROFESSOR: OK, so I can do math. 418 00:18:17,010 --> 00:18:18,150 OK, so that's one issue. 419 00:18:18,150 --> 00:18:19,110 There's one more issue. 420 00:18:19,110 --> 00:18:21,380 So, there are too many issues here. 421 00:18:21,380 --> 00:18:23,400 Issue number one, this. 422 00:18:23,400 --> 00:18:26,229 Issue number two, I got this wrong. 423 00:18:26,229 --> 00:18:27,854 AUDIENCE: Oh, we get a negative number. 424 00:18:27,854 --> 00:18:29,646 AUDIENCE: 2x minus x prime. 425 00:18:29,646 --> 00:18:30,270 PROFESSOR: Yep. 426 00:18:30,270 --> 00:18:32,385 So the reason for that is we're going-- 427 00:18:32,385 --> 00:18:34,510 AUDIENCE: Only if you start from the right, though. 428 00:18:34,510 --> 00:18:35,176 PROFESSOR: Yeah. 429 00:18:35,176 --> 00:18:36,724 AUDIENCE: If you start from the left, 430 00:18:36,724 --> 00:18:44,368 if your guess is to the left of the actual root, 431 00:18:44,368 --> 00:18:47,077 it may or may not be different. 432 00:18:47,077 --> 00:18:47,660 PROFESSOR: OK. 433 00:18:47,660 --> 00:18:50,780 So our guess should be to the right. 434 00:18:50,780 --> 00:18:54,030 435 00:18:54,030 --> 00:18:58,180 So this is x minus x prime. 436 00:18:58,180 --> 00:19:00,539 So the reason it's x minus x prime, the way you remember 437 00:19:00,539 --> 00:19:02,580 this and you don't do the same mistake that I did 438 00:19:02,580 --> 00:19:05,910 is, you want to walk against the derivative. 439 00:19:05,910 --> 00:19:08,050 If you walk in the direction of the derivative, 440 00:19:08,050 --> 00:19:09,970 it's going to move you forward, right? 441 00:19:09,970 --> 00:19:19,120 So, if you go in the direction of the derivative, 442 00:19:19,120 --> 00:19:21,580 instead of going backwards like this, 443 00:19:21,580 --> 00:19:24,000 you're going to go forward like this. 444 00:19:24,000 --> 00:19:27,690 So you're going to go away from the solution. 445 00:19:27,690 --> 00:19:32,320 So, this will take us in the right direction, 446 00:19:32,320 --> 00:19:34,480 and this means that it's-- 447 00:19:34,480 --> 00:19:52,050 448 00:19:52,050 --> 00:19:52,550 OK. 449 00:19:52,550 --> 00:19:53,690 So two ways to remember this. 450 00:19:53,690 --> 00:19:55,565 One that you're going against the derivative. 451 00:19:55,565 --> 00:19:57,740 Another one is that you have your guess 452 00:19:57,740 --> 00:19:59,500 and you're subtracting something from it. 453 00:19:59,500 --> 00:20:01,060 AUDIENCE: You flipped your primes again. 454 00:20:01,060 --> 00:20:01,350 PROFESSOR: Again? 455 00:20:01,350 --> 00:20:01,850 Jesus. 456 00:20:01,850 --> 00:20:03,334 [LAUGHTER] 457 00:20:03,334 --> 00:20:05,084 AUDIENCE: I mean, I agree, the prime looks 458 00:20:05,084 --> 00:20:08,097 better on top part of the fraction, but still. 459 00:20:08,097 --> 00:20:08,680 PROFESSOR: OK. 460 00:20:08,680 --> 00:20:11,980 461 00:20:11,980 --> 00:20:15,190 Well clearly, my hand thinks the same thing. 462 00:20:15,190 --> 00:20:18,732 So this is you'd iterate using Newton. 463 00:20:18,732 --> 00:20:20,690 So the way to remember that the signs are right 464 00:20:20,690 --> 00:20:22,299 is your x is somewhere here, and you 465 00:20:22,299 --> 00:20:24,590 know you have to subtract something from it so it looks 466 00:20:24,590 --> 00:20:25,930 like this figure. 467 00:20:25,930 --> 00:20:29,790 And this actually works in all the cases, turns out. 468 00:20:29,790 --> 00:20:33,430 469 00:20:33,430 --> 00:20:35,750 Our guesses are usually smaller than the actual number, 470 00:20:35,750 --> 00:20:38,510 and this still works. 471 00:20:38,510 --> 00:20:40,390 OK, so let's go over Newton. 472 00:20:40,390 --> 00:20:42,840 What do we have, or what do we need in order 473 00:20:42,840 --> 00:20:45,280 to make Newton happen. 474 00:20:45,280 --> 00:20:48,790 So we need to be able to evaluate this, right? 475 00:20:48,790 --> 00:20:51,190 So we need to be able to evaluate 476 00:20:51,190 --> 00:20:58,180 f over f prime of x for any x that Newton gives us. 477 00:20:58,180 --> 00:21:01,210 And for Newton, this is a black box. 478 00:21:01,210 --> 00:21:03,500 So whichever way you use to implement 479 00:21:03,500 --> 00:21:07,280 this is fine, as long as it works reasonably fast. 480 00:21:07,280 --> 00:21:11,550 OK, what else do we need to use Newton. 481 00:21:11,550 --> 00:21:14,470 We need to remember this formula Let's start with something 482 00:21:14,470 --> 00:21:15,350 easy. 483 00:21:15,350 --> 00:21:18,600 Suppose we want to use it to compute a over b. 484 00:21:18,600 --> 00:21:20,600 How do I do that? 485 00:21:20,600 --> 00:21:21,330 What do I need? 486 00:21:21,330 --> 00:21:24,634 487 00:21:24,634 --> 00:21:26,679 AUDIENCE: You need a line, a tangent line 488 00:21:26,679 --> 00:21:27,950 like you did before. 489 00:21:27,950 --> 00:21:30,730 PROFESSOR: Well, that's already taken care of here. 490 00:21:30,730 --> 00:21:33,210 So we have this, and we know that we'll 491 00:21:33,210 --> 00:21:36,000 have to compute this and plug it in here. 492 00:21:36,000 --> 00:21:41,900 So, what do I need to compute a/b using Newton? 493 00:21:41,900 --> 00:21:59,500 494 00:21:59,500 --> 00:22:03,060 So, I need the function, right? 495 00:22:03,060 --> 00:22:03,790 This thing. 496 00:22:03,790 --> 00:22:06,790 I can't say it's something, I have to figure out what it is. 497 00:22:06,790 --> 00:22:09,940 I guess I was confusing because I said assume we have this. 498 00:22:09,940 --> 00:22:10,789 Well, sorry. 499 00:22:10,789 --> 00:22:11,580 We don't have this. 500 00:22:11,580 --> 00:22:12,996 We need to figure out the function 501 00:22:12,996 --> 00:22:15,149 so we can evaluate this. 502 00:22:15,149 --> 00:22:16,940 OK, so we need to come up with the function 503 00:22:16,940 --> 00:22:19,850 so we can evaluate that, and what property 504 00:22:19,850 --> 00:22:21,674 does the function need to meet? 505 00:22:21,674 --> 00:22:22,590 AUDIENCE: [INAUDIBLE]. 506 00:22:22,590 --> 00:22:25,779 507 00:22:25,779 --> 00:22:27,570 PROFESSOR: Yeah, that would be nice, right? 508 00:22:27,570 --> 00:22:34,980 So we want the function so that f of a/b equals 0, 509 00:22:34,980 --> 00:22:37,760 because that's the number that Newton will give us. 510 00:22:37,760 --> 00:22:46,080 And we also need to be able to compute f over f prime of x 511 00:22:46,080 --> 00:22:47,840 without doing any division, right? 512 00:22:47,840 --> 00:22:53,094 If we did the divisions, it doesn't work. 513 00:22:53,094 --> 00:22:54,760 OK, so the first thing we're going to do 514 00:22:54,760 --> 00:22:59,000 is we're going to simplify this problem to 1 over b instead 515 00:22:59,000 --> 00:23:02,630 of a over b, because if you know what's 1 over b, 516 00:23:02,630 --> 00:23:05,400 you're going to multiply this by a, 517 00:23:05,400 --> 00:23:08,160 and you're going to get a over b. 518 00:23:08,160 --> 00:23:11,050 519 00:23:11,050 --> 00:23:13,480 Suppose we work with integers and we 520 00:23:13,480 --> 00:23:16,200 don't want to touch floating point numbers. 521 00:23:16,200 --> 00:23:17,695 What would we actually compute? 522 00:23:17,695 --> 00:23:22,310 523 00:23:22,310 --> 00:23:23,730 AUDIENCE: You shift it out, right? 524 00:23:23,730 --> 00:23:26,920 To get that 0.23, shift now to [INAUDIBLE]. 525 00:23:26,920 --> 00:23:28,310 PROFESSOR: All right, all right. 526 00:23:28,310 --> 00:23:30,150 So 1 over b. 527 00:23:30,150 --> 00:23:32,160 Unless b is 1, in which case it's really boring. 528 00:23:32,160 --> 00:23:33,540 1 over b looks like this. 529 00:23:33,540 --> 00:23:38,410 0 point something. 530 00:23:38,410 --> 00:23:39,710 This is not an integer number. 531 00:23:39,710 --> 00:23:40,830 I don't like it. 532 00:23:40,830 --> 00:23:42,560 So what I do is, I decide that I'm 533 00:23:42,560 --> 00:23:45,880 going to need digits of precision, 534 00:23:45,880 --> 00:23:47,820 and I'm going to shift the decimal point 535 00:23:47,820 --> 00:23:51,130 right by d digits. 536 00:23:51,130 --> 00:23:57,190 So instead of 0 point something, it's 537 00:23:57,190 --> 00:24:00,650 d digits here point something else. 538 00:24:00,650 --> 00:24:04,110 How do I do this? 539 00:24:04,110 --> 00:24:05,580 AUDIENCE: Multiply by 10 to the d? 540 00:24:05,580 --> 00:24:07,038 PROFESSOR: Multiply by 10 to the d. 541 00:24:07,038 --> 00:24:12,830 So instead of computing 1 over b, 10 to the d over b. 542 00:24:12,830 --> 00:24:18,210 And we call this 10 to the d R in our station notes. 543 00:24:18,210 --> 00:24:24,620 So we're going to compute R. Over b multiplied 544 00:24:24,620 --> 00:24:31,190 by a, and then everything divided by R. 545 00:24:31,190 --> 00:24:33,150 So we talked about how you multiply 546 00:24:33,150 --> 00:24:37,080 by R. How do you divide by R? 547 00:24:37,080 --> 00:24:39,230 So, if I have a number with n digits 548 00:24:39,230 --> 00:24:44,875 and I want to divide by 10 to the d, how do I do that? 549 00:24:44,875 --> 00:24:46,127 AUDIENCE: Shift. 550 00:24:46,127 --> 00:24:47,085 PROFESSOR: Shift right. 551 00:24:47,085 --> 00:24:48,830 If the number is a python list? 552 00:24:48,830 --> 00:24:53,449 553 00:24:53,449 --> 00:24:54,240 AUDIENCE: Slice it. 554 00:24:54,240 --> 00:24:55,018 PROFESSOR: Yep. 555 00:24:55,018 --> 00:24:56,730 So kill the last d digits. 556 00:24:56,730 --> 00:24:58,850 So, if I add d digits to the right, 557 00:24:58,850 --> 00:25:00,710 I multiply by 10 to the d. 558 00:25:00,710 --> 00:25:04,290 If I slice the last digits, I divide by 10 to the d. 559 00:25:04,290 --> 00:25:08,690 So this is division, this is multiplication. 560 00:25:08,690 --> 00:25:11,770 And the reason I care about that is this 561 00:25:11,770 --> 00:25:16,894 is going to be an easy division, and whenever I have this, 562 00:25:16,894 --> 00:25:18,060 it's an easy multiplication. 563 00:25:18,060 --> 00:25:21,250 564 00:25:21,250 --> 00:25:24,660 OK, now what function am I going to use? 565 00:25:24,660 --> 00:25:26,570 Does anyone know? 566 00:25:26,570 --> 00:25:32,460 Can I use x minus R over b equals zero? 567 00:25:32,460 --> 00:25:42,771 568 00:25:42,771 --> 00:25:44,750 AUDIENCE: Sure? 569 00:25:44,750 --> 00:25:49,972 PROFESSOR: Well, so, this is f of x. f prime of x is what? 570 00:25:49,972 --> 00:25:51,445 AUDIENCE: Just negative R over b. 571 00:25:51,445 --> 00:25:54,120 Or no, 1. 572 00:25:54,120 --> 00:25:54,770 PROFESSOR: OK. 573 00:25:54,770 --> 00:25:59,142 So, f prime of x over-- 574 00:25:59,142 --> 00:26:00,808 AUDIENCE: I think you switched it again. 575 00:26:00,808 --> 00:26:01,986 [LAUGHTER] 576 00:26:01,986 --> 00:26:02,860 PROFESSOR: Thank you. 577 00:26:02,860 --> 00:26:06,530 Because I was running ahead, and I was like, OK, this works. 578 00:26:06,530 --> 00:26:07,880 Why does it work? 579 00:26:07,880 --> 00:26:12,764 OK, so this is going to be x minus R over b, right? 580 00:26:12,764 --> 00:26:13,680 Can you evaluate this? 581 00:26:13,680 --> 00:26:16,660 582 00:26:16,660 --> 00:26:19,135 If I can't evaluate this, I already know the answer. 583 00:26:19,135 --> 00:26:23,395 584 00:26:23,395 --> 00:26:26,650 AUDIENCE: Your prime's not on the bottom one. 585 00:26:26,650 --> 00:26:29,130 PROFESSOR: So, it's x minus this divided by 1. 586 00:26:29,130 --> 00:26:30,084 So, it's this. 587 00:26:30,084 --> 00:26:32,500 So then, if you're trying to evaluate this far the guesses 588 00:26:32,500 --> 00:26:36,200 that Newton gives you, you can't. 589 00:26:36,200 --> 00:26:38,720 Because if you could, you'd have the answer already. 590 00:26:38,720 --> 00:26:40,340 So we can't use this function. 591 00:26:40,340 --> 00:26:43,010 This is a nice and easy function that doesn't work. 592 00:26:43,010 --> 00:26:45,731 So while I erase the board, one minute, someone 593 00:26:45,731 --> 00:26:46,980 figure out the right function. 594 00:26:46,980 --> 00:27:05,920 595 00:27:05,920 --> 00:27:08,158 Sorry? 596 00:27:08,158 --> 00:27:09,074 AUDIENCE: [INAUDIBLE]. 597 00:27:09,074 --> 00:27:11,080 PROFESSOR: Man, that's hard math. 598 00:27:11,080 --> 00:27:11,990 No, that's too hard. 599 00:27:11,990 --> 00:27:12,656 That's too hard. 600 00:27:12,656 --> 00:27:16,330 601 00:27:16,330 --> 00:27:17,950 OK, let's try this. 602 00:27:17,950 --> 00:27:21,820 Let's try instead of x minus R over b, 603 00:27:21,820 --> 00:27:28,240 let's try this 1/x minus b/R. And the intuition behind this 604 00:27:28,240 --> 00:27:36,391 is if I have to compute b/R, I can do that. 605 00:27:36,391 --> 00:27:36,890 Right? 606 00:27:36,890 --> 00:27:38,450 It's an easy division. 607 00:27:38,450 --> 00:27:42,260 If I somehow get rid of 1/x and all I have to do 608 00:27:42,260 --> 00:27:44,330 is compute b/R, it's an easy division. 609 00:27:44,330 --> 00:27:47,850 610 00:27:47,850 --> 00:27:51,430 Because dividing by 2 to the R by R means 611 00:27:51,430 --> 00:27:54,222 you're going to shift by some digits to the right. 612 00:27:54,222 --> 00:27:56,430 So let's see if the math works out for this function. 613 00:27:56,430 --> 00:28:00,780 614 00:28:00,780 --> 00:28:01,830 What's f prime of x? 615 00:28:01,830 --> 00:28:08,304 616 00:28:08,304 --> 00:28:11,292 AUDIENCE: Negative 1 over x prime? 617 00:28:11,292 --> 00:28:14,280 PROFESSOR: All right. 618 00:28:14,280 --> 00:28:15,510 Like, does no one know it? 619 00:28:15,510 --> 00:28:19,050 At least one student has to know it. 620 00:28:19,050 --> 00:28:25,820 OK, so f of x divided by f prime of x is what? 621 00:28:25,820 --> 00:28:30,850 622 00:28:30,850 --> 00:28:36,900 AUDIENCE: Negative x plus x squared b/R. 623 00:28:36,900 --> 00:28:39,127 PROFESSOR: Plus x squared b R. 624 00:28:39,127 --> 00:28:39,752 AUDIENCE: Yeah. 625 00:28:39,752 --> 00:28:43,289 626 00:28:43,289 --> 00:28:44,330 PROFESSOR: Is this right? 627 00:28:44,330 --> 00:28:50,140 628 00:28:50,140 --> 00:28:52,837 AUDIENCE: Yes. 629 00:28:52,837 --> 00:28:53,420 PROFESSOR: OK. 630 00:28:53,420 --> 00:28:59,890 So if I have my initial guess-- so if I want to get x prime, 631 00:28:59,890 --> 00:29:08,592 x prime is x minus f of x over f prime of x, right? 632 00:29:08,592 --> 00:29:09,400 So, what is it? 633 00:29:09,400 --> 00:29:14,746 634 00:29:14,746 --> 00:29:23,635 AUDIENCE: 2x minus x squared over R. OK. 635 00:29:23,635 --> 00:29:24,612 Did this work? 636 00:29:24,612 --> 00:29:26,320 Did it get rid of all the hard divisions? 637 00:29:26,320 --> 00:29:37,160 638 00:29:37,160 --> 00:29:37,950 [LAUGHS] 639 00:29:37,950 --> 00:29:40,650 Please nod so I know we're good to go. 640 00:29:40,650 --> 00:29:41,710 Tell me if we're not. 641 00:29:41,710 --> 00:29:43,420 So how many divisions did we have here? 642 00:29:43,420 --> 00:29:45,212 One division, this guy, right? 643 00:29:45,212 --> 00:29:46,420 AUDIENCE: But that's a shift. 644 00:29:46,420 --> 00:29:47,503 PROFESSOR: That's a shift. 645 00:29:47,503 --> 00:29:51,120 Because R is 10 to the d. 646 00:29:51,120 --> 00:29:53,602 AUDIENCE: What about the multiplication [INAUDIBLE]? 647 00:29:53,602 --> 00:29:55,560 PROFESSOR: So, we know how to do multiplication 648 00:29:55,560 --> 00:29:58,200 because we learned Karatsuba just now. 649 00:29:58,200 --> 00:29:59,740 So we wanted to get rid of division, 650 00:29:59,740 --> 00:30:01,490 because if you're trying to solve division 651 00:30:01,490 --> 00:30:03,950 by doing division, it's probably not 652 00:30:03,950 --> 00:30:06,800 I'm going to work unless you're doing divide and conquer. 653 00:30:06,800 --> 00:30:14,372 OK, so this is how it works. 654 00:30:14,372 --> 00:30:16,580 I'm not going to run into the error formulas for this 655 00:30:16,580 --> 00:30:19,030 because I want to do another case first. 656 00:30:19,030 --> 00:30:22,110 You can keep going on this and it's in the notes. 657 00:30:22,110 --> 00:30:23,940 The only thing that is useful to remember 658 00:30:23,940 --> 00:30:27,600 is that we use this trick. 659 00:30:27,600 --> 00:30:32,730 So, I want to look at this function, square root 3 of a, 660 00:30:32,730 --> 00:30:36,060 and I want to use Newton to compute it. 661 00:30:36,060 --> 00:30:37,654 So this is the third order root. 662 00:30:37,654 --> 00:30:39,820 It's not the regular square root that we had before. 663 00:30:39,820 --> 00:30:41,530 So we're trying to not be boring and not 664 00:30:41,530 --> 00:30:44,300 just repeat what's in the notes. 665 00:30:44,300 --> 00:30:45,630 How do I do this? 666 00:30:45,630 --> 00:30:48,424 Let's walk through the steps. 667 00:30:48,424 --> 00:30:49,965 So what's the first thing that we do? 668 00:30:49,965 --> 00:30:54,171 669 00:30:54,171 --> 00:30:54,670 Very good. 670 00:30:54,670 --> 00:30:55,419 Look to the right. 671 00:30:55,419 --> 00:30:57,320 Find the first step, and let's put it here. 672 00:30:57,320 --> 00:30:58,280 What's the first step. 673 00:30:58,280 --> 00:31:05,880 674 00:31:05,880 --> 00:31:08,057 AUDIENCE: Function f of 0 at cube root of a. 675 00:31:08,057 --> 00:31:08,640 PROFESSOR: OK. 676 00:31:08,640 --> 00:31:16,640 So we need a function f so that f of-- good. 677 00:31:16,640 --> 00:31:20,070 So before we start writing the actual function, 678 00:31:20,070 --> 00:31:23,740 what if I want to compute cube root 679 00:31:23,740 --> 00:31:27,700 of a up to d digits of precision? 680 00:31:27,700 --> 00:31:29,737 So if I want to compute cube root of 2, 681 00:31:29,737 --> 00:31:31,820 this is going to give me numbers that are below 1. 682 00:31:31,820 --> 00:31:33,236 I have to do with fractions again. 683 00:31:33,236 --> 00:31:34,350 I don't like that. 684 00:31:34,350 --> 00:31:36,470 If I want the digits of precision, what do I do? 685 00:31:36,470 --> 00:31:41,629 686 00:31:41,629 --> 00:31:43,510 AUDIENCE: [INAUDIBLE]. 687 00:31:43,510 --> 00:31:46,340 PROFESSOR: Jumping ahead. 688 00:31:46,340 --> 00:31:46,840 But yeah. 689 00:31:46,840 --> 00:31:49,173 So you have the right answer, but you're speaking slowly 690 00:31:49,173 --> 00:31:51,670 because you're afraid you're going to do a mistake, right? 691 00:31:51,670 --> 00:31:57,010 So, the way to compute this to d digits of precision 10 692 00:31:57,010 --> 00:32:01,650 to the d, right? 693 00:32:01,650 --> 00:32:03,970 This shifts the dot to the right. 694 00:32:03,970 --> 00:32:07,030 So I have to get this 10 to the d inside here, 695 00:32:07,030 --> 00:32:10,590 and I get and to the 3d times a. 696 00:32:10,590 --> 00:32:13,700 Perfect answer, by the way. 697 00:32:13,700 --> 00:32:15,694 Don't forget this 3 here. 698 00:32:15,694 --> 00:32:17,610 If you do, you're going to get something else. 699 00:32:17,610 --> 00:32:20,600 700 00:32:20,600 --> 00:32:24,320 So now I take this guy, and this is the new number 701 00:32:24,320 --> 00:32:26,070 whose cube root I have to compute. 702 00:32:26,070 --> 00:32:27,620 Cube, cube, cube. 703 00:32:27,620 --> 00:32:29,100 OK. 704 00:32:29,100 --> 00:32:31,500 So I can do this in integer land, 705 00:32:31,500 --> 00:32:33,500 and then I'll get an integer result, 706 00:32:33,500 --> 00:32:35,590 and I shift it right by d digits, 707 00:32:35,590 --> 00:32:38,350 and I have a number with d digits of precision. 708 00:32:38,350 --> 00:32:41,730 709 00:32:41,730 --> 00:32:44,520 Does this make sense? 710 00:32:44,520 --> 00:32:45,330 OK, what's f? 711 00:32:45,330 --> 00:32:54,526 712 00:32:54,526 --> 00:32:55,494 AUDIENCE: [INAUDIBLE]. 713 00:32:55,494 --> 00:32:56,702 PROFESSOR: Let's go for that. 714 00:32:56,702 --> 00:32:58,200 Let's see if that works. 715 00:32:58,200 --> 00:32:59,220 x cubed minus a. 716 00:32:59,220 --> 00:33:02,090 717 00:33:02,090 --> 00:33:03,310 Well, let's pretend. 718 00:33:03,310 --> 00:33:06,560 We're going to make this b the new a. 719 00:33:06,560 --> 00:33:09,160 So let's not to worry about this. 720 00:33:09,160 --> 00:33:10,780 This happens somewhere else. 721 00:33:10,780 --> 00:33:12,810 We went through it so that we know 722 00:33:12,810 --> 00:33:14,996 that we know how to deal with it. 723 00:33:14,996 --> 00:33:16,620 And now we're going to forget about it. 724 00:33:16,620 --> 00:33:19,379 So, it's x cubed minus a. 725 00:33:19,379 --> 00:33:21,420 Because we argued that this is an integer, right? 726 00:33:21,420 --> 00:33:23,980 So we don't have to do anything fancy like dividing by R 727 00:33:23,980 --> 00:33:25,960 that we had to do over there. 728 00:33:25,960 --> 00:33:27,740 So, what's f prime of x? 729 00:33:27,740 --> 00:33:34,580 730 00:33:34,580 --> 00:33:35,110 OK. 731 00:33:35,110 --> 00:33:37,005 So, iteration? 732 00:33:37,005 --> 00:33:39,770 733 00:33:39,770 --> 00:33:41,814 How do we iterate? 734 00:33:41,814 --> 00:33:43,690 AUDIENCE: x prime? 735 00:33:43,690 --> 00:33:46,930 PROFESSOR: Let's start with x prime equals 736 00:33:46,930 --> 00:33:51,241 x minus f of x over f prime of x. 737 00:33:51,241 --> 00:33:51,740 Right? 738 00:33:51,740 --> 00:33:53,850 Nice and easy so we have it here. 739 00:33:53,850 --> 00:33:59,380 And this becomes minus copy these two things, right? 740 00:33:59,380 --> 00:34:04,160 x cubed minus a over 3x squared. 741 00:34:04,160 --> 00:34:04,920 OK. 742 00:34:04,920 --> 00:34:08,020 Next thing, I bring this guy under the denominator, 743 00:34:08,020 --> 00:34:16,540 so it's 3x cubed minus x cubed plus a over 3x squared. 744 00:34:16,540 --> 00:34:23,250 So it's 2x cubed plus a over 3x squared. 745 00:34:23,250 --> 00:34:30,082 So this is 2/3 plus-- 746 00:34:30,082 --> 00:34:31,528 AUDIENCE: 2 over 3x. 747 00:34:31,528 --> 00:34:33,456 You keep saying cubed and writing 2. 748 00:34:33,456 --> 00:34:36,830 749 00:34:36,830 --> 00:34:39,650 PROFESSOR: Yeah, that's better. 750 00:34:39,650 --> 00:34:41,170 Thank you. 751 00:34:41,170 --> 00:34:48,900 Plus 1/3 times a over x. 752 00:34:48,900 --> 00:34:51,510 So this one's division. 753 00:34:51,510 --> 00:34:53,364 AUDIENCE: x squared. 754 00:34:53,364 --> 00:34:54,239 PROFESSOR: x squared. 755 00:34:54,239 --> 00:34:55,370 Ouch. 756 00:34:55,370 --> 00:34:56,500 So this guy wants division. 757 00:34:56,500 --> 00:35:00,044 By the time I do this, I better have division ready, right? 758 00:35:00,044 --> 00:35:02,700 759 00:35:02,700 --> 00:35:05,830 OK, so that my iteration. 760 00:35:05,830 --> 00:35:14,097 x prime is 2/3 x plus 1/3 and a over x squared. 761 00:35:14,097 --> 00:35:14,930 What else do I need? 762 00:35:14,930 --> 00:35:22,097 763 00:35:22,097 --> 00:35:23,680 An initial guess would be nice, right? 764 00:35:23,680 --> 00:35:26,830 I can't do this if I don't have the first x. 765 00:35:26,830 --> 00:35:30,894 So let's try to think of a starting x that's reasonable. 766 00:35:30,894 --> 00:35:32,810 The better it is, the faster it's going to be. 767 00:35:32,810 --> 00:35:35,059 So let's try to come up with something reasonable that 768 00:35:35,059 --> 00:35:40,310 doesn't require too much thinking or too much. 769 00:35:40,310 --> 00:35:42,889 AUDIENCE: [INAUDIBLE]. 770 00:35:42,889 --> 00:35:43,930 PROFESSOR: Too much work. 771 00:35:43,930 --> 00:35:45,430 I have to compute a square root. 772 00:35:45,430 --> 00:35:46,564 So what's a? 773 00:35:46,564 --> 00:35:47,480 Let's start with that. 774 00:35:47,480 --> 00:35:48,880 What's an a, right? 775 00:35:48,880 --> 00:35:55,600 So, it's an n digit number. 776 00:35:55,600 --> 00:36:01,410 And say the digits are d1, d2, d3, all the way up to dn. 777 00:36:01,410 --> 00:36:04,950 778 00:36:04,950 --> 00:36:06,930 So what's a good approximation? 779 00:36:06,930 --> 00:36:08,970 Well, the first approximation for this? 780 00:36:08,970 --> 00:36:12,000 781 00:36:12,000 --> 00:36:13,886 AUDIENCE: You get a third as many digits. 782 00:36:13,886 --> 00:36:15,320 PROFESSOR: A third as many digits. 783 00:36:15,320 --> 00:36:15,820 OK. 784 00:36:15,820 --> 00:36:22,830 So something times 10 to the n/3. 785 00:36:22,830 --> 00:36:26,680 786 00:36:26,680 --> 00:36:30,452 Let's say that something is 1, right? 787 00:36:30,452 --> 00:36:31,910 So this is the first approximation. 788 00:36:31,910 --> 00:36:33,326 It's the right order of magnitude. 789 00:36:33,326 --> 00:36:36,280 790 00:36:36,280 --> 00:36:39,204 Do people see why this is a good approximation? 791 00:36:39,204 --> 00:36:40,620 So this number, whatever it is, it 792 00:36:40,620 --> 00:36:50,260 has to be between 1, 0, 0 0, 0, and 1, 0, 0. 793 00:36:50,260 --> 00:36:50,760 OK. 794 00:36:50,760 --> 00:36:52,050 So generally when we do this, what 795 00:36:52,050 --> 00:36:53,620 we have to have in an approximation 796 00:36:53,620 --> 00:36:56,840 is the right order of magnitude And maybe the first digit. 797 00:36:56,840 --> 00:36:58,872 If we can figure out the first digit, 798 00:36:58,872 --> 00:37:00,830 then we're in a good shape, or something really 799 00:37:00,830 --> 00:37:02,516 close to the first digit. 800 00:37:02,516 --> 00:37:03,890 How would we get the first digit? 801 00:37:03,890 --> 00:37:09,370 802 00:37:09,370 --> 00:37:11,020 AUDIENCE: Cube root of the first digit? 803 00:37:11,020 --> 00:37:12,230 PROFESSOR: OK. 804 00:37:12,230 --> 00:37:13,572 Sure. 805 00:37:13,572 --> 00:37:14,530 How do we compute this? 806 00:37:14,530 --> 00:37:18,322 807 00:37:18,322 --> 00:37:19,744 AUDIENCE: Get a formula? 808 00:37:19,744 --> 00:37:20,660 AUDIENCE: [INAUDIBLE]. 809 00:37:20,660 --> 00:37:26,805 810 00:37:26,805 --> 00:37:28,930 PROFESSOR: OK, so I'm not going to argue with that. 811 00:37:28,930 --> 00:37:29,870 AUDIENCE: I like that. 812 00:37:29,870 --> 00:37:33,020 PROFESSOR: So I want to reject the recursive argument first. 813 00:37:33,020 --> 00:37:34,520 So this is going to be small, right? 814 00:37:34,520 --> 00:37:38,130 This is going to be 10 if you're working with digits, 815 00:37:38,130 --> 00:37:41,310 or if you're a computer, maybe it's 256, 816 00:37:41,310 --> 00:37:45,600 or maybe it's 2 to the 16 or 2 to the 32. 817 00:37:45,600 --> 00:37:47,650 Not much bigger than that, right? 818 00:37:47,650 --> 00:37:48,760 Pretty small. 819 00:37:48,760 --> 00:37:53,390 So these algorithms really good for big numbers. 820 00:37:53,390 --> 00:37:55,900 Algorithms that are complicated but have 821 00:37:55,900 --> 00:37:58,930 nice asymptotic complexity are good for big numbers. 822 00:37:58,930 --> 00:38:02,910 They're awful for small numbers, as in they 10 to 100 times 823 00:38:02,910 --> 00:38:04,290 more times to run. 824 00:38:04,290 --> 00:38:07,730 So let's not to do that for this, 825 00:38:07,730 --> 00:38:10,650 because it's like bringing a tank 826 00:38:10,650 --> 00:38:13,690 and shooting it so you can hammer a nail in. 827 00:38:13,690 --> 00:38:15,720 Not the right tool. 828 00:38:15,720 --> 00:38:18,210 So, precomputed list. 829 00:38:18,210 --> 00:38:18,970 I like that. 830 00:38:18,970 --> 00:38:21,261 It's an option, especially if you're [INAUDIBLE] right? 831 00:38:21,261 --> 00:38:23,430 You can use pen and paper to get it. 832 00:38:23,430 --> 00:38:24,900 What if I don't want to do that. 833 00:38:24,900 --> 00:38:26,630 What if my base is more like this.? 834 00:38:26,630 --> 00:38:27,546 AUDIENCE: [INAUDIBLE]. 835 00:38:27,546 --> 00:38:31,259 836 00:38:31,259 --> 00:38:33,050 PROFESSOR: So this is a very good solution. 837 00:38:33,050 --> 00:38:34,726 I'm not arguing with it. 838 00:38:34,726 --> 00:38:38,820 If your power is this or this, by all means, use a table. 839 00:38:38,820 --> 00:38:40,660 So let's see what do we do here? 840 00:38:40,660 --> 00:38:44,048 I just want to think a little bit more. 841 00:38:44,048 --> 00:38:44,964 AUDIENCE: [INAUDIBLE]. 842 00:38:44,964 --> 00:38:51,700 843 00:38:51,700 --> 00:38:53,850 PROFESSOR: OK, so there's some approximation 844 00:38:53,850 --> 00:38:57,300 that comes from math that says that d1 over 3 845 00:38:57,300 --> 00:38:59,150 is not going to be such a bad guess. 846 00:38:59,150 --> 00:39:02,030 Now let's be CS people and do something better. 847 00:39:02,030 --> 00:39:03,726 AUDIENCE: [INAUDIBLE] the exponent. 848 00:39:03,726 --> 00:39:07,239 2 to the 14, divide-- is that 14, right here 849 00:39:07,239 --> 00:39:07,780 AUDIENCE: 16. 850 00:39:07,780 --> 00:39:08,321 AUDIENCE: 16. 851 00:39:08,321 --> 00:39:09,512 Divide 16 by 3. 852 00:39:09,512 --> 00:39:11,220 Or I guess that's not quite right either. 853 00:39:11,220 --> 00:39:14,841 PROFESSOR: So you're saying 2 to the power of, say, 5? 854 00:39:14,841 --> 00:39:17,118 15 over 3? 855 00:39:17,118 --> 00:39:19,400 AUDIENCE: It doesn't seem quite right. 856 00:39:19,400 --> 00:39:21,550 PROFESSOR: So, let's try to do better. 857 00:39:21,550 --> 00:39:22,140 This is math. 858 00:39:22,140 --> 00:39:26,120 Let's just try to do it in a CS way. 859 00:39:26,120 --> 00:39:32,120 So we're trying to guess a digit between 0 and 2 to the 16. 860 00:39:32,120 --> 00:39:36,730 I heard an "oh." 861 00:39:36,730 --> 00:39:38,660 Yes? 862 00:39:38,660 --> 00:39:40,170 You had your hand up? 863 00:39:40,170 --> 00:39:41,400 No? 864 00:39:41,400 --> 00:39:44,155 OK. 865 00:39:44,155 --> 00:39:47,745 AUDIENCE: You take the current time 2 to the 16. 866 00:39:47,745 --> 00:39:50,170 I mean-- 867 00:39:50,170 --> 00:39:52,729 [LAUGHTER] 868 00:39:52,729 --> 00:39:54,270 PROFESSOR: So your algorithm is going 869 00:39:54,270 --> 00:39:56,707 to be fast with some probability, right? 870 00:39:56,707 --> 00:39:57,540 No, that's terrible. 871 00:39:57,540 --> 00:40:00,900 Let's not do that. 872 00:40:00,900 --> 00:40:04,232 Please don't make me grade code like that. 873 00:40:04,232 --> 00:40:06,845 AUDIENCE: Did you already cut out the recursive option? 874 00:40:06,845 --> 00:40:07,428 AUDIENCE: Yes. 875 00:40:07,428 --> 00:40:08,820 PROFESSOR: Yeah. 876 00:40:08,820 --> 00:40:10,957 Well, so I don't want to recurse on square roots. 877 00:40:10,957 --> 00:40:12,790 AUDIENCE: But you could recurse on that one. 878 00:40:12,790 --> 00:40:13,530 PROFESSOR: I mean, if you give me 879 00:40:13,530 --> 00:40:15,250 some algorithm that happens-- 880 00:40:15,250 --> 00:40:18,427 AUDIENCE: You're already [INAUDIBLE]. 881 00:40:18,427 --> 00:40:19,010 PROFESSOR: OK. 882 00:40:19,010 --> 00:40:24,990 883 00:40:24,990 --> 00:40:26,400 So, what's the intuition? 884 00:40:26,400 --> 00:40:28,730 If you have a computer and you have register, 885 00:40:28,730 --> 00:40:29,957 bytes, bits, whatever. 886 00:40:29,957 --> 00:40:31,540 You don't know how to do square roots. 887 00:40:31,540 --> 00:40:38,440 That's not an instruction, but these are all instructions. 888 00:40:38,440 --> 00:40:38,940 Right? 889 00:40:38,940 --> 00:40:43,119 So if I have a guess, say I start with half 890 00:40:43,119 --> 00:40:45,660 and then I get my guess, what do I need for the binary search 891 00:40:45,660 --> 00:40:46,470 to work? 892 00:40:46,470 --> 00:40:48,500 Given a guess that's somewhere here, 893 00:40:48,500 --> 00:40:51,640 I have to be able to say whether this is too small, too big, 894 00:40:51,640 --> 00:40:54,820 or just the right number. 895 00:40:54,820 --> 00:40:58,500 So given a guess, I can multiply it by itself three times, 896 00:40:58,500 --> 00:40:59,000 right? 897 00:40:59,000 --> 00:41:00,400 Compute gets cubed. 898 00:41:00,400 --> 00:41:04,210 And I can see how does it compare to the number 899 00:41:04,210 --> 00:41:04,780 that I want. 900 00:41:04,780 --> 00:41:14,690 901 00:41:14,690 --> 00:41:17,555 So I have the first digit, and I have an order of magnitude. 902 00:41:17,555 --> 00:41:20,740 903 00:41:20,740 --> 00:41:23,330 Not bad, right? 904 00:41:23,330 --> 00:41:25,150 Pretty good initial guess. 905 00:41:25,150 --> 00:41:27,390 This is as much of an answer is you need to give out 906 00:41:27,390 --> 00:41:31,610 in physics problems, and you get full score, so that's good. 907 00:41:31,610 --> 00:41:34,120 908 00:41:34,120 --> 00:41:35,950 OK, how are we doing so far? 909 00:41:35,950 --> 00:41:37,670 Following along? 910 00:41:37,670 --> 00:41:40,892 AUDIENCE: If we compute our guess cubed, 911 00:41:40,892 --> 00:41:43,724 we want only to compare it to our original number 912 00:41:43,724 --> 00:41:44,987 to see how close it is? 913 00:41:44,987 --> 00:41:45,612 PROFESSOR: Yup. 914 00:41:45,612 --> 00:41:49,337 AUDIENCE: And, do we just keep on doing that until-- 915 00:41:49,337 --> 00:41:51,920 PROFESSOR: Well, so you're going have to guess a digit, right? 916 00:41:51,920 --> 00:41:54,000 Between 0 and 2 to the 16. 917 00:41:54,000 --> 00:41:58,120 So you choose the largest thing that's smaller than your guess, 918 00:41:58,120 --> 00:41:58,760 or something. 919 00:41:58,760 --> 00:42:00,760 AUDIENCE: Or until we get the first digit. 920 00:42:00,760 --> 00:42:00,794 PROFESSOR: Yeah. 921 00:42:00,794 --> 00:42:01,505 Just the first. 922 00:42:01,505 --> 00:42:03,380 And then you have a first digit, and then you 923 00:42:03,380 --> 00:42:04,705 have an order of magnitude. 924 00:42:04,705 --> 00:42:06,080 And then you feed that to Newton, 925 00:42:06,080 --> 00:42:07,275 which converges way faster. 926 00:42:07,275 --> 00:42:09,805 927 00:42:09,805 --> 00:42:11,930 So you could the binary search for the whole thing, 928 00:42:11,930 --> 00:42:14,640 but that would be slower than Newton, turns out. 929 00:42:14,640 --> 00:42:15,740 Yes? 930 00:42:15,740 --> 00:42:18,900 AUDIENCE: So where'd you get the f of x here? 931 00:42:18,900 --> 00:42:20,320 I'm missing that stuff. 932 00:42:20,320 --> 00:42:21,000 PROFESSOR: Oh. 933 00:42:21,000 --> 00:42:22,760 AUDIENCE: Yeah, right there. 934 00:42:22,760 --> 00:42:26,550 PROFESSOR: Someone told me to use this. 935 00:42:26,550 --> 00:42:29,540 [LAUGHTER] 936 00:42:29,540 --> 00:42:33,710 One of you guys told me to use this. 937 00:42:33,710 --> 00:42:34,780 Well, so I tried it out. 938 00:42:34,780 --> 00:42:36,040 I put it here. 939 00:42:36,040 --> 00:42:38,110 And then I computed the derivative, 940 00:42:38,110 --> 00:42:40,747 and I looked to see if this looks reasonable. 941 00:42:40,747 --> 00:42:42,580 And this looks like something I can compute. 942 00:42:42,580 --> 00:42:44,550 AUDIENCE: And why was that reasonable? 943 00:42:44,550 --> 00:42:46,150 PROFESSOR: Because I know how to do the division 944 00:42:46,150 --> 00:42:46,941 and multiplication. 945 00:42:46,941 --> 00:42:49,870 946 00:42:49,870 --> 00:42:52,890 So, say if I would have had the square root of 3 in here, 947 00:42:52,890 --> 00:42:55,700 that wouldn't be reasonable, right? 948 00:42:55,700 --> 00:42:56,440 Just like before. 949 00:42:56,440 --> 00:42:58,065 When you're trying to compute division, 950 00:42:58,065 --> 00:42:59,317 we can't have division. 951 00:42:59,317 --> 00:43:00,900 If you're trying to compute sine of x, 952 00:43:00,900 --> 00:43:03,720 you don't want to have sine of x. 953 00:43:03,720 --> 00:43:04,570 AUDIENCE: OK. 954 00:43:04,570 --> 00:43:08,120 and computing a over x squared is reasonable? 955 00:43:08,120 --> 00:43:09,659 PROFESSOR: Because we did it before. 956 00:43:09,659 --> 00:43:10,200 AUDIENCE: OK. 957 00:43:10,200 --> 00:43:11,820 So then you might use something else, maybe? 958 00:43:11,820 --> 00:43:12,390 PROFESSOR: Yeah. 959 00:43:12,390 --> 00:43:14,730 You can use something else as long as you know how to do it, 960 00:43:14,730 --> 00:43:16,230 and as long as it's reasonably fast. 961 00:43:16,230 --> 00:43:17,976 AUDIENCE: OK. 962 00:43:17,976 --> 00:43:18,600 PROFESSOR: Yes? 963 00:43:18,600 --> 00:43:19,516 AUDIENCE: [INAUDIBLE]. 964 00:43:19,516 --> 00:43:24,650 965 00:43:24,650 --> 00:43:25,900 PROFESSOR: Oh, no that's fine. 966 00:43:25,900 --> 00:43:27,210 AUDIENCE: Oh, that fine? 967 00:43:27,210 --> 00:43:27,752 OK. 968 00:43:27,752 --> 00:43:29,210 PROFESSOR: So, the binary search is 969 00:43:29,210 --> 00:43:30,840 fine to get the first approximation. 970 00:43:30,840 --> 00:43:32,290 But after that-- so I'm not going 971 00:43:32,290 --> 00:43:35,140 to do a binary search for the whole result, 972 00:43:35,140 --> 00:43:38,240 because Newton is faster than that. 973 00:43:38,240 --> 00:43:40,520 I'm just using this so that I have a decent guess 974 00:43:40,520 --> 00:43:42,110 to pass to Newton. 975 00:43:42,110 --> 00:43:46,960 And we'll see why we need that decent guess in two minutes 976 00:43:46,960 --> 00:43:48,495 total. 977 00:43:48,495 --> 00:43:50,620 So I'm going to try to spend two minutes to explain 978 00:43:50,620 --> 00:43:52,830 how the error thing works, and you'll 979 00:43:52,830 --> 00:43:55,060 have to look at the notes and make sense out 980 00:43:55,060 --> 00:43:58,130 of the rest of it. 981 00:43:58,130 --> 00:43:59,345 So, let's see. 982 00:43:59,345 --> 00:43:59,845 Errors. 983 00:43:59,845 --> 00:44:07,360 984 00:44:07,360 --> 00:44:10,260 So with Newton, you start to with an initial guess, 985 00:44:10,260 --> 00:44:12,570 and then you get to a better guess, and a better 986 00:44:12,570 --> 00:44:16,220 guess, and a better guess, and so on and so forth 987 00:44:16,220 --> 00:44:17,535 until you're satisfied. 988 00:44:17,535 --> 00:44:19,785 By the way, if we're doing this one, are we satisfied? 989 00:44:19,785 --> 00:44:23,790 990 00:44:23,790 --> 00:44:25,956 AUDIENCE: What do you mean, like, finding the guess? 991 00:44:25,956 --> 00:44:26,680 Are we satisfied? 992 00:44:26,680 --> 00:44:27,430 PROFESSOR: Oh, no. 993 00:44:27,430 --> 00:44:28,790 So, we have the initial guess. 994 00:44:28,790 --> 00:44:33,280 And we keep applying the formula that I just deleted to iterate. 995 00:44:33,280 --> 00:44:34,400 When do we stop? 996 00:44:34,400 --> 00:44:36,670 AUDIENCE: When we have enough digits of precision? 997 00:44:36,670 --> 00:44:38,660 PROFESSOR: So how do we know when we have enough digits, 998 00:44:38,660 --> 00:44:39,950 if we're working with integers? 999 00:44:39,950 --> 00:44:41,910 AUDIENCE: We iterate again and nothing changes. 1000 00:44:41,910 --> 00:44:44,010 PROFESSOR: We iterate again and nothing changes. 1001 00:44:44,010 --> 00:44:47,892 So I'm computing-- do I have this anywhere? 1002 00:44:47,892 --> 00:44:49,030 Oh, no. 1003 00:44:49,030 --> 00:44:50,180 I erased it. 1004 00:44:50,180 --> 00:44:54,140 So I'm computing 10 t0 some-- oh, I had it up here. 1005 00:44:54,140 --> 00:44:55,730 So, I'm computing 10 to the power 1006 00:44:55,730 --> 00:44:59,630 of d times a square root of 3, because I 1007 00:44:59,630 --> 00:45:00,800 want to work with integers. 1008 00:45:00,800 --> 00:45:03,730 Just integers. 1009 00:45:03,730 --> 00:45:04,810 I used Newton to iterate. 1010 00:45:04,810 --> 00:45:08,250 My precision gets gets better and better and better. 1011 00:45:08,250 --> 00:45:09,150 And I use integers. 1012 00:45:09,150 --> 00:45:10,860 So I only have d digits of precision. 1013 00:45:10,860 --> 00:45:14,510 Everything after that gets discarded automatically. 1014 00:45:14,510 --> 00:45:17,516 When I get 2 x's that don't change-- so if I get x5, 1015 00:45:17,516 --> 00:45:18,890 and then I run the thing and then 1016 00:45:18,890 --> 00:45:22,530 I get x6 that is equal to x5, there's 1017 00:45:22,530 --> 00:45:24,520 no point to keep running Newton, right? 1018 00:45:24,520 --> 00:45:25,109 I;m stuck. 1019 00:45:25,109 --> 00:45:26,900 And I'm also done because I have the answer 1020 00:45:26,900 --> 00:45:28,650 with d digits of precision. 1021 00:45:28,650 --> 00:45:30,262 So this is where I stop. 1022 00:45:30,262 --> 00:45:34,231 1023 00:45:34,231 --> 00:45:34,730 OK. 1024 00:45:34,730 --> 00:45:38,390 Now, my precision is how far I am from the right answer. 1025 00:45:38,390 --> 00:45:40,750 And we write that by saying that x1 1026 00:45:40,750 --> 00:45:47,770 is x, the true answer, times 1 plus epsilon, epsilon 1. 1027 00:45:47,770 --> 00:45:55,120 And then x2 is x times 1 plus epsilon 2, 1 plus epsilon 3, 1028 00:45:55,120 --> 00:45:58,480 so on and so forth. 1029 00:45:58,480 --> 00:45:59,040 Right? 1030 00:45:59,040 --> 00:46:03,670 So, if we had a lot of time and not too much stuff to do, 1031 00:46:03,670 --> 00:46:06,830 I could copy this thing here that we have in the notes. 1032 00:46:06,830 --> 00:46:09,210 That's eight lines of math. 1033 00:46:09,210 --> 00:46:15,920 And then we'd get something along the lines of x of i 1034 00:46:15,920 --> 00:46:24,460 plus 1 is x times 1 plus something times E 1035 00:46:24,460 --> 00:46:31,840 squared-- I'm sorry, Ei squared. 1036 00:46:31,840 --> 00:46:40,100 So this is also 1 plus Ei plus 1. 1037 00:46:40,100 --> 00:46:47,220 So what we get is that E of i plus 1 is roughly E i squared. 1038 00:46:47,220 --> 00:46:52,620 1039 00:46:52,620 --> 00:46:57,810 And this is what's really called quadratic convergence. 1040 00:46:57,810 --> 00:46:59,690 Now why is this good? 1041 00:46:59,690 --> 00:47:02,920 Can anyone think intuitively why this is nice? 1042 00:47:02,920 --> 00:47:03,660 In which cases? 1043 00:47:03,660 --> 00:47:04,580 Yes? 1044 00:47:04,580 --> 00:47:07,150 AUDIENCE: You're converging really quickly to your answer. 1045 00:47:07,150 --> 00:47:08,100 PROFESSOR: OK. 1046 00:47:08,100 --> 00:47:10,405 But when do I converge? 1047 00:47:10,405 --> 00:47:12,257 , So what I want this to happen? 1048 00:47:12,257 --> 00:47:13,340 What do I want this to be? 1049 00:47:13,340 --> 00:47:14,256 AUDIENCE: [INAUDIBLE]. 1050 00:47:14,256 --> 00:47:17,197 1051 00:47:17,197 --> 00:47:19,030 PROFESSOR: Well, you guys told me everything 1052 00:47:19,030 --> 00:47:21,600 I need for the next two minutes. 1053 00:47:21,600 --> 00:47:25,880 So, I want this to become 1, right? 1054 00:47:25,880 --> 00:47:31,170 This has to go to 1 because I want this whole thing to be x. 1055 00:47:31,170 --> 00:47:35,740 So in order for this to be 1, I want to epsilons to go to 0. 1056 00:47:35,740 --> 00:47:38,140 So I want them to be as small as possible. 1057 00:47:38,140 --> 00:47:42,470 Now, you said that if my epsilon is smaller than 1, 1058 00:47:42,470 --> 00:47:48,400 then epsilon squared is smaller than epsilon. 1059 00:47:48,400 --> 00:47:50,940 And intuitively, how this works is, 1060 00:47:50,940 --> 00:47:54,160 suppose you start with an epsilon of 0.1. 1061 00:47:54,160 --> 00:47:58,290 When you square it, you get 0.01. 1062 00:47:58,290 --> 00:48:02,260 You square it again, you get 0.0001. 1063 00:48:02,260 --> 00:48:03,080 Square it again. 1064 00:48:03,080 --> 00:48:08,700 0.00000001. 1065 00:48:08,700 --> 00:48:09,200 OK. 1066 00:48:09,200 --> 00:48:12,330 This is step 0, step 1, step 2, step 3. 1067 00:48:12,330 --> 00:48:13,980 How many digits do I have here? 1068 00:48:13,980 --> 00:48:18,240 1069 00:48:18,240 --> 00:48:20,698 Don't be shy. 1070 00:48:20,698 --> 00:48:22,180 AUDIENCE: 2 to the i? 1071 00:48:22,180 --> 00:48:22,810 PROFESSOR: Yup. 1072 00:48:22,810 --> 00:48:23,675 2 to the i. 1073 00:48:23,675 --> 00:48:28,700 1074 00:48:28,700 --> 00:48:31,460 So this is going to be equal to this 1075 00:48:31,460 --> 00:48:40,220 when 1 plus x times 1 plus epsilon i over 1 plus epsilon-- 1076 00:48:40,220 --> 00:48:48,020 sorry, i plus 1 epsilon i when the floor of this thing 1077 00:48:48,020 --> 00:48:53,800 is-- sorry, there is a delta somewhere here. 1078 00:48:53,800 --> 00:48:57,210 So, something has to converge to 0. 1079 00:48:57,210 --> 00:49:00,330 1080 00:49:00,330 --> 00:49:03,210 Sorry, this is what it is. 1081 00:49:03,210 --> 00:49:06,110 1 plus e of i. 1082 00:49:06,110 --> 00:49:10,210 1083 00:49:10,210 --> 00:49:14,310 So this is the difference between two terms, x. 1084 00:49:14,310 --> 00:49:16,737 So this is x6 minus x5, right? 1085 00:49:16,737 --> 00:49:20,850 1086 00:49:20,850 --> 00:49:23,332 Convincing? 1087 00:49:23,332 --> 00:49:24,770 AUDIENCE: [INAUDIBLE]. 1088 00:49:24,770 --> 00:49:25,979 Let's write it again. 1089 00:49:25,979 --> 00:49:26,854 Let's write it again. 1090 00:49:26,854 --> 00:49:27,687 This is out of hand. 1091 00:49:27,687 --> 00:49:30,380 So, x, x minus x5, or actually, xi 1092 00:49:30,380 --> 00:49:37,900 plus 1 minus xi is equal to x times 1 plus epsilon i 1093 00:49:37,900 --> 00:49:43,390 plus 1 minus x times 1 plus epsilon i, right? 1094 00:49:43,390 --> 00:49:48,639 So this is x times-- Sorry? 1095 00:49:48,639 --> 00:49:50,046 AUDIENCE: Those are xi, x of i. 1096 00:49:50,046 --> 00:49:53,700 AUDIENCE: No, those are the real x's. 1097 00:49:53,700 --> 00:49:56,920 PROFESSOR: These are-- so these are the approximations, 1098 00:49:56,920 --> 00:49:59,154 but then, this is the real x. 1099 00:49:59,154 --> 00:50:00,570 AUDIENCE: I understand, thank you. 1100 00:50:00,570 --> 00:50:01,153 PROFESSOR: OK. 1101 00:50:01,153 --> 00:50:04,610 So, this is, the difference between them is this guy here. 1102 00:50:04,610 --> 00:50:12,430 So if I take the floor because I work with integers, 1103 00:50:12,430 --> 00:50:16,700 when this floor becomes 0, we're done, right? 1104 00:50:16,700 --> 00:50:18,970 So in order for the floor to become 0, 1105 00:50:18,970 --> 00:50:23,400 this guy has to be canceled by this guy. 1106 00:50:23,400 --> 00:50:27,300 So this guy has some number of digits, whatever that is. 1107 00:50:27,300 --> 00:50:31,260 It's my number with d digits of precision. 1108 00:50:31,260 --> 00:50:35,980 Well, that's OK because-- where my 0s? 1109 00:50:35,980 --> 00:50:36,790 Did I erase my 0s? 1110 00:50:36,790 --> 00:50:37,590 Oh, no. 1111 00:50:37,590 --> 00:50:39,940 I have 0s here, right? 1112 00:50:39,940 --> 00:50:41,740 The epsilons have a lot of 0s in them, 1113 00:50:41,740 --> 00:50:46,110 so the 0s are going to cancel the digits in x. 1114 00:50:46,110 --> 00:50:53,180 So as soon as I have enough 0s here to cancel this, I'm stuck. 1115 00:50:53,180 --> 00:50:59,040 The number of 0s increases exponentially. 1116 00:50:59,040 --> 00:51:02,310 So in each step the number of 0s I have doubles. 1117 00:51:02,310 --> 00:51:06,880 So after log d steps, I'm done. 1118 00:51:06,880 --> 00:51:09,700 If I have d digits in here, because I'm 1119 00:51:09,700 --> 00:51:12,190 computing this with d digits of precision, 1120 00:51:12,190 --> 00:51:15,650 after roughly log d steps, I'll have enough 0s here 1121 00:51:15,650 --> 00:51:17,750 to reduce this and make the whole thing be 0. 1122 00:51:17,750 --> 00:51:20,770 1123 00:51:20,770 --> 00:51:23,420 So this is how I know that it's fast. 1124 00:51:23,420 --> 00:51:27,730 So in the end, what you want is the initial guess 1125 00:51:27,730 --> 00:51:30,440 has to satisfy this, and then you 1126 00:51:30,440 --> 00:51:36,660 want to be able to prove that this is true. 1127 00:51:36,660 --> 00:51:39,130 So you want this factor here that tells you you're 1128 00:51:39,130 --> 00:51:40,900 converging fast. 1129 00:51:40,900 --> 00:51:43,280 So when you look at the recitation notes 1130 00:51:43,280 --> 00:51:46,374 and you look at this long string of equations, 1131 00:51:46,374 --> 00:51:47,790 make sure this is somewhere there, 1132 00:51:47,790 --> 00:51:50,631 because this means you're on the right track. 1133 00:51:50,631 --> 00:51:51,480 Yes? 1134 00:51:51,480 --> 00:51:52,941 AUDIENCE: If it takes log d steps, 1135 00:51:52,941 --> 00:51:56,960 doesn't the binary search also take log-- ah, OK. 1136 00:51:56,960 --> 00:51:57,930 Log 10 steps. 1137 00:51:57,930 --> 00:51:58,430 Got it. 1138 00:51:58,430 --> 00:51:59,030 PROFESSOR: Yeah. 1139 00:51:59,030 --> 00:51:59,560 Which is d. 1140 00:51:59,560 --> 00:52:02,317 1141 00:52:02,317 --> 00:52:04,150 AUDIENCE: He's talking about binary search-- 1142 00:52:04,150 --> 00:52:05,250 PROFESSOR: Oh, for one digit. 1143 00:52:05,250 --> 00:52:05,540 Yeah. 1144 00:52:05,540 --> 00:52:06,040 Oh, sorry. 1145 00:52:06,040 --> 00:52:07,710 I thought you meant for the whole thing. 1146 00:52:07,710 --> 00:52:11,020 So if you wanted to do binary search for the whole thing, 1147 00:52:11,020 --> 00:52:13,200 that's log of the whole number. 1148 00:52:13,200 --> 00:52:15,420 So that's order d where d is the number of digits. 1149 00:52:15,420 --> 00:52:18,260 1150 00:52:18,260 --> 00:52:20,622 AUDIENCE: Wait, he's talking about a binary [INAUDIBLE]. 1151 00:52:20,622 --> 00:52:22,350 AUDIENCE: [INAUDIBLE]. 1152 00:52:22,350 --> 00:52:26,720 AUDIENCE: [INAUDIBLE] wants to go for [INAUDIBLE], 10 1153 00:52:26,720 --> 00:52:28,060 to the 20th. 1154 00:52:28,060 --> 00:52:30,490 He wants to do a binary search over like a cube root-- 1155 00:52:30,490 --> 00:52:31,630 PROFESSOR: So, for this? 1156 00:52:31,630 --> 00:52:33,310 Binary search for this or for one digit? 1157 00:52:33,310 --> 00:52:36,005 Or binary search to compute the cube root? 1158 00:52:36,005 --> 00:52:37,030 AUDIENCE: I think, yeah. 1159 00:52:37,030 --> 00:52:39,630 PROFESSOR: So, if you do that, your entire thing is 1160 00:52:39,630 --> 00:52:40,980 d digits, right? 1161 00:52:40,980 --> 00:52:42,861 So 10 to the d. 1162 00:52:42,861 --> 00:52:45,610 Binary search takes log of 10 to the d. 1163 00:52:45,610 --> 00:52:48,070 AUDIENCE: Right, yeah. 1164 00:52:48,070 --> 00:52:49,570 PROFESSOR: So the numbers that we're 1165 00:52:49,570 --> 00:52:51,690 dealing with are d digits. 1166 00:52:51,690 --> 00:52:53,930 So this d is the number of digits, not the number 1167 00:52:53,930 --> 00:52:54,919 that you have. 1168 00:52:54,919 --> 00:52:56,710 So if you look at the number that you have, 1169 00:52:56,710 --> 00:52:58,125 this is log log n. 1170 00:52:58,125 --> 00:53:00,228 AUDIENCE: Right, that makes sense. 1171 00:53:00,228 --> 00:53:00,728 Sorry. 1172 00:53:00,728 --> 00:53:02,632 PROFESSOR: So, it's faster. 1173 00:53:02,632 --> 00:53:03,590 AUDIENCE: I like it. 1174 00:53:03,590 --> 00:53:04,507 It is faster. 1175 00:53:04,507 --> 00:53:05,090 PROFESSOR: OK. 1176 00:53:05,090 --> 00:53:05,390 Cool. 1177 00:53:05,390 --> 00:53:06,306 Thanks for the lesson. 1178 00:53:06,306 --> 00:53:07,840 AUDIENCE: [INAUDIBLE].