開根號演算法

(本篇文章利用Python實作)

本文要介紹基本的演算法概念
以及利用二元搜索法(binary search algorithm)來實作開根號演算法

算法（算法），在數學（算學）和電腦科學之中，為任何良定義的具體計算步驟的一個序列，常用於計算，數據處理和自動推理。精確而言，算法是一個表示為有限長列表的有效方法。算法應包含清晰定義的指令用於計算函數。
(以上文字截自維基百科)

我來替各位簡單翻譯
以我的觀點 演算法即是一個利用程式語言定義解決問題的過程
以今天的標題為例
即是希望給定一個輸入值
經過演算法後
得到該值的平方根

所以開始今天的主題吧！

本次的主題是利用二元搜索法尋找數值的開根號
首先介紹何謂二元搜索法
https://zh.wikipedia.org/wiki/二分搜索算法
簡言之 就是利用不斷的切半來近似答案
那要怎麼利用這個方式算平方根呢？

假定輸入的值為a
而先預設a=5
則 0 < a < a^2 必會成立
也就是 0 < 5 < 25
接著帶入另一個概念 上下界線
在這個式子中 上界=a 下界=0
因此我們要開始不斷縮小上下界線(找尋上下界平均數)來逼近答案

首先 5-0 = 5
5/2 = 2.5
2.5^2 = 6.25
6.25仍大於5
因此2.5依然大於5的開根號 上界變為2.5

再將2.5除以2
1.25^2 = 1.5625
這時5>1.5625 下界則提升成1.5625

不斷利用這種方式迭代
就可以逼近出很相近的答案囉
而知道了做法後
讓我們一起把利用python實做出來吧

input_num = float(input("請輸入一個正數:"))

首先利用input函數來輸入值
而正規化的輸入輸出又是另一門課了
有機會再寫一篇跟大家聊聊吧
而輸入的值都是字串
因此要先轉成浮點數

while input_num<0:
    input_num = float(input("請輸入一個正數: "))

這邊我做了一個簡單的除錯
由於開平方根輸入的值要是正數
因此輸入負數需要重新輸入

upper = input_num
lower = 0
epsilon = upper-lower

而這個則是設定上下界

while epsilon>0.00001:
    new_limit = (upper+lower)/2
    if new_limit**2>input_num:
        upper = new_limit
        epsilon = upper-lower
    elif new_limit**2<input_num:
        lower = new_limit
        epsilon = upper-lower
    else:
        break

這段實在無法拆開來講
一開始設定一個迭代條件
也就是開根號後可以接受的誤差(上下界差距)有多大
這邊是到小數點後第五位

接著便開始上面所講的迭代方式
藉著更新上下界決定新的epsilon找最接近的值
誤差到了可以接受的範圍就結束迴圈

print("square root of ", input_num, '=', round(new_limit, 5))

接著就可以將答案印出來啦

可以拿計算機驗算一下哈哈

在完成這個問題後
留下兩個小彩蛋給各位
第一、其實這個演算法有重大的缺陷 有發現的可以在底下留言
第二、可以實作看看開立方根的 只要改一點點地方就行囉
我將我的程式碼附在底下
有興趣的同學可以參考看看

input_num = float(input("請輸入一個數:"))

if input_num<0:
    input_num = -input_num
    upper = input_num
    lower = 0
    epsilon = upper-lower
    
    while epsilon>0.00001:
        new_limit = (upper+lower)/2
        if new_limit**3>input_num:
            upper = new_limit
            epsilon = upper-lower
        elif new_limit**3<input_num:
            lower = new_limit
            epsilon = upper-lower
        else:
            break

    print("square root of", input_num, '=', -round(new_limit, 5))
    
elif input_num>0:
    upper = input_num
    lower = 0
    epsilon = upper-lower
    
    while epsilon>0.00001:
        new_limit = (upper+lower)/2
        if new_limit**3>input_num:
            upper = new_limit
            epsilon = upper-lower
        elif new_limit**3<input_num:
            lower = new_limit
            epsilon = upper-lower
        else:
            break

    print("square root of", input_num, '=', round(new_limit, 5))
    
else:
    print("square root of", input_num, '=', 0)

所以今天學到的有：
了解何為演算法
利用二元搜尋法實作開根號演算法

未來會繼續分享各種實例給大家囉~