Écrire votre propre fonction racine carrée
comment écrivez-vous votre propre fonction pour trouver la racine carrée la plus précise d'un entier?
après l'avoir googlé, j'ai trouvé ce (archivé de son lien original ), mais d'abord, je ne l'ai pas obtenu complètement, et deuxièmement, il est approximatif aussi.
suppose racine carrée comme entier le plus proche (à la racine réelle) ou un flotteur.
20 réponses
le plancher de calcul suivant (sqrt( N)) Pour N > 0:
x = 2^ceil(numbits(N)/2)
loop:
y = floor((x + floor(N/x))/2)
if y >= x
return x
x = y
c'est une version de la méthode de Newton donnée dans Crandall & Pomerance,"Prime Numbers: a Computational Perspective". La raison pour laquelle vous devriez utiliser cette version est que les gens qui savent ce qu'ils font ont prouvé qu'elle converge exactement au sol de la racine carrée, et c'est simple de sorte que la probabilité de faire une erreur de mise en œuvre est petite. Il est également rapide (bien qu'il soit possible de construire un algorithme encore plus rapide -- mais faire cela correctement est beaucoup plus complexe). Une recherche binaire correctement implémentée peut être plus rapide pour de très petites N, mais là vous pouvez aussi bien utiliser une table de recherche.
D'arrondir le plus proche entier, juste calculer t = floor(sqrt(4N)) à l'aide de l'algorithme ci-dessus. Si le bit le moins significatif de t est défini, choisissez x = (t+1)/2; sinon, choisissez t/2. Notez que cette arrondit sur une cravate; vous pouvez également arrondir (ou rond à pair) en regardant si le reste est non nul (i.e. si t^2 == 4N).
Notez que vous n'avez pas besoin d'utiliser l'arithmétique à virgule flottante. En fait, tu ne devrais pas. Cet algorithme devrait être mis en œuvre entièrement en utilisant des entiers (en particulier, les fonctions floor() indiquent juste que la division entière régulière devrait être utilisée).
en fonction de vos besoins, une stratégie simple "diviser pour mieux régner" peut être utilisée. Il ne va pas converger comme rapide comme d'autres méthodes, mais il peut être beaucoup plus facile pour un novice de comprendre. De plus, puisqu'il s'agit d'un algorithme O(log n) (réduisant de moitié l'espace de recherche à chaque itération), le pire cas pour un flotteur 32 bits sera 32 itérations.
disons que vous voulez la racine carrée de 62.104. Tu choisis une valeur à mi-chemin entre 0 et ça, et tu la règles. Si le carré est plus élevé que votre nombre, vous devez vous concentrer sur les nombres inférieurs au point médian. Si c'est trop bas, concentrez-vous sur ceux plus haut.
avec de vraies mathématiques, vous pouvez continuer à diviser l'espace de recherche en deux pour toujours (si elle n'a pas une racine carrée rationnelle). En réalité, les ordinateurs finiront par manquer de précision et vous aurez votre approximation. Le programme C suivant illustre ce point:
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[]) {
float val, low, high, mid, oldmid, midsqr;
int step = 0;
// Get argument, force to non-negative.
if (argc < 2) {
printf ("Usage: sqrt <number>\n");
return 1;
}
val = fabs (atof (argv[1]));
// Set initial bounds and print heading.
low = 0;
high = mid = val;
oldmid = -1;
printf ("%4s %10s %10s %10s %10s %10s %s\n",
"Step", "Number", "Low", "High", "Mid", "Square", "Result");
// Keep going until accurate enough.
while (fabs(oldmid - mid) >= 0.00001) {
oldmid = mid;
// Get midpoint and see if we need lower or higher.
mid = (high + low) / 2;
midsqr = mid * mid;
printf ("%4d %10.4f %10.4f %10.4f %10.4f %10.4f ",
++step, val, low, high, mid, midsqr);
if (mid * mid > val) {
high = mid;
printf ("- too high\n");
} else {
low = mid;
printf ("- too low\n");
}
}
// Desired accuracy reached, print it.
printf ("sqrt(%.4f) = %.4f\n", val, mid);
return 0;
}
voici quelques passages on espère avoir une idée de comment ça marche. Pour 77:
pax> sqrt 77
Step Number Low High Mid Square Result
1 77.0000 0.0000 77.0000 38.5000 1482.2500 - too high
2 77.0000 0.0000 38.5000 19.2500 370.5625 - too high
3 77.0000 0.0000 19.2500 9.6250 92.6406 - too high
4 77.0000 0.0000 9.6250 4.8125 23.1602 - too low
5 77.0000 4.8125 9.6250 7.2188 52.1104 - too low
6 77.0000 7.2188 9.6250 8.4219 70.9280 - too low
7 77.0000 8.4219 9.6250 9.0234 81.4224 - too high
8 77.0000 8.4219 9.0234 8.7227 76.0847 - too low
9 77.0000 8.7227 9.0234 8.8730 78.7310 - too high
10 77.0000 8.7227 8.8730 8.7979 77.4022 - too high
11 77.0000 8.7227 8.7979 8.7603 76.7421 - too low
12 77.0000 8.7603 8.7979 8.7791 77.0718 - too high
13 77.0000 8.7603 8.7791 8.7697 76.9068 - too low
14 77.0000 8.7697 8.7791 8.7744 76.9893 - too low
15 77.0000 8.7744 8.7791 8.7767 77.0305 - too high
16 77.0000 8.7744 8.7767 8.7755 77.0099 - too high
17 77.0000 8.7744 8.7755 8.7749 76.9996 - too low
18 77.0000 8.7749 8.7755 8.7752 77.0047 - too high
19 77.0000 8.7749 8.7752 8.7751 77.0022 - too high
20 77.0000 8.7749 8.7751 8.7750 77.0009 - too high
21 77.0000 8.7749 8.7750 8.7750 77.0002 - too high
22 77.0000 8.7749 8.7750 8.7750 76.9999 - too low
23 77.0000 8.7750 8.7750 8.7750 77.0000 - too low
sqrt(77.0000) = 8.7750
pour 62.104:
pax> sqrt 62.104
Step Number Low High Mid Square Result
1 62.1040 0.0000 62.1040 31.0520 964.2267 - too high
2 62.1040 0.0000 31.0520 15.5260 241.0567 - too high
3 62.1040 0.0000 15.5260 7.7630 60.2642 - too low
4 62.1040 7.7630 15.5260 11.6445 135.5944 - too high
5 62.1040 7.7630 11.6445 9.7037 94.1628 - too high
6 62.1040 7.7630 9.7037 8.7334 76.2718 - too high
7 62.1040 7.7630 8.7334 8.2482 68.0326 - too high
8 62.1040 7.7630 8.2482 8.0056 64.0895 - too high
9 62.1040 7.7630 8.0056 7.8843 62.1621 - too high
10 62.1040 7.7630 7.8843 7.8236 61.2095 - too low
11 62.1040 7.8236 7.8843 7.8540 61.6849 - too low
12 62.1040 7.8540 7.8843 7.8691 61.9233 - too low
13 62.1040 7.8691 7.8843 7.8767 62.0426 - too low
14 62.1040 7.8767 7.8843 7.8805 62.1024 - too low
15 62.1040 7.8805 7.8843 7.8824 62.1323 - too high
16 62.1040 7.8805 7.8824 7.8815 62.1173 - too high
17 62.1040 7.8805 7.8815 7.8810 62.1098 - too high
18 62.1040 7.8805 7.8810 7.8807 62.1061 - too high
19 62.1040 7.8805 7.8807 7.8806 62.1042 - too high
20 62.1040 7.8805 7.8806 7.8806 62.1033 - too low
21 62.1040 7.8806 7.8806 7.8806 62.1038 - too low
22 62.1040 7.8806 7.8806 7.8806 62.1040 - too high
23 62.1040 7.8806 7.8806 7.8806 62.1039 - too high
sqrt(62.1040) = 7.8806
pour 49:
pax> sqrt 49
Step Number Low High Mid Square Result
1 49.0000 0.0000 49.0000 24.5000 600.2500 - too high
2 49.0000 0.0000 24.5000 12.2500 150.0625 - too high
3 49.0000 0.0000 12.2500 6.1250 37.5156 - too low
4 49.0000 6.1250 12.2500 9.1875 84.4102 - too high
5 49.0000 6.1250 9.1875 7.6562 58.6182 - too high
6 49.0000 6.1250 7.6562 6.8906 47.4807 - too low
7 49.0000 6.8906 7.6562 7.2734 52.9029 - too high
8 49.0000 6.8906 7.2734 7.0820 50.1552 - too high
9 49.0000 6.8906 7.0820 6.9863 48.8088 - too low
10 49.0000 6.9863 7.0820 7.0342 49.4797 - too high
11 49.0000 6.9863 7.0342 7.0103 49.1437 - too high
12 49.0000 6.9863 7.0103 6.9983 48.9761 - too low
13 49.0000 6.9983 7.0103 7.0043 49.0598 - too high
14 49.0000 6.9983 7.0043 7.0013 49.0179 - too high
15 49.0000 6.9983 7.0013 6.9998 48.9970 - too low
16 49.0000 6.9998 7.0013 7.0005 49.0075 - too high
17 49.0000 6.9998 7.0005 7.0002 49.0022 - too high
18 49.0000 6.9998 7.0002 7.0000 48.9996 - too low
19 49.0000 7.0000 7.0002 7.0001 49.0009 - too high
20 49.0000 7.0000 7.0001 7.0000 49.0003 - too high
21 49.0000 7.0000 7.0000 7.0000 49.0000 - too low
22 49.0000 7.0000 7.0000 7.0000 49.0001 - too high
23 49.0000 7.0000 7.0000 7.0000 49.0000 - too high
sqrt(49.0000) = 7.0000
une méthode simple (mais pas très rapide) pour calculer la racine carrée de X:
squareroot(x)
if x<0 then Error
a = 1
b = x
while (abs(a-b)>ErrorMargin)
a = (a+b)/2
b = x/a
endwhile
return a;
exemple: squareroot (70000)
a b
1 70000
35001 2
17502 4
8753 8
4381 16
2199 32
1116 63
590 119
355 197
276 254
265 264
comme vous pouvez le voir il définit une limite supérieure et une limite inférieure pour la racine carrée et rétrécit la limite jusqu'à ce que sa taille est acceptable.
il y a des méthodes plus efficaces mais celle-ci illustre le processus et est facile à comprendre.
il suffit de se méfier de mettre L'Errormargin à 1 si vous utilisez des entiers autrement vous avez une boucle sans fin.
Permettez-moi de souligner une méthode extrêmement intéressante de calcul d'une racine carrée inverse 1/sqrt(x) qui est une légende dans le monde de la conception de jeu parce qu'il est esprit-incroyablement rapide. Ou attendre, lire le post suivant:
http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root /
PS: je sais que vous voulez juste la racine carrée mais l'élégance de quake surmonté toute résistance de ma part :)
soit dit en passant, l'article mentionné ci-dessus parle aussi de L'ennuyeuse approximation Newton-Raphson quelque part.
bien sûr, c'est approximatif; c'est ainsi que les mathématiques avec des nombres à virgule flottante fonctionnent.
de toute façon, la méthode standard est avec méthode de Newton . C'est à peu près la même chose que D'utiliser la série de Taylor, l'autre façon qui vient immédiatement à l'esprit.
calculer racine carrée avec précision arbitraire en Python
#!/usr/bin/env python
import decimal
def sqrt(n):
assert n > 0
with decimal.localcontext() as ctx:
ctx.prec += 2 # increase precision to minimize round off error
x, prior = decimal.Decimal(n), None
while x != prior:
prior = x
x = (x + n/x) / 2 # quadratic convergence
return +x # round in a global context
decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()
sortie:
111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True
c'est une question d'interview courante posée par Facebook etc. Je ne pense pas que ce soit une bonne idée d'utiliser la méthode de Newton dans une interview. Et si l'intervieweur vous demande le mécanisme de la méthode de Newton alors que vous ne le comprenez pas vraiment?
j'ai fourni une solution basée sur la recherche binaire en Java que je crois que tout le monde peut comprendre.
public int sqrt(int x) {
if(x < 0) return -1;
if(x == 0 || x == 1) return x;
int lowerbound = 1;
int upperbound = x;
int root = lowerbound + (upperbound - lowerbound)/2;
while(root > x/root || root+1 <= x/(root+1)){
if(root > x/root){
upperbound = root;
} else {
lowerbound = root;
}
root = lowerbound + (upperbound - lowerbound)/2;
}
return root;
}
vous pouvez tester mon code ici: leetcode: sqrt (x)
a trouvé un grand article sur Les Racines Carrées entières .
c'est une version légèrement améliorée qu'il présente là:
unsigned long sqrt(unsigned long a){
int i;
unsigned long rem = 0;
unsigned long root = 0;
for (i = 0; i < 16; i++){
root <<= 1;
rem = (rem << 2) | (a >> 30);
a <<= 2;
if(root < rem){
root++;
rem -= root;
root++;
}
}
return root >> 1;
}
Voici une façon d'obtenir une racine carrée en utilisant la trigonométrie. Ce n'est pas l'algorithme le plus rapide, mais il est précis. Le Code est en javascript:
var n = 5; //number to get the square root of
var icr = ((n+1)/2); //intersecting circle radius
var sqrt = Math.cos(Math.asin((icr-1)/icr))*icr; //square root of n
alert(sqrt);
il y a un algorithme que j'ai étudié à l'école que vous pouvez utiliser pour calculer des racines carrées exactes (ou de grande précision si la racine est un nombre irrationnel). Il est certainement plus lent que les algorithmes de Newton, mais il est exact. Disons que vous voulez calculer la racine carrée de 531.3025
la première chose est de diviser votre nombre à partir du point décimal en groupes de 2 chiffres:
{5} {31}.{30}{25}
Puis:
1) Trouver la racine carrée la plus proche pour le premier groupe qui est plus petite ou égale à la racine carrée réelle du premier groupe: sqrt({5}) > = 2. Cette racine carrée est le premier chiffre de votre réponse finale. Indiquons les chiffres que nous avons déjà trouvés de notre racine carrée finale comme B. donc au moment B = 2.
2) calculer ensuite la différence entre {5} et b^2: 5-4 = 1.
3) Pour tous les 2 chiffres groupes suivants:
Multiplier le reste par 100, puis l'ajouter au deuxième groupe: 100 + 31 = 131.
Trouver x-prochain chiffre de votre racine, tel que 131 >=((B*20) + X)*X. X = 3. 43 * 3 = 129 < 131. Maintenant B = 23. Aussi parce que vous n'avez plus de groupes à 2 chiffres à la gauche des points décimaux, vous avez trouvé tous les nombres entiers de votre racine finale.
4) répéter la même chose pour {30} et {25}. Donc vous avez:
{30} : 131 - 129 = 2. 2 * 100 + 30 = 230 >= (23*2*10 + X) * X - > X = 0 - > B = 23,0
{25} : 230 - 0 = 230. 230 * 100 + 25 = 23025. 23025 >= (230 * 2 * 10 + X) * X - > X = 5 - > B = 23,05
Résultat Final = 23.05.
L'algorithme semble compliqué de cette façon mais il est beaucoup plus simple si vous le faites sur le papier en utilisant la même notation que vous utilisez pour "division longue" vous avez étudié à l'école, sauf que vous ne faites pas de division mais calculez la racine carrée.
la première chose qui me vient à l'esprit est: c'est un bon endroit pour utiliser la recherche binaire (inspiré par ce grand tutoriels .)
pour trouver la racine carrée de vaule ,nous cherchons le number dans (1..value) où le prédicteur
est vrai pour la première fois. Le prédicteur que nous choisissons est number * number - value > 0.00001 .
double square_root_of(double value)
{
assert(value >= 1);
double lo = 1.0;
double hi = value;
while( hi - lo > 0.00001)
{
double mid = lo + (hi - lo) / 2 ;
std::cout << lo << "," << hi << "," << mid << std::endl;
if( mid * mid - value > 0.00001) //this is the predictors we are using
{
hi = mid;
} else {
lo = mid;
}
}
return lo;
}
// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt (isqrt4)
// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)
private static uint sqrt(uint x)
{
uint y, z;
if (x < 1u << 16)
{
if (x < 1u << 08)
{
if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
else
{
if (x < 1u << 06)
{ y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
else
{ y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
}
}
else // slower (on my pc): .... y = 3u << 04; } goto L1; }
{
if (x < 1u << 12)
{
if (x < 1u << 10)
{ y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
else
{ y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
}
else
{
if (x < 1u << 14)
{ y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
else
{ y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
}
}
}
else
{
if (x < 1u << 24)
{
if (x < 1u << 20)
{
if (x < 1u << 18)
{ y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
else
{ y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
}
else
{
if (x < 1u << 22)
{ y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
else
{ y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
}
}
else
{
if (x < 1u << 28)
{
if (x < 1u << 26)
{ y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
else
{ y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
}
else
{
if (x < 1u << 30)
{ y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
else
{ y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
}
}
}
z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}
use recherche binaire
public class FindSqrt {
public static void main(String[] strings) {
int num = 10000;
System.out.println(sqrt(num, 0, num));
}
private static int sqrt(int num, int min, int max) {
int middle = (min + max) / 2;
int x = middle * middle;
if (x == num) {
return middle;
} else if (x < num) {
return sqrt(num, middle, max);
} else {
return sqrt(num, min, middle);
}
}
}
en général la racine carrée d'un entier (comme 2, par exemple) peut seulement être approximé (pas en raison de problèmes avec l'arithmétique flottante, mais parce qu'ils sont des nombres irrationnels qui ne peuvent pas être calculés exactement).
bien sûr, certaines approximations sont meilleures que d'autres. Je veux dire, bien sûr, que la valeur 1.732 est une meilleure approximation de la racine carrée de 3, de 1,7
La méthode utilisée par le code à ce lien vous avez donné des travaux en prenant une première approximation et en l'utilisant pour calculer une meilleure approximation.
C'est la méthode de Newton, et vous pouvez répéter le calcul avec chaque nouvelle approximation jusqu'à c'est assez précis pour vous.
en fait il doit être une façon de décider quand arrêter la répétition ou il va courir pour toujours.
Habituellement vous arrêteriez quand la différence entre les approximations est moins que une valeur que vous décidez.
EDIT: Je ne pense pas qu'il puisse y avoir une implémentation plus simple que les deux que vous avez déjà trouvées.
l'inverse, comme dit le nom, mais parfois "assez proche" est "assez proche"; une lecture intéressante en tout cas.
// A Java program to find floor(sqrt(x)
public class Test
{
public static int floorSqrt(int x)
{
// Base Cases
if (x == 0 || x == 1)
return x;
// Do Binary Search for floor(sqrt(x))
int start = 1, end = x, ans=0;
while (start <= end)
{
int mid = (start + end) / 2;
// If x is a perfect square
if (mid*mid == x)
return mid;
// Since we need floor, we update answer when mid*mid is
// smaller than x, and move closer to sqrt(x)
if (mid*mid < x)
{
start = mid + 1;
ans = mid;
}
else // If mid*mid is greater than x
end = mid - 1;
}
return ans;
}
// Driver Method
public static void main(String args[])
{
int x = 11;
System.out.println(floorSqrt(x));
}
}
sortie: 3 (plancher)
Let 's' be the answer. We know that 0 <= s <= x.
Consider any random number r.
If r*r <= x, s >= r
If r*r > x, s < r.
algorithme:
-
commence par "démarrer" = 0, fin = 'x', après tout "démarrer" est plus petit ou égal à "fin".
-
a) Calculer " mid " comme (debut + fin)/2
-
B) comparer mid*mid avec X.
- c) SI x est égal à mid*mid, retourner mid.
- d) SI x est plus grand, faites une recherche binaire entre mid+1 et end. Dans ce cas, nous mettons également à jour le SNA (notez que nous avons besoin d'un étage).
- e) si x est plus petit, faire une recherche binaire entre le début et le milieu de 1
la complexité temporelle de la solution ci-dessus est O(√ n).
Une solution simple qui peut faire face à flotteur racine carrée et une précision arbitraire à l'aide de la recherche binaire
codé en rubis
include Math
def sqroot_precision num, precision
upper = num
lower = 0
middle = (upper + lower)/2.0
while true do
diff = middle**2 - num
return middle if diff.abs <= precision
if diff > 0
upper = middle
else diff < 0
lower = middle
end
middle = (upper + lower)/2.0
end
end
puts sqroot_precision 232.3, 0.0000000001
disons que nous essayons de trouver la racine carrée de 2, et vous avez une estimation de 1,5. Nous dirons a = 2, et x = 1,5. Pour calculer une meilleure estimation, on divisera a par X. Ceci donne une nouvelle valeur y = 1.333333. Cependant, nous ne pouvons pas prendre cela comme notre prochaine estimation (pourquoi pas?). Nous avons besoin de moyenne avec l'estimation précédente. Donc notre prochaine estimation, xx sera (x + y) / 2, ou 1.416666.
Double squareRoot(Double a, Double epsilon) {
Double x = 0d;
Double y = a;
Double xx = 0d;
// Make sure both x and y != 0.
while ((x != 0d || y != 0d) && y - x > epsilon) {
xx = (x + y) / 2;
if (xx * xx >= a) {
y = xx;
} else {
x = xx;
}
}
return xx;
}
Epsilon détermine à quel point l'approximation doit être précise être. La fonction devrait retourner la première approximation x qu'elle obtient qui satisfait abs(x*x - a) < epsilon, où abs(x) est la valeur absolue de X.
square_root(2, 1e-6)
Output: 1.4142141342163086
Eh bien il y a déjà pas mal de réponses, mais voici la mienne C'est le plus simple morceau de code ( pour moi ), voici le algorithme pour lui.
et code en python 2.7:
from __future__ import division
val = 81
x = 10
def sqr(data,x):
temp = x - ( (x**2 - data)/(2*x))
if temp == x:
print temp
return
else:
x = temp
return sqr(data,x)
#x =temp
#sqr(data,x)
sqr(val,x)
pour calculer la racine carrée d'un nombre à l'aide de la fonction intégrée
# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;
float squreroot(float);
float z=squareroot(x);
cout<<z;
float squareroot(int x)
{
float s;
s = pow(x,.5)
return(s);
}