2.4. Búsqueda binaria#

2.4.1. Adivinar un número entre el 1 y el 100#

Nos piden adivinar un número entero \(N\) del 1 al 100. Ya conocemos un algoritmo de búsqueda exhaustiva. En el algoritmo de búsqueda binaria se empieza en \(n_0=50,\) el punto medio de la secuencia considerada, no en el primer valor, y se verifica si \(N\) es o bien

i) igual a $n_0$, o bien 
ii) mayor que $n_0$ o bien 
iii) menor a $n_0$. 

En el primer caso ya habríamos acabado. En el segundo caso, escogeríamos el punto medio entre 0 y 50, es decir 25, como nuestra siguente apuesta; en el tercer caso se escogería el 75. Reptiendo el procedimiento llegaremos a \(N\).

import random
N = random.randint(1,100)

def busqueda_binaria(N):
    
    limInf = 1
    limSup = 100
    n = int((limSup + limInf)/2)
    
    while n != N:
        if n < N:
            limInf = n
        else:
            limSup = n
        n = int((limSup + limInf)/2)
    
    print('Has acertado, el número es: ',n,N)

busqueda_binaria(N)      
Has acertado, el número es:  14 14

En la búsqueda binaria las condiciones que se verifican a cada paso requieren mucha información: si nuestra apuesta es mayor, igual o menor a \(N\). Para poder hacer estas verificaciones es necesario que haya algún tipo de orden subyacente en los elementos entre los que buscamos. En particular, los número enteros son un conjunto ordenado y poseen las propiedades necesarias para esta tarea. En este caso usamos también los operadores de comparación > y <.

2.4.2. Uso de la búsqueda binaria para calcular la raíz cuadrada#

Vamos a mejorar el algoritmo de búsqueda de la raíz cuadrada de un número mayor que uno. Para ello usaremos que si \(N>1\) entonces

\[ 1<N<N^2\Leftrightarrow 1<\sqrt[2]{N}<N. \]

Por tanto, dado un número \(N\), su raíz cuadrada estará en el intervalo \([1,N]\). Llamaremos \(r\) al valor buscado, es decir, a la raíz cuadrada de \(N\): \(r=\sqrt{N}\).

Como el intervalo \([1,N]\) es un conjunto ordenado podemos usar, como primera aproximación de \(r\), el punto medio del intervalo, \(\tilde{r}\), y preguntar si el cuadrado de ese número es

i) igual a $N$ (con una precisión dada), 
ii) mayor (con una precisión dada) o 
iii) menor que $N$ (con una precisión dada). 

En el primer caso hemos terminado. En el segundo ocurrirá que la raíz cuadrada de \(N\) estará en el intervalo \([1,\tilde{r}]\) y en el tercero en \([\tilde{r},N]\). Repetimos el procedimiento con una nueva aproximación a \(r\), que sea el punto medio del intervalo obtenido en el paso anterior.

Atención: no podemos usar preguntas del tipo ¿es \(\tilde{r}\) igual/mayor/menor que la raíz de \(N\)? No conocemos ese valor, por tanto hemos de comparar usando \(\tilde{r}^2\).

N = 389
precision = 0.001

menor = 1
mayor = N
prueba = (menor + mayor)/2
contador = 0

while abs(prueba**2 - N) >= precision:
    if prueba**2 > N:
        mayor = prueba
    else:
        menor = prueba
    prueba =(menor + mayor)/2
    contador += 1

print('La raíz cuadrada de ',N,' es ',prueba, 'con una precisión ',precision)
print('Hemos dado: ',contador,' iteraciones.')
La raíz cuadrada de  389  es  19.723065853118896 con una precisión  0.001
Hemos dado:  22  iteraciones.

2.4.3. Ventajas de la búsqueda binaria#

Hemos visto que la búsqueda binaria es más restrictiva que la búsqueda exhaustiva: es necesaria una ordenación del conjunto donde estamos buscando. En el caso de los números enteros o reales esta ordenación existe, pero en otros casos puede no existir o no ser tan obvia. Pensemos en la tarea de contar la cantidad de letras s de las obras completas de Calderón de la Barca. ¿Qué tipo de orden existe entre las letras de, por ejemplo, La vida es sueño?

Esta restricción, tan fastidiosa a veces, viene con una gran ventaja: la búsqueda binaria es mucho más eficiente que la búsqueda exhaustiva. Usando la búsqueda binaria daremos muchos menos pasos, en media, para llegar a nuestro objetivo.

Observaciones: Existen algoritmos que mejoran la velocidad de la búsqueda binaria.

Adivinar un número entre 1 y 100

Vamos a contar el número de preguntas que tenemos que hacer en cada caso, es decir, el número de iteraciones que hay que realizar para obtener el resultado.

#import random
#N = random.randint(1,100)
N = 86

def busqueda_exhaustiva_pasos(N):
    pasos = 0
    for i in range(1,101):
        pasos += 1
        if i == N:
            print('Has acertado, el número es: ',i,N)
            print('Hemos necesitado: ',pasos,' pasos.')
            break

def busqueda_binaria_pasos(N):
    limInf = 1
    limSup = 100
    n = int((limSup+limInf)/2)
    pasos = 0
    
    while n != N:
        if N > n:
            limInf = n
        else:
            limSup = n
        n = int((limSup + limInf)/2)
        pasos+=1
    
    print('Has acertado, el número es: ',n,N)
    print('Hemos necesitado: ',pasos,' pasos.')

busqueda_exhaustiva_pasos(N)
busqueda_binaria_pasos(N) 
Has acertado, el número es:  86 86
Hemos necesitado:  86  pasos.
Has acertado, el número es:  86 86
Hemos necesitado:  6  pasos.

Para el caso particular \(N=86\) necesitamos \(86\) pasos en la búsqueda exhaustiva y solamente 6 de la búsqueda binaria. Veamos qué sucede en media.

Vamos a realizar varias simulaciones aleatorias con ambas búsquedas. Veremos que, en media, el número de iteracines en la búsqueda binaria es próximo 5 en media, mientras que en la búsqueda exhaustiva es próxima, en media, a 53, con 10 simulaciones.

def busqueda_exhaustiva_numero_pasos(N):
    pasos = 0
    for i in range(1,101):
        pasos += 1
        if i == N:
            break
    return pasos
            
def busqueda_binaria_numero_pasos(N):
    limInf = 1
    limSup = 100
    n = int((limSup + limInf)/2)
    pasos = 0
    
    while n != N:
        if n < N:
            limInf = n
        else:
            limSup = n
        n = int((limSup + limInf)/2)
        pasos += 1
    return pasos

pasos_busqueda_exhaustiva = 0
pasos_busqueda_binaria = 0

media_exhaustiva = 0
media_binaria = 0
    
simulaciones = 1000
simulaciones_efectivas = 0
estamos_en_100 = False
enes = ''

import random
for s in range(simulaciones):
    N = random.randint(1,100)
    enes += str(N) +','
    if N == 100:
        #print('N es:',N)
        estamos_en_100 = True
        continue
    else:
        pasos_busqueda_exhaustiva += busqueda_exhaustiva_numero_pasos(N)
        pasos_busqueda_binaria += busqueda_binaria_numero_pasos(N)
    simulaciones_efectivas += 1

media_exhaustiva = pasos_busqueda_exhaustiva/simulaciones_efectivas
media_binaria = pasos_busqueda_binaria/simulaciones_efectivas

print('Media de pasos en búsqueda exhaustiva: ',media_exhaustiva)
print('Media de pasos en búsqueda binaria: ',media_binaria)
print('Tenemos', simulaciones_efectivas, 'simulaciones')
#print(enes[:-1])
Media de pasos en búsqueda exhaustiva:  50.50353892821031
Media de pasos en búsqueda binaria:  4.673407482305359
Tenemos 989 simulaciones

Observación:

Hay un problema con el número \(100,\) \(N = 100.\) En ese caso la búsqueda binaria no funciona, porque la operación:

\[\text{n} = \text{int}((\text{limSup} + \text{limInf})/2)\]

cuando \(\textrm{limSup} = 100\) y \(\textrm{limInf} = 99,\) implica que \(n = 99,\) por tanto nunca se podrá elegir \(100\) en el caso de este sea el valor seleccionado por la máquina. Por esta razón hemos eliminado el valor \(100,\) en caso de que salga.

Raíz cuadrada

Las siguientes funciones cuentan el número de pasos para calcular la raíz cuadrada de un número con una precisón de \(0.001\) y un paso de \(0.0001\)

def raiz_cuadrada_exhaustiva(N):
    precision = 0.001
    paso = 0.0001
    prueba = 1
    contador = 0
    señal = False

    while abs(prueba**2-N) >= precision:
        if prueba**2 > N + precision:
            señal = True
            break       
        prueba +=paso
        contador+=1
    if señal:
        print('Nos hemos pasado')
    else:
        print('Pasos con la búsqueda exhaustiva:  ', contador)  

def raiz_cuadrada_binaria(N):
    precision = 0.001

    menor = 1
    mayor = N
    prueba = (menor + mayor)/2
    contador = 0

    while abs(prueba**2 - N) >= precision:
        if prueba**2 > N:
            mayor = prueba
        else:
            menor = prueba
        prueba =(menor + mayor)/2
        contador += 1
    print('Pasos con la búsqueda binaria:  ', contador)

raiz_cuadrada_exhaustiva(125)
raiz_cuadrada_binaria(125)
Pasos con la búsqueda exhaustiva:   101803
Pasos con la búsqueda binaria:   20

Hemos pasado de 101803 iteraciones en la búsqueda exhaustiva a 20 en la búsqueda binaria. Uno puede pensar que esto es un ejemplo concreto, pero si repetimos este procedimiento para todos los números entre el 100 y el 125 veremos que se repite este resultado.

def raiz_cuadrada_exhaustiva(N):
    precision = 0.001
    paso = 0.0001
    prueba = 1
    contador = 0
    señal = False

    while abs(prueba**2 - N) >= precision:
        if prueba**2 > N + precision:
            señal = True
            break       
        prueba += paso
        contador += 1
    return contador 

def raiz_cuadrada_binaria(N):
    precision = 0.001

    menor = 1
    mayor = N
    prueba = (menor + mayor)/2
    contador = 0

    while abs(prueba**2 - N) >= precision:
        if prueba**2 > N:
            mayor = prueba
        else:
            menor = prueba
        prueba = (menor + mayor)/2
        contador += 1
    return contador


pasos_busqueda_exhaustiva = 0
pasos_busqueda_binaria = 0
numero_pruebas = 25

for s in range(100,100 + numero_pruebas):
    pasos_busqueda_exhaustiva += raiz_cuadrada_exhaustiva(s)
    pasos_busqueda_binaria += raiz_cuadrada_binaria(s)

media_raiz_cuadrada_exhaustiva = pasos_busqueda_exhaustiva/numero_pruebas
media_raiz_cuadrada_binaria = pasos_busqueda_binaria/numero_pruebas
print('Media iteraciones en la búsqueda exhaustiva de la raíz: ',media_raiz_cuadrada_exhaustiva)
print('Media iteraciones en la búsqueda binaria de la raíz: ',media_raiz_cuadrada_binaria)
Media iteraciones en la búsqueda exhaustiva de la raíz:  95775.12
Media iteraciones en la búsqueda binaria de la raíz:  17.96

Observación: Como ya se ha indicado la búsqueda binaria en este caso mejora mucho la eficiencia del algoritmo. En el caso del cálculo de raices el algoritmo de Newton-Raphson mejora aún más esta eficiencia de la búsqueda binaria.

2.4.4. La búsqueda binaria: descripción#

La búsqueda binaria es un tipo de búsqueda rápida que puede realizarse en conjuntos ordenados.

Si buscamos un elemento en un conjunto ordenado, dividimos el conjunto en dos partes (iguales) y conservamos aquella mitad donde podría encontrarse el elemento buscado. Volvemos a repetir este proceso con la mitad seleccionada y continuamos hasta encontrar el valor buscado.

Ejemplo Supongamos que tenemos un conjunto de cajas

\[\{ \square_1, \square_2,\square_3,\square_4,\square_5,\square_6,\square_7,\square_8 \}.\]

Las cajas contienen los números

\[\{ 1,2,3,5,6,8,11,15\},\]

en ese orden, pero no lo sabemos antes de abrirlas. El problema consiste en determinar si el número \(3\) está en alguna de las cajas.

Algoritmo Si dividimos el conjunto de cajas en dos partes (de igual tamaño)

\[\{\square_1, \square_2,\square_3,\square_4\}, \quad \{ \square_5, \square_6,\square_7,\square_8\},\]

el \(3\) estará en alguna de ellas.

Abrimos una de las cajas centrales:

\[ \square_5 = 6\]

Como \(3 < 6\), el \(3\) debe estar en la mitad izquierda (si está). Debemos buscar por ello en

\[\{\square_1, \square_2,\square_3,\square_4\}.\]

Repetimos el proceso:

\[\square_2 = 2\]

por lo que continuamos buscando en

\[\{\square_3, \square_4\}.\]

Una vez más

\[\square_4 = 2\]

por lo que continuamos buscando en

\[\{\square_3\}.\]

Y por último, abrimos la última caja:

\[\square_3=3\]

y comprobamos que \(3\) sí está en el conjunto, precisamente en la tercera caja.

Observaciones:

  • Si en el último paso obtenemos un número diferente de \(3\), entonces \(3\) no formaría parte del conjunto. Hay dos problemas posibles: averiguar si \(3\) está en el conjunto y averiguar en que caja está.

  • Como en cada paso se reduce el número de elementos a la mitad, el algoritmo termina un número finito de pasos. Si el conjunto donde buscamos tiene \(N\) cajas, serán necesarios \(\log_2N\) pasos (en el peor escenario).

  • La búsqueda exhaustiva (lineal) sería diferentes. Consistiría en ir abriendo las cajas \(\square_1\), \(\square_2\), \(\dots\) en ese orden hasta encontrar (o no) el número buscado. En este caso serán necesarios \(N\) pasos (en el peor escenario).

  • La búsqueda binaria es más rápida pero exige que los números contenidos en las cajas estén ordenados. Esta condición es restrictiva.

2.4.5. Más detalles de la comparación de la búsqueda exhaustiva y la búsqueda binaria en la obtención de la raíz cuadrada#

Vamos a ver más detalles de la comparación de la eficiencia de ambos algoritmos en la búsqueda de la raíz cuadrada de un número mayor que uno.

Vamos a hallar, computacionalmente, la raíz cuadrada de un número, \(N\), suponiendo que no disponemos de la operación elevar a 1/2 y a comparar el comprtamiento de estos dos algoritmos en este caso particular.

Sea \(N\) un número mayor que \(1\) cualquiera (tipo float). Estamos buscando un número \(r\) tal que \(r=\sqrt[2]{N}\), es decir, \(r^2=N\). Pero ya hemos visto que esta condición a veces es imposible de probar usando variables de tipo float y el operador ==. Por ejemplo, si \(N=3\):

N=3
raiz = N**(1/2)
raiz,raiz**2,N,raiz**2 == N
(1.7320508075688772, 2.9999999999999996, 3, False)

Es necesario usar el concepto de precisión. Diremos que un número \(r\) es la raíz cuadrada de \(N\) con precisión \(\varepsilon\) si

\[ \left|r^2-N\right|<\varepsilon,\qquad \varepsilon>0. \]

Dicho de otro modo, \(r\) no será la raíz cuadrada de \(N\) si \(|r^2-N|\geq \varepsilon\), para una precisón \(\varepsilon>0\) dada.

Solamente queda decidir qué números \(r\) probaremos.

Sabemos que se verifica que si \(x>1\) entonces \(1<x<x^2\) (la raíz cuadrada de un número mayor que 1 es mayor que uno y menor que dicho número). entonces un buen candidato para comenzar a buscar la raíz de un número \(N\) mayor que 1 es \(r=1\). Si resulta que \(|r^2-N|\geq\varepsilon\) entonces procederemos a incrementar el valor de \(r\) y probar de nuevo. El tamaño del incremento lo llamaremos paso.

Ejemplo

Buscamos \(\sqrt[2]{2}\cong 1.4140\) con una precisión de \(\varepsilon=0.05\). Si nuestra prueba inicial es \(r=1\) y el paso es 0.05, entonces las iteraciones serán:

2**(1/2)
1.4142135623730951
N=3
precision = 0.05
paso = 0.01
prueba = 1
contador = 0

print('prueba','\t\t\t','abs(prueba**2-N)')
print(prueba,'\t\t\t',abs(prueba**2-N))

while abs(prueba**2-N)>=precision:
    prueba +=paso
    contador+=1
    print(prueba,'\t\t\t',abs(prueba**2-N))
    
print('Hemos necesitado: ',contador,' iteraciones.')
print('El candidato a raíz cuadrada es: ',prueba)
    
prueba 			 abs(prueba**2-N)
1 			 2
1.01 			 1.9799
1.02 			 1.9596
1.03 			 1.9391
1.04 			 1.9183999999999999
1.05 			 1.8975
1.06 			 1.8763999999999998
1.07 			 1.8551
1.08 			 1.8336
1.09 			 1.8118999999999998
1.1 			 1.7899999999999998
1.11 			 1.7678999999999998
1.12 			 1.7455999999999998
1.1300000000000001 			 1.7230999999999996
1.1400000000000001 			 1.7003999999999997
1.1500000000000001 			 1.6774999999999998
1.1600000000000001 			 1.6543999999999996
1.1700000000000002 			 1.6310999999999996
1.1800000000000002 			 1.6075999999999997
1.1900000000000002 			 1.5838999999999996
1.2000000000000002 			 1.5599999999999996
1.2100000000000002 			 1.5358999999999996
1.2200000000000002 			 1.5115999999999996
1.2300000000000002 			 1.4870999999999994
1.2400000000000002 			 1.4623999999999995
1.2500000000000002 			 1.4374999999999993
1.2600000000000002 			 1.4123999999999994
1.2700000000000002 			 1.3870999999999993
1.2800000000000002 			 1.3615999999999993
1.2900000000000003 			 1.3358999999999994
1.3000000000000003 			 1.3099999999999994
1.3100000000000003 			 1.2838999999999994
1.3200000000000003 			 1.2575999999999992
1.3300000000000003 			 1.2310999999999992
1.3400000000000003 			 1.2043999999999992
1.3500000000000003 			 1.177499999999999
1.3600000000000003 			 1.1503999999999992
1.3700000000000003 			 1.123099999999999
1.3800000000000003 			 1.095599999999999
1.3900000000000003 			 1.067899999999999
1.4000000000000004 			 1.039999999999999
1.4100000000000004 			 1.011899999999999
1.4200000000000004 			 0.9835999999999991
1.4300000000000004 			 0.955099999999999
1.4400000000000004 			 0.9263999999999988
1.4500000000000004 			 0.8974999999999986
1.4600000000000004 			 0.868399999999999
1.4700000000000004 			 0.8390999999999988
1.4800000000000004 			 0.8095999999999988
1.4900000000000004 			 0.7798999999999987
1.5000000000000004 			 0.7499999999999987
1.5100000000000005 			 0.7198999999999987
1.5200000000000005 			 0.6895999999999987
1.5300000000000005 			 0.6590999999999987
1.5400000000000005 			 0.6283999999999987
1.5500000000000005 			 0.5974999999999984
1.5600000000000005 			 0.5663999999999985
1.5700000000000005 			 0.5350999999999986
1.5800000000000005 			 0.5035999999999983
1.5900000000000005 			 0.47189999999999843
1.6000000000000005 			 0.43999999999999817
1.6100000000000005 			 0.4078999999999984
1.6200000000000006 			 0.37559999999999816
1.6300000000000006 			 0.34309999999999796
1.6400000000000006 			 0.31039999999999823
1.6500000000000006 			 0.2774999999999981
1.6600000000000006 			 0.24439999999999795
1.6700000000000006 			 0.21109999999999784
1.6800000000000006 			 0.17759999999999776
1.6900000000000006 			 0.14389999999999814
1.7000000000000006 			 0.1099999999999981
1.7100000000000006 			 0.07589999999999764
1.7200000000000006 			 0.04159999999999764
Hemos necesitado:  72  iteraciones.
El candidato a raíz cuadrada es:  1.7200000000000006

Podemos aumentar la precisión, pero necesitaremos más pasos.

Este procedimiento tiene un peligro: si usamos el mismo ejemplo que antes, pero el paso es muy grande, o la precisión muy pequeña, podemos pasarnos de largo y continuar iterando sin fin; puede suceder que entremos en un bucle infinito.

N=3
precision = 0.01
paso = 0.1
prueba = 1
contador = 0

print('prueba','\t\t\t','abs(prueba**2-N)')
print(prueba,'\t\t\t',abs(prueba**2-N))

while abs(prueba**2-N)>=precision:
    prueba +=paso
    contador+=1
    print(prueba,'\t\t\t',abs(prueba**2-N))
    if contador >20:
        break
prueba 			 abs(prueba**2-N)
1 			 2
1.1 			 1.7899999999999998
1.2000000000000002 			 1.5599999999999996
1.3000000000000003 			 1.3099999999999994
1.4000000000000004 			 1.039999999999999
1.5000000000000004 			 0.7499999999999987
1.6000000000000005 			 0.43999999999999817
1.7000000000000006 			 0.1099999999999981
1.8000000000000007 			 0.24000000000000243
1.9000000000000008 			 0.610000000000003
2.000000000000001 			 1.0000000000000036
2.100000000000001 			 1.4100000000000037
2.200000000000001 			 1.8400000000000043
2.300000000000001 			 2.2900000000000054
2.4000000000000012 			 2.760000000000006
2.5000000000000013 			 3.250000000000006
2.6000000000000014 			 3.760000000000008
2.7000000000000015 			 4.290000000000008
2.8000000000000016 			 4.840000000000009
2.9000000000000017 			 5.410000000000009
3.0000000000000018 			 6.000000000000011
3.100000000000002 			 6.610000000000012

Es necesario poner una condición de parada. En el programa anterior hemos puesto la condición que el número de iteraciones del bucle sea, como mucho, 20. Observamos que con ese número de iteraciones ya hemos llegado a probar números mayores que 3 como candidatos a raíz cuadrada de 3, lo cual es una tontería. Ya hemos visto antes que la raíz cuadrada de un número mayor que uno será menor que dicho número.

También puede suceder lo contrario: puede suceder que 20 iteraciones no sean suficientes para alcanzar la raíz cuadrada. Por ejemplo, usando el ejemplo anterior, si \(N=25,\) se obtiene:

N=25
precision = 0.01
paso = 0.04
prueba = 1
contador = 0

print('prueba','\t\t\t','abs(prueba**2-N)')
print(prueba,'\t\t\t',abs(prueba**2-N))

while abs(prueba**2-N)>=precision:
    prueba +=paso
    contador+=1
    print(prueba,'\t\t\t',abs(prueba**2-N))
    if contador > 20:
        break
prueba 			 abs(prueba**2-N)
1 			 24
1.04 			 23.9184
1.08 			 23.8336
1.12 			 23.7456
1.1600000000000001 			 23.6544
1.2000000000000002 			 23.56
1.2400000000000002 			 23.4624
1.2800000000000002 			 23.3616
1.3200000000000003 			 23.2576
1.3600000000000003 			 23.150399999999998
1.4000000000000004 			 23.04
1.4400000000000004 			 22.926399999999997
1.4800000000000004 			 22.8096
1.5200000000000005 			 22.6896
1.5600000000000005 			 22.566399999999998
1.6000000000000005 			 22.439999999999998
1.6400000000000006 			 22.310399999999998
1.6800000000000006 			 22.177599999999998
1.7200000000000006 			 22.0416
1.7600000000000007 			 21.902399999999997
1.8000000000000007 			 21.759999999999998
1.8400000000000007 			 21.614399999999996

Conclusión: La condición de fijar un número máximo a la cantidad de iteraciones no es buena. Necesitamos otra condición. Pensando en el ejemplo anterior (\(N=3\)) una primera idea sería que si llegamos a un valor de prueba tal que \(prueba>N\) entonces deberíamos parar. En ese caso no habríamos encontrado la raíz cúbica de \(N\) para los valores de paso y precisión usados; deberíamos cambiarlos para obtener un resultado.

Pero esta opción es poco informativa y se puede mejorar. Pararemos el bucle si \(prueba^2>N\). En ese caso, al terminar el bucle sin haber hallado un buen candidato para la raíz de \(N,\) podremos comenzar de nuevo el proceso con un valor cercano al último valor de prueba obtenido, modificando los valores de paso y precisión.

N=3
precision = 0.01
paso = 0.01
prueba = 1
contador = 0
señal = False

while abs(prueba**2-N)>=precision:

    if prueba**2>N or contador >10**6:
        señal = True
        break
    
    prueba +=paso
    contador+=1

if señal:
    print('Nos hemos pasado. El último valor probado es: ',prueba)
else:
    print('La raíz cuadrada de ',N,' es ',prueba, 'con una precisión ',precision)
print('Hemos dado: ',contador,' iteraciones.')
La raíz cuadrada de  3  es  1.7300000000000006 con una precisión  0.01
Hemos dado:  73  iteraciones.
N=3
precision = 0.01
paso = 0.001
prueba = 1
contador = 0
señal = False

while abs(prueba**2-N)>=precision:

    #print(prueba,'\t\t\t',abs(prueba**2-N))
    if prueba**2 > N or contador > 10**6:
        señal = True
        break
    
    prueba += paso
    contador += 1

if señal:
    print('Nos hemos pasado. El último valor probado es: ',prueba)
else:
    print('La raíz cuadrada de ',N,' es ',prueba, 'con una precisión ',precision)
print('Hemos dado: ',contador,' iteraciones.')
La raíz cuadrada de  3  es  1.7299999999999196 con una precisión  0.01
Hemos dado:  730  iteraciones.

En el programa anterior hemos usado una variable semáfor0 (flag) que nos indica si nos hemos pasado o no. En función del valor del semáforo mostraremos un mensaje u otro.

Observamos que disminuyendo el paso son necesarias muchas más iteraciones para obtener el resultado. Esto es obvio, ya que vamos avanzando con pasos más pequeños y necesitaremos más para llegar al valor de parada. Si usamos un valor de \(N\) más grande:

N=389
precision = 0.001
paso = 0.00001
prueba = 1
contador = 0
señal = False

while abs(prueba**2-N)>=precision:

    #print(prueba,'\t\t\t',abs(prueba**2-N))
    if prueba**2 > N or contador > 10**6:
        señal = True
        break
    
    prueba += paso
    contador += 1

if señal:
    print('Nos hemos pasado. El último valor probado es: ',prueba)
else:
    print('La raíz cuadrada de ',N,' es ',prueba, 'con una precisión ',precision)
print('Hemos dado: ',contador,' iteraciones.')
Nos hemos pasado. El último valor probado es:  11.00000999975465
Hemos dado:  1000001  iteraciones.

2.4.6. Ejercicios#

  1. Obtener la raíz cúbica de un número no negativo menor que \(1.\)

  2. Obtener la raíz cúbica de un número arbitrario.