1.5 Example, square roots with Newton's method Functional Programming Principles in Scala English French

1.5 Example, square roots with Newton's methodYouTube↗ IA↗(long shot)
Education 843 views 2 likes 1 dislikes 11 Sep 2017

Functional Programming Principles in Scala 1.3K subscribers N/A YouTube↗

Click to Play Video

In this session, we are going to apply what we learned so far in a larger

Dans cette session, nous allons appliquer ce que nous avons appris jusqu'à présent dans un plus grand

example. The task is to develop a square root

exemple. La tâche consiste à développer une fonction pour calculer

function using Newton's method. That's the first time that we need more

la racine carrée à l'aide de la méthode de Newton. C'est la première fois que nous avons besoin de plus

than a couple of lines to actually express a program and we will learn new techniques

de quelques lignes pour exprimer en fait un programme et nous allons apprendre de nouvelles techniques

and new tools for doing so. So, what that means is that we want to

et de nouveaux outils pour le faire. Donc, ce que cela signifie, c'est que nous voulons

define a function with the signature. It takes a double and gives me back a

définir une fonction avec la signature suivante. Elle prend un double x et me donne un double en retour

double, and return the value is the square root of its parameter x.

et la valeur de retour est la racine carrée du paramètre x.

The classical way to compute that is by successive approximations using the method

La façon classique de calculer ceci est en utilisant la méthode des approximations successives

of Isaac Newton. So, let's see what this method is.

d'Isaac Newton. Donc, nous allons voir ce qu'est cette méthode.

To compute square root of x, we start with an initial estimate value.

Pour calculer la racine carrée de x, nous commençons avec une valeur quelconque pour l'estimation initiale.

It doesn't really matter what that estimate is as long as it's positive.

Peu importe ce que c'est tant qu'elle est positive.

So, let's pick y = one. And then, we repeatedly improve the

Donc, nous allons choisir y = 1. Et puis, nous améliorons constamment

estimate by taking the mean of the old estimate y and the value of x divided by

l'estimation en prenant la moyenne de l'ancienne estimation y et la valeur de x divisé par

y, where x is the value we want to draw the root from.

y, où x est la valeur dont nous voulons prendre la racine.

So, it's, let's see that in action. For the value of x, in our example, would

Ainsi, nous allons voir cela en action. Pour la valeur de x, dans notre exemple, ce serait

be two. Our initial estimation is one, as usual,

deux. Notre estimation initiale est, comme d'habitude,

so the initial quotient is two divided by one, that's two, the mean is 1.5.

alors le quotient initial est de deux, divisée par 1, c'est deux, la moyenne est de 1,5.

Now, we plug in 1.5 to our estimation, we get a new quotient of 1.33, a new mean

Maintenant, nous mettons 1.5 comme notre estimation, nous obtenons un nouveau quotient de 1,33, une nouvelle moyenne

that you'd see here and you'll see that it converges very quickly to the actual value

que vous verriez ici et vous verrez qu'il converge très rapidement à la valeur réelle

of two. So now, we have an abstract algorithm.

de deux. Alors maintenant, nous avons un algorithme abstrait.

Let's see how we would put that into a function that computes that algorithm.

Nous allons voir comment implémenter une fonction qui calcule cet algorithme.

A typical way to code algorithms in functional languages is to go step by

Une façon de procéder des algorithmes de code dans les langages fonctionnels est d'aller étape par

step. So, we take a small task and formulate it

étape. Donc, nous prenons une petite tâche que nous formulons

as a function and then probably, that task will need further tasks that then would be

en fonction et, probablement, cette tâche aura besoin davantage les tâches qui seraient ensuite

defined in their own function. The first function we want to define is

définie en leur propre fonction. La première fonction que nous voulons définir est

the actual iteration called the square root Iter, which says, well, if you have a

l'itération actuelle appellé square root Iter, qui dit : Et bien, si vous avez une

guess and the value would be one to draw the root from, what do we do?

estimation et la valeur dont on veut une racine carré, que faisons-nous ?

Well, either we stop the iteration and return the result or we go and do another

Et bien, nous arrêtons l'itération et retournent le résultat ou nous allons encore dans une

iteration step. The predicate that controls that we give

étape de l'itération. Le prédicat qui contrôle cela a besoin d'un nom

it a name, let's call it, isGoodEnough. So, if my guess is good enough, then I

appelons-le, isGoodEnough. Donc, si ma conjecture est assez bonne, alors je

just can return the guess. If my guess is not yet good enough, then I

peut juste retourner l'estimation. Si ma conjecture n'est pas encore bien assez, alors je

have to improve my guess. Let's do that with another function in

peut améliorer ma conjecture. Nous allons le faire avec une autre fonction,

prove and call, square root Iter again with the improved guess.

et appelez, racine carrée Iter à nouveau avec l'estimation améliorée.

Note that square root Iter is recursive so its right-hand side calls itself.

Notez que Iter est récursive, que cette fonction s'appelle dans son côté droit.

One peculiarity in Scala is that the return type of a recursive function needs

Une particularité dans Scala est que le type de retour d'une fonction récursive doit être déclaré

to be given always whereas, for other functions, it's optional.

alors que, pour d'autres fonctions, il est facultatif.

The reason for that is that to compute that return type, the Scala compiler would

La raison en est que pour calculer ce que retourne le type, le compilateur Scala aurait besoin

have to look at the right-hand side and because the square root Iter function is

de regarder du côté droit et parce que Iter est

recursive it's stacked in a cycle. It would need the return type for that to

Recursive, le compilateur est empilé dans un cycle. Il faudrait le type de retour pour que ce soit

compute the type for expression. To break the cycle, we require that

le type d'expression de calcul. Pour briser le cycle, nous exigeons que

recursive functions always have explicit return types.

les fonctions récursives ont toujours des types de retour explicites.

It actually makes sense even for other publicly used functions to give an

Il est en fait logique même pour les autres fonctions utilisées publiquement donner un

explicitly return type because that's good documentation but it's not required by the

type de retour explicite parce que c'est la bonne documentation, mais il n'est pas requis par la

language. Okay.

langue. D'accord.

So, let's implement this in practice. What we're going to see is a new way to

Donc, nous allons implémenter cela en pratique. Ce que nous allons voir est une nouvelle façon de

write programs. So far, we have done everything in the

écrire des programmes. Jusqu'à présent, nous avons tout fait dans le

repo. Now, for larger programs, we have

repl. Maintenant, pour des programmes plus importants, nous avons

something that is better adapted. We go into Eclipse and we start a

quelque chose qui est mieux adapté. Nous entrons dans Eclipse et nous commençons une

worksheet. So, I take you through the steps one by

feuille de calcul. Alors, je vous amène à travers les étapes une par

one. Here, we have an empty Eclipse thing.

une. Ici, nous avons une fenêtre vide d'Eclipse.

We first start a new project the Scala project.

Tout d'abord, nous commençons un nouveau projet, le projet Scala.

Call it, demands a name, call it [unknown] for the course.

Nommez-le, demande un nom, appelez-le [unknown] pour le cours.

And then, in the project what we can do is define a package, which is essentially a

Puis, dans le projet que nous pouvons faire est définir un package, qui est essentiellement un

directory in which we are going to put all the stuff from this week.

Répertoire dans lequel nous allons mettre tous les trucs de cette semaine.

Call this Week one. We don't need to define packages but it's

Appelez cette semaine. Il est inutile de définir les paquets, mais c'est

good practice to keep stuff tidy and ordered.

de bonnes pratiques pour garder les choses bien rangé et ordonné.

And then, in that package, we define a new sheet.

Et puis, dans cet emballage, nous définissons une nouvelle feuille.

It needs a name, let's call it Session. In a worksheet, what we can do is we can

Il a besoin d'un nom, appelons-le Session. Dans une feuille de calcul, ce que nous pouvons faire est denous pouvons

type expressions and have them evaluated, just like in a repo.

Taper les expressions et les faire évaluer, tout comme dans un repl.

So, we can do one plus two and expressions get reevaluated when we hit Save, that

Ainsi, nous pouvons faire un plus deux et expressions obtenir réévaluées lorsque nous avons atteint, sauf que

will become [unknown] or Control+S. But the expressions show up on the right

deviendra [inconnu] ou Ctrl + S. Mais les expressions apparaissent sur la droite

in a different column that you see here. We can also define functions, let's say,

dans une autre colonne que vous voyez ici. Nous pouvons également définir des fonctions, disons,

the absolute, absolute function that we've seen before.

la fonction absolue, absolue, que nous avons vu avant.

So, we could say, well, if x is less than zero - x else x And the repo would answer

Ainsi, nous pourrions dire, Et bien, si x est inférieur à zéro - x x d'autre et le repl répondrais

the, with the value of the absolute function, well, not the repo, the

le, avec la valeur de la fonction absolue, Et bien, pas le repl, la

worksheet but the two are actually related.

feuille de calcul, mais les deux sont en fait liés.

It's just a different mode of presentation.

C'est juste un autre mode de présentation.

One thing we can do which is nice, nicer in the worksheet is we can actually go

Une chose que nous pouvons faire qui est sympa, agréable dans la feuille de calcul est en fait, nous pouvons aller

back and edit expressions and the reevaluation will then show the edited

dos et modifier des expressions et la réévaluation affichera alors l'édition

value. So, it's not just a single line editing

valeur. Par conséquent, il n'est pas juste une seule ligne d'édition

window but a whole window that we can use. So, let's use the worksheet to complete

fenêtre mais une fenêtre entière que nous pouvons utiliser. Donc, nous allons utiliser la feuille de calcul pour toutes les

our square root functions. The first thing I'm going to do is take it

nos fonctions racine carrée. La première chose que je vais faire est de le prendre

from the slide. So, I select square root Iter here and

de la diapositive. Donc, j'ai sélectionner racine carrée Iter ici et

paste it inside the worksheet. I can reformat with Control+Shift+F.

coller à l'intérieur de la feuille de calcul. Puis-je reformater avec Ctrl + Maj + F.

So, that would reformat things nicely. But the worksheet still doesn't compile

Alors, qui serait reformater les choses bien. Mais la feuille de calcul ne compile toujours pas

because, of course, I have two functions here that I haven't yet defined that would

parce que, bien sûr, j'ai deux fonctions ici que je n'ai pas encore défini qui serait

be as good enough and improve. So, for isGoodEnough, let's do that first.

être aussi bon et améliorer. Donc, pour isGoodEnough, nous allons faire cela d'abord.

So, is, isGoodEnough takes these same parameters as square root Iter, and it

Par conséquent, est, isGoodEnough prend ces mêmes paramètres que la racine carrée de Iter et il

returns a bullion that says whether we can stop the iteration or whether we need more

Retourne un boolean qui dit que nous pouvons arrêter l'itération ou si nous avons besoin de plus

steps. So, what could that predicate be?

étapes. Donc, ce que pourrait être ce prédicat ?

Well, one way to do it would be to say, well, if we take the current guess here

Eh bien, une façon de le faire serait de dire, Eh bien, si nous prenons l'estimation actuelle ici

and we square it. If we are close enough to the original

et il nous place. Si nous sommes suffisamment proches de l'original

value x, then guess by itself would be close enough to the desired square root

valeur x, puis devinez par elle-même serait assez proche de la racine carrée désirée

value. So, let's code that up.

valeur. Donc, nous allons coder que jusqu'à.

We would say, guess, guess - x, we would have to take the absolute value of that.

Nous dirions, devinez, devinez - x, il faut prendre la valeur absolue de cela.

And it would have to be smaller than some epsilon value of, say, 001 for the moment.

Et elle devra être inférieure à une valeur epsilon de, disons, 001 pour le moment.

Okay. So, that was number one.

Okay. Donc, ça a été numéro un.

The second function we need to define is Improve.

La deuxième fonction, que vous devez définir est à améliorer.

And that's now the core of the Newton method, we say, would say, well, it could

Et c'est maintenant au cœur de la méthode de Newton, dit-on, serait dire, Eh bien, il pourrait

take a guess and an X. And to improve the guess, what do we do?

prendre une supposition et un X. Et pour améliorer la conjecture, que faisons-nous ?

Well, we say, we need to take the mean of the value the current value of guess and

Eh bien, nous disons, nous devons prendre la moyenne de la valeur de la valeur actuelle de guess et

the quotient of x divided by guess. So, to take the average, we would first

le quotient de x divisé par conjecture. Ainsi, pour prendre la moyenne, nous aimerions tout d'abord

sum the two values and then, divide by two.

somme des deux valeurs et ensuite diviser par deux.

Good. Now, we have a worksheet that compiles.

Bonne. Maintenant, nous avons une feuille de calcul qui compile.

You see on the right-hand side, you see all of the types.

Vous voyez sur la droite, vous voyez tous les types.

The last function we need to define is square root itself.

La dernière fonction, que vous devez définir est la racine carrée lui-même.

So, let's do that, what would that be? Well, it would be the square root

Donc, nous allons le faire, quelle serait-elle ? Eh bien, ce serait la racine carrée

iteration. With our first initial value, we said,

itération. Avec notre première valeur initiale, nous a dit,

that was 1.0 and x. Well, now, we have all the elements in

C'était 1.0 et x. Eh bien, maintenant, nous avons tous les éléments

place and we can start to test our function.

lieu et nous pouvons commencer à tester notre fonction.

Let's start with the square root of two and we get 1.4142.

Commençons par la racine carrée de deux, et nous obtenons 1.4142.

So, that looks right. Let's do another one.

Alors, qui regarde à droite. Nous allons faire un autre.

Square root of four, and we, we get something close to two, as we would

Racine carrée de quatre et nous, nous obtenons quelque chose proche de deux, comme nous le ferions

expect. So, as an exercise, I would like you to

s'attendre. Ainsi, à titre d'exercice, je voudrais vous

think about the implementation we have so far and try to improve it.

Pensez à la mise en œuvre nous avons jusqu'à maintenant et essayer de l'améliorer.

One thing to improve is that the, is good enough test is not very precise for small

Une chose à améliorer est la, est assez bon test n'est pas très précis pour les petits

numbers. And it can lead to non-termination for

numéros. Et les raisons pour lesquelles elle peut entraîner

very, very large numbers. So here, let me demonstrate that.

très, très grand nombre. Donc ici, je voudrais démontrer que.

And let's take a very small number. Let's say, one^-6.

Et nous allons prendre un très petit nombre. Disons que, un ^ -6.

So, one / 1,000,000.

Donc, on / 1 000 000.

So our square root, the square root we would expect to see is one over minus

Donc notre racine carrée, la racine carrée, qu'on s'attendrait à voir est un au moins

three. And actually what we see is 0.03.

trois. Et en fait ce que nous voyons est de 0,03.

So, that's pretty far away from where we want to be.

Alors, qui est assez loin de là où nous voulons être.

And the other problem we have is if we take a large one, let's say, one to the

Et l'autre problème, c'est si nous prenons un grand, disons, un à la

60th power. What would we see then?

puissance 60e. Ce qui nous verrait alors ?

Well, actually what we'd see is non-termination.

Eh bien, en fait ce que nous verrions est les raisons pour lesquelles.

You see this here, with this little bar? That's as well, it doesn't find the square

Vous voyez cela ici, avec ce petit bar ? C'est ainsi, il ne trouve pas la place

root. Not so good.

racine. Pas très bon.

Let me take that out with an escape. So, can you explain why that is?

Je voudrais sortir avec une évasion. Alors, pouvez-vous expliquer pourquoi c'est ?

Why is the, is good enough test not precise for small numbers and why can it

Pourquoi est la, est assez bon test pas précis pour un petit nombre et pourquoi il peut

lead to non-termination for very large numbers?

entraîner les raisons pour lesquelles de très grands nombres ?

And secondly, can you define a different version of isGoodEnough that doesn't have

Et deuxièmement, vous pouvez définir une autre version d'isGoodEnough qui n'a pas

these problems? Here are some numbers to test your, your

ces problèmes ? Voici quelques chiffres pour tester votre, vos

version, some very small and some very large numbers.

version, certains très petite et des grands nombres.

So, to answer that exercise, let's go back to our worksheet.

Donc, pour répondre à cet exercice, revenons à notre feuille de calcul.

The problem, we had for both small numbers and, and large numbers was that our

Le problème, nous avons eu pour les deux petits nombres et grand nombre était que notre

isGoodEnough test is, takes an absolute difference.

test d'isGoodEnough est, prend une différence absolue.

It asks whether the absolute difference between the square of guess and X is less

Il demande si la différence absolue entre la place de guess et X est inférieure

than some threshold value. And that's not very good for very, very

à une valeur de seuil. Et ce n'est pas très bon pour les très, très

small numbers because the number we want to find in the square root might, might

petits nombres parce que le nombre de choix nous trouver à la racine carrée pourrait, peut-être

even be smaller than that. So, that, relatively speaking, that

même être inférieur. Alors, que, relativement parlant, que

epsilon value might be huge compared to the number we want to find.

valeur Epsilon peut être énorme comparé au nombre nous voulons trouver.

And for very large numbers, we have the opposite problem, which is that very large

Et pour un très grand nombre, nous avons le problème inverse, c'est-à-dire que les très grands

floating point numbers have, can actually be further apart than this epsilon value.

nombres à virgule flottante ont, peut se révéler plus apart que cette valeur epsilon.

That means in the 52-bits, they have available for the [unknown].

Cela signifie dans la 52 bits, dont ils disposent pour le [inconnu].

It could be that the distance between one number and the next is actually larger

Il est possible que la distance entre l'un numéro et l'autre est en fait plus grande

than 0.001. And in that case, of course the iteration

que 0,001. Et dans ce cas, bien sûr l'itération

can never stop because, simply because there is no value that's ever good enough.

ne peut jamais arrêter parce que, simplement parce qu'il n'y a pas de valeur qui n'est jamais assez bon.

So, we can solve both problems by making the test proportional to x.

Ainsi, nous pouvons résoudre ces deux problèmes en effectuant le test proportionnelle à x.

And that's very simply done by saying, okay, let's divide the absolute difference

Et qui s'effectue très simplement en disant : OK, nous allons diviser la différence absolue

by the current value of x and let's make that be smaller than the threshold value.

de la valeur actuelle de x et Let's make qui est inférieure à la valeur seuil.

So, once I've done that, I can simply reevaluate my spreadsheet.

Donc, une fois que j'ai fait cela, je peux simplement réévaluer ma feuille de calcul.

And now, I will see that everything computes nicely.

Et maintenant, je vais voir que tout ce que calcule bien.

And for the small number, I get something very close to one^e-3 as expected, and for

Et le petit nombre, j'obtiens quelque chose de très proche un ^ e-3 comme prévu et pour

the large numbe, I get something like e1 to e30, and that's also as expected.

le grand nombre, j'obtiens quelque chose comme e1 pour e30, et c'est également comme prévu.

Similar videos:

12. Square Roots, Newton's Method
MIT OpenCourseWare
60.5K views 220 likes 6 dislikes 14 Jan 201380% match

¿Qué es la derivada? EXPLICACIÓN DESDE CERO
MateFacil
1.7M views 38.6K likes 1.1K dislikes 24 Sep 201528% match

Pantuflas y Babuchas A dos Agujas con Adornos | Tejidos a Palillos
Vivirtejiendo
483.3K views 9.2K likes 511 dislikes 17 Mar 201927% match

Cómo poner SUELA PLANTILLA a Pantuflas o Babuchas | vivirtejiendo
Vivirtejiendo
1M views 25.5K likes -1 dislikes 28 Oct 201926% match

Couple Builds Gorgeous Tiny House to Escape HigH Rent
Tiny House Giant Journey
259K views 7.7K likes 0 dislikes 12 Jul 201926% match

Partial derivatives, introduction
Khan Academy
836.1K views 6.5K likes 294 dislikes 11 May 201626% match

Problems with Zero - Numberphile
Numberphile
5.2M views 72.9K likes 1.5K dislikes 25 Oct 201226% match

The Scientific Method
Bozeman Science
767.8K views 2.7K likes 343 dislikes 22 Sep 201026% match

Double integrals 5 | Double and triple integrals | Multivariable Calculus | Khan Academy
Khan Academy
248.9K views 582 likes 14 dislikes 14 Aug 200826% match

Indeterminate: the hidden power of 0 divided by 0
Mathologer
1.3M views 27.1K likes 845 dislikes 02 Dec 201626% match

Splice App - Overview & Tutorial - iPhone Video Editor 2019 Update
@Brant_Moore
308.1K views 2.6K likes 155 dislikes 11 Jun 201926% match

Vector valued function derivative example | Multivariable Calculus | Khan Academy
Khan Academy
128.7K views 337 likes 6 dislikes 26 Feb 201026% match

Vintage Camper Trailer Restoration - Episode 3: “After"
Tiny House Giant Journey
144.2K views 4.7K likes 122 dislikes 23 Aug 201926% match

Renovated RV is their Beautiful Tiny Home + Cystic Fibrosis
Tiny House Giant Journey
370.4K views 13.5K likes 146 dislikes 10 Jan 202025% match

DIY globos de agua o gotas con pegamento. Experimentos fáciles | Easy glue drops experiment
Ideas FACILES
1.9M views 14.8K likes 2.2K dislikes 04 May 201625% match

Identifying an ellipse from equation | Conic sections | Algebra II | Khan Academy
Khan Academy
211.6K views 551 likes 15 dislikes 16 Jun 200925% match

Transcendental Numbers - Numberphile
Numberphile
1.9M views 30.4K likes 606 dislikes 12 Jun 201325% match

Settings Privacy About Contact Donate