Divisão e Conquista - Busca Binária

Na math.h tem o valor da raiz de 2 com uma constante:
#define M_SQRT2 1.41421356237309504880

Vamos fazer um programa que calcula o valor de $\sqrt{2}$ sem utilizar uma função pré-definida como pow(2.0,0.5).

Observação 1:
Sabemos que $\sqrt{2}$ é a raiz da seguinte função f(x) = $x^2$ - 2. Sabemos que a função f é contínua e monótona no intervalo [1,2] e f(1) < 0 < f(2).

Observação 2:
O teorema do valor intermediário garante que existe um ponto 1<=x<=2 tal que f(x)=0. O valor de x é o valor de $\sqrt{2}$. Vamos utilizar a busca binária para encontrar o valor de $\sqrt{2}$.

Observação 3:
Seja x $\in$ [a,b] , f(a) < 0  e f(b) > 0 então

• se f(x) > 0 então existe um x $\in$ [a,x] tal que f(x) = 0
• se f(x) < 0 então existe um x $\in$ [x,b] tal que f(x) = 0

Observação 4:
A condição de parada do algoritmo será |f(x)| < eps

Observação 5:

tipo            | bits | expoente | precisão decimal

-----------------|-----------|--------------------------

float            | 32 | 38            | 6

double        | 64 | 308          | 15

long double | 80 | 19.728     | 18

 

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;
template <typename T>
T precision(int n){
  T p = (T)1.0;
  for(int i=1;i<=n;i++)
   p = p/10.0;
  return p;
  
}

template <typename T>
T f(T x){
  return x*x - 2;
}


template <typename T>
void sqrt2(T inicio, T fim,T eps){
  T meio;
  T res;
  long long int numiter = 0;
  cout <<"precisao" << setprecision(18) << eps << endl;
  while(1){
    meio = (inicio+fim)/2;
    res = f(meio);
    if( fabs( res ) < eps ) break;
    else if ( res > 0 ) fim = meio;
    else if ( res < 0 ) inicio = meio;
    numiter++;
  }
  
  cout << "num iter " << numiter << endl;
  cout << "x " << setprecision(18) << meio << endl; 
}
int main()
{
    int i;
    double a = 1.0;
    double b = 2.0;

    for(int i=1;i<=15;i++){
      sqrt2(a,b,precision<double>(i));
    }
    
    system("PAUSE");
    return 0;
} 

Saída
precisao 0.10000000000000001
num iter 3
x 1.4375
precisao 0.01
num iter 6
x 1.4140625
precisao 0.001
num iter 6
x 1.4140625
precisao 0.0001
num iter 12
x 1.4141845703125
precisao 1.0000000000000001e-005
num iter 14
x 1.414215087890625
precisao 1.0000000000000002e-006
num iter 20
x 1.4142136573791504
precisao 1.0000000000000002e-007
num iter 22
x 1.4142135381698608
precisao 1.0000000000000002e-008
num iter 26
x 1.4142135605216026
precisao 1.0000000000000003e-009
num iter 28
x 1.4142135623842478
precisao 1.0000000000000003e-010
num iter 28
x 1.4142135623842478
precisao 1.0000000000000003e-011
num iter 35
x 1.4142135623696959
precisao 1.0000000000000002e-012
num iter 37
x 1.4142135623733338
precisao 1.0000000000000002e-013
num iter 41
x 1.4142135623731065
precisao 1.0000000000000002e-014
num iter 45
x 1.4142135623730923
precisao 1.0000000000000001e-015
num iter 49
x 1.4142135623730949
Pressione qualquer tecla para continuar. . .

Para adicionar mais precisão, vamos utilizar o tipo long double com maior precisão.

int main()
{
    int i;
    long double a = 1.0;
    long double b = 2.0;

    for(int i=1;i<=18;i++){
      sqrt2(a,b,precision<long double>(i));
    }
    
    system("PAUSE");
    return 0;
}

Saída

precisao 0.10000000000000001
num iter 3
x 1.4375
precisao 0.01
num iter 6
x 1.4140625
precisao 0.001
num iter 6
x 1.4140625
precisao 0.0001
num iter 12
x 1.4141845703125
precisao 1.0000000000000001e-005
num iter 14
x 1.414215087890625
precisao 9.9999999999999995e-007
num iter 20
x 1.4142136573791504
precisao 9.9999999999999995e-008
num iter 22
x 1.4142135381698608
precisao 1e-008
num iter 26
x 1.4142135605216026
precisao 1.0000000000000001e-009
num iter 28
x 1.4142135623842478
precisao 1e-010
num iter 28
x 1.4142135623842478
precisao 9.9999999999999994e-012
num iter 35
x 1.4142135623696959
precisao 9.9999999999999998e-013
num iter 37
x 1.4142135623733338
precisao 1e-013
num iter 41
x 1.4142135623731065
precisao 1e-014
num iter 45
x 1.4142135623730923
precisao 1.0000000000000001e-015
num iter 49
x 1.4142135623730949
precisao 9.9999999999999998e-017
num iter 52
x 1.4142135623730949
precisao 1.0000000000000001e-017
num iter 55
x 1.4142135623730951
precisao 1.0000000000000001e-018
num iter 60
x 1.4142135623730951
Pressione qualquer tecla para continuar. . .

Outros links:
http://diegodonah.wordpress.com/2009/11/16/bug-secreto-na-busca-binaria/
http://www.ime.usp.br/~pf/algoritmos/aulas/footnotes/epigraphs.html
http://blog.ricbit.com/2012/06/formula-de-bhaskara.html
http://searchforquality.blogspot.com.br/2007/06/very-interesting-bug.html
http://locklessinc.com/articles/binary_search/