WEBVTT 00:00.150 --> 00:04.890 Hello again! In this video, we are going to continue looking at further numerical algorithms. 00:05.910 --> 00:08.850 We are going to look at the inner_product algorithm in more depth. 00:09.390 --> 00:12.810 So, to remind ourselves, this takes two ranges of iterators. 00:13.320 --> 00:18.640 It multiplies together corresponding elements from each iterator range, and then it adds them all up, and 00:18.640 --> 00:20.670 it adds them to this initial value of the sum. 00:23.250 --> 00:26.790 This can actually be written as two separate algorithm calls. 00:27.300 --> 00:33.000 We could have a call to transform() which does the multiplication and a call to accumulate(), which adds 00:33.000 --> 00:35.910 up the results of the multiplications. 00:37.200 --> 00:41.940 So we would have this transform() call, which takes the two containers as the input range. 00:42.570 --> 00:44.940 It has a temporary vector as the destination. 00:45.360 --> 00:49.250 And then it calls the library function object, "multiplies" for int. 00:49.590 --> 00:51.390 So we need to pass an object of that. 00:52.560 --> 00:58.290 And then the accumulate() call will take this temporary vector as the iterator range, initial value 00:58.290 --> 01:02.490 zero, and it will use the library function object "plus" to add them up. 01:05.300 --> 01:12.290 And, just to show they give the same result, here is the code that we had for inner_product() before, and 01:12.290 --> 01:15.950 then we are going to write this as a call to transform() and accumulate(). 01:17.390 --> 01:18.980 So let's see if we get the same answers. 01:20.710 --> 01:21.700 And yes, we do. 01:25.430 --> 01:28.790 If we want to overload inner_product(), we actually have two possibilities. 01:29.180 --> 01:32.330 We can overload the addition and the multiplication. 01:33.080 --> 01:37.220 We can replace the multiplication step by some kind of transform operation. 01:37.760 --> 01:43.700 So this will take two arguments of the element type, and combine them, and return a value of some return 01:43.700 --> 01:44.030 type. 01:45.320 --> 01:48.320 This will usually be the same type as the elements, but it does not have to be. 01:48.710 --> 01:53.270 For example, we could have two vectors of real numbers and we could return a complex number. 01:57.050 --> 02:00.470 We can also replace the addition by some kind of "accumulate" operation. 02:01.100 --> 02:07.000 So this will take two arguments, of the returned type from this operation, and it will return a value of 02:07.010 --> 02:08.210 the result type. 02:08.420 --> 02:10.850 Again, this can be a different type from the one it was given. 02:11.630 --> 02:17.840 So this will collect up all the results of these transformations, and reduce them down to a single final 02:17.840 --> 02:18.290 result. 02:18.710 --> 02:20.990 So this is sometimes called a "reduce" operation. 02:24.590 --> 02:28.580 As an example of this, let's imagine that we have conducted a scientific experiment. 02:28.880 --> 02:31.330 We have our results and we have stored them in a vector. 02:32.090 --> 02:36.800 We have also calculated the results we expected to get, according to theory, and we have those in another 02:36.800 --> 02:40.370 vector and we want to find out how accurate our results are. 02:40.400 --> 02:46.520 Or if you prefer, how accurate the theory is! So we want to find the biggest error in the results. 02:47.000 --> 02:52.640 So that means the maximum difference between one of our results and the expected theoretical result. 02:55.060 --> 03:00.700 And we can do that by using inner_product(). We can have a transform operation, which will find the differences 03:00.700 --> 03:07.840 between elements in the two vectors, and then a "reduce" or "accumulate" operation, which will go through 03:07.840 --> 03:10.240 all those differences and pick out the biggest one. 03:11.200 --> 03:13.870 And then the result of that will be the maximum error in the data. 03:16.970 --> 03:21.680 So we need to replace the multiplication by some function, which will find the difference between the 03:21.680 --> 03:27.350 corresponding elements, and we need to replace addition by something that finds the largest difference. 03:29.450 --> 03:35.900 And by the way, I found this on a blog, so credit to the original author. So when we overload 03:35.900 --> 03:38.270 innre_product(), we add two extra arguments. 03:38.270 --> 03:43.850 The first one is the replacement for the reduce operation, and the second one is the replacement for 03:43.850 --> 03:45.260 the transform operation. 03:47.640 --> 03:51.330 So, our transform operation is going to be called with one element from each vector. 03:52.140 --> 03:57.750 We want to find the difference, so we subtract them, and then we want to ignore the of this result, 03:57.770 --> 04:00.720 so we use fabs(), which will return the absolute value. 04:02.840 --> 04:07.830 The reduce operation is going to be called with two of these differences as arguments, and we want to 04:07.850 --> 04:11.510 find the biggest one so we can just use the library max() function for that. 04:14.610 --> 04:20.190 So here is that code, we have our vector with the theoretical predictions, the nice straight line. 04:21.210 --> 04:25.200 And then another vector with our actual results, which is pretty close, actually. 04:27.090 --> 04:31.710 So here is our call to inner_product(). We give those two vectors as the input ranges. 04:32.370 --> 04:37.020 We have zero as the starting value, because we want to find a difference that is bigger than 0. 04:39.000 --> 04:42.610 We have this function, which is going to be called with one element from each vector. 04:43.080 --> 04:45.450 And it is going to return the difference, ignoring sign. 04:47.250 --> 04:52.110 Then we have this function, which would be called with two of these differences as arguments, and 04:52.110 --> 04:53.490 we return the biggest one. 04:54.510 --> 04:56.520 So let's find out what the biggest difference is. 04:57.990 --> 05:00.090 And the answer is 0.03. 05:01.260 --> 05:06.990 So let's check this. So that is 0.01, 0.02, 0.03, 0.01, 0.02. 05:07.290 --> 05:09.810 So yes, that is the biggest discrepancy. 05:10.710 --> 05:11.520 So that is correct. 05:12.450 --> 05:15.300 If you have done parallel programming, this may seem a bit familiar. 05:15.660 --> 05:17.130 This is actually quite a common pattern. 05:17.640 --> 05:22.920 So if you have a problem which involves a large calculation, sometimes you can break it down into smaller 05:22.920 --> 05:25.770 calculations, which are independent of each other. 05:26.520 --> 05:30.540 So you do not need to wait for one part to complete before you can do the next. 05:31.680 --> 05:36.580 And if that is the case, you can perform each of these sub-calculations on its own processor core, 05:36.580 --> 05:38.280 so they can all be done concurrently. 05:39.120 --> 05:43.620 And then you combine together the results of these sub-calculations, and that will give you the final 05:43.920 --> 05:44.410 result, 05:44.430 --> 05:45.780 the answer to your calculation. 05:47.370 --> 05:51.570 So we could do this with inner_product(), with transform() and accumulate(). 05:53.550 --> 05:59.220 Unfortunately, as we saw when we looked at the accumulates algorithm function, it is not really suitable 05:59.220 --> 06:00.390 for parallel processing. 06:01.350 --> 06:05.760 C++ 17 has a new algorithm function, transform_reduce(). 06:06.780 --> 06:11.850 This is exactly the same as inner_product, except it uses reduce() instead of accumulate(). 06:12.360 --> 06:17.070 And as we saw when we discussed accumulate(), reduce() is compatible with parallel processing. 06:17.640 --> 06:23.180 So this can give much better results than using inner_product() for this kind of programming idiom. 06:25.150 --> 06:26.620 OK, so that is it for this video. 06:27.040 --> 06:27.880 I will see you next time. 06:28.180 --> 06:29.950 Meanwhile, keep coding!