Mettre en œuvre le double sqrt(double x) dans C++

Mettre en œuvre double sqrt(double x) en C++ sans utiliser std bibliothèque.

C'est un facebook les questions de l'entrevue que j'ai vu ici. http://www.glassdoor.com/Interview/Implement-double-sqrt-double-x-in-C-QTN_87210.htm
Toute autre bonne idée à ce sujet?...

!!!Édité.!!!(sans utiliser std bibliothèque.)

  • #include <cmath> [newline] double sqrt(double x) { return std::sqrt(x); }
  • Je pensais #include <cmath> [newline] double sqrt(double x) { return std::pow(x, 0.5); }
  • en.wikipedia.org/wiki/Newton%27s_method
  • en.wikipedia.org/wiki/Methods_of_computing_square_roots
  • Ce doit être l'un des plus idiotes les questions de l'entretien. Ils veulent quelqu'un capable de C++ ou de quelqu'un en sachant algorithmes, qui peut facilement être regardé?
  • Ce n'est pas une "programmation" la question, c'est une des mathématiques de la théorie question

InformationsquelleAutor Josh Morrison | 2011-02-15
  1. 7

    Look ici. Cette CodeProject article compare 14 différentes méthodes pour le calcul de la racine carrée.

    InformationsquelleAutor Lior Kogan
  2. 4

    Les deux réponses évidentes sont non-bloquante (semi-lente) et de Newton-Raphson/Leibniz itération (généralement plus rapide). Pour éviter de gâcher un plaisir, je vais faire un reinterpret_cast sur la question, voici une mise en œuvre d'un entier de la racine carrée dans 8086 langage d'assemblage à l'aide de la technique de Newton-Raphson:

    isqrt proc uses di, number:word
;
; uses bx, cx, dx
;
    mov di,number
    mov ax,255
start_loop:
    mov bx,ax
    xor dx,dx
    mov ax,di
    div bx
    add ax,bx
    shr ax,1
    mov cx,ax
    sub cx,bx
    cmp cx,2
    ja  start_loop
    ret
isqrt endp

    Il est ouvert à une certaine amélioration -- il utilise x/2, tel que son estimation initiale à la sqrt(x). 386+ instructions, vous pouvez utiliser bsr de trouver le bit le plus significatif c'est réglé pour obtenir une approximation de log2x, et de diviser le résultat par 2 pour obtenir votre première approximation.

    Otoh, que, cela ne fait sens que sur les anciens processeurs. Pour quoi que ce soit depuis le 486 (ou presque) qui a intégré dans le matériel de point flottant, il est presque certain que la FSQRT instruction va battre ce (ou n'importe quoi d'autre, vous pouvez écrire).

    • autant que je sache, à l'aide de la Réciproque approche en.wikipedia.org/wiki/... est plus rapide, probablement parce qu'il substitue intelligent hacks à une boucle. Je ne suis pas sûr de sa précision cependant.
    • M.: Oui, si vous modifiez le problème, vous pouvez améliorer la vitesse un peu. La plupart d'entre eux font également un très approximation plus grossière que seulement bon pour environ 10 ou 12 bits (ce qui est encore ~1 pixel au typique des résolutions). Pour une réelle racine carrée, cependant, c'est vraiment difficile à battre du matériel dédié.
    • oui, bien sûr, mais je faisais allusion à l'assemblée de la fonction vous avez écrit: j'ai utilisé la Réciproque approche avec une parfaite précision sur des entiers, et je pense que l'ajout de quelques itérations de Newton permettrait d'améliorer la précision un peu. Ce qui est intéressant, c'est de faire une bonne première approximation, de toute façon, vous pouvez ensuite affiner la précision en fonction de vos besoins.
    InformationsquelleAutor Jerry Coffin
  3. 4

    Ici est l'un des plus génie sqrt implémentations qui peut être trouvé sur wikipédia. Ce n'est pas la plus précise, mais aussi extrêmement rapide.

    float fast_sqrt(float number) {
   long i;
   float x2, y;
   const float threehalfs = 1.5F;

   x2 = number * 0.5F;
   y  = number;
   i  = * ( long * ) &y;                     //floating point bit level hacking [sic]
   i  = 0x5f3759df - ( i >> 1 );             //Newton's approximation
   y  = * ( float * ) &i;
   y  = y * ( threehalfs - ( x2 * y * y ) ); //1st iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); //2nd iteration
   y  = y * ( threehalfs - ( x2 * y * y ) ); //3rd iteration

   return 1/y;
}
    • Et vous nous dire qu'est ce que vous pensez que la réponse doit avoir été à l'entrevue?
    • Voulait-il le travail? Vous êtes censé vouloir impressionner lors de l'entrevue.
    • utiliser la méthodologie de la rapide inverse de la racine carrée de la fonction de Quake - cette formule est étonnant - savez-vous si il?" serait probablement suffisant. (si, techniquement, ce n'3 passes de newton-raphson rapprochement au lieu de 1... donc ce n'est pas tout à fait la même chose)
    • oh ya, j'ai ajouté ces pour un peu plus de précision, et j'ai oublié de les sortir. fondamentalement la même chose tho.
    • J'ai utilisé cette méthode sur des entiers et pour 32bits une seule itération était suffisante pour une précision de 100% (prises de nombres aléatoires et dont les bords), avez-vous vérifié les itérations supplémentaires pour float ?
    • cracher à partir de la mémoire & il peut l'impressionner. Mais, quels sont-ils susceptibles de s'attendre? Si ce n'est pas un emploi où vous êtes que le niveau de maths peut être prévu, ou sqrt est particulièrement pertinente, juste un travail de mise en œuvre de la pratique, le bon sens comme successive approximation. Le fait qu'il est une puissance constante de 0,5 et pas un journal ou une autre fonction est probablement l'accessoire. Une référence au Tremblement de terre dirais que comme une curiosité pour moi, si on ne pouvait pas expliquer l'algo, tout comme le "C++ boost::any donne le temps d'exécution de la saisie de" ne vaut pas beaucoup sans la mise en œuvre de la perspicacité.
    • OK j'espère que votre accord avec BoneOS à l'aide de cette.. Nous avons cité que par son originalité. Source github.com/Bone-Project/BoneOS/blob/amanuel_progress_kbd/libc/...

    InformationsquelleAutor regality
  4. 0

    Si je suis autorisé à utiliser log (ln) et exp puis, bien sûr, exp(log(x)/2) me donnent la racine carrée.

    En supposant que pas:

    Si notre valeur, nous trouvons la racine carrée de x et la valeur de départ est de y, puis on itère y-> y+x/y)/2

    Condition d'arrêt pourraient être à proximité de y à sa valeur précédente ou de y*y x.

    Avec 385 que ma valeur de x, je reçois ces valeurs dans mon itérations (Excel)

    1
193
97.49740933
50.7231161
29.15667189
21.1805984
19.67880541
19.62150055
19.62141687
19.62141687

    Vous pouvez utiliser un "approximative" de la 2^(log base 2(x)/2) comme un point de départ au lieu de 1.
    385 a un log quelque part entre le 8 et le 9, et si nous disons 8.5 et donc commencer avec 2^4.25. Si nous faisons cela linéaire entre 16 et 32 puis nous allons commencer avec 20.

    De départ avec 20-je y arriver en seulement 4 étapes:

    20
19.625
19.6214172
19.62141687

    mais il requis précédent "itérations" pour calculer la taille approximative des journaux et exponentielle.

    InformationsquelleAutor CashCow