-
1 # 雄姿英發5048
-
2 # 帖木兒
初中時老爺子出過這題讓我獨立解決。本身不難,只是(a+b)²=a²+b²+2ab的一個簡單應用,很容易找到類似短除法的方法。
上大學時我曾重新考慮過這個問題,因為一般的短除法在我看來還是有點麻煩。我首先想到這個“麻煩”主要是十進位制造成的,而數學運算本身跟進位制無關,所以應該選擇一個更“友好”的進位制。
顯然,是二進位制。此時每一步只需要決定下一位是0還是1,運算變成極其簡單的比大小:
計算(二進位制表示的)√aₙ…a₁a₀.b₀b₁…
1. 以小數點為界,把整數部分(aₓ)和小數部分(bₓ)每兩位分成一段段(也可以理解為四進位制),每一段有00,01,10,11四個可能。
2. 初始化狀態:
當前已計算的平方根:S=0
當前餘數:R=0
當然遊標:最高位段
3. 計算平方根的下一位(二進位制):當餘數R<S或R=S且當前段為00時,平方根的下一位是t=0,否則t=1
4. 更新狀態:
將當前段D(i)拼在餘數尾部:R={R,D(i)}
如果3的結果t=1,則R=R-{S,01}
把t拼在平方根尾部:S={S,t}
遊標前進至下一段
5. 跳回3開始重複,直至除盡,迴圈,或達到精度要求。
舉例:計算√20.25,轉為二進位制√1 01 00.01
整數部分分段:01,01,00,小數部分:01
初始:S=0,R=0。
第一位:S=R且D=01,有t=1
更新:R={R,01}-{S,01}=01-01=0,S=1
第二位:S=1>0=R,有t=0
更新:R={R,01}=01,S={S,0}=10
第三位:S=10>01=R,有t=0
更新:R={R,00}=100,S={S,0}=100
至此整數部分完成,進入小數部分:
第一位小數:S=100=R且D=01,有t=1
更新:R={R,01}-{S,01}=0,S={S,1}=100.1
至此除盡,所以平方根為100.1,轉回十進位制即為:√20.25=4.5
畢業後從事晶片設計工作時,在GPU運算器設計時再次遇到這個問題。根據ic設計的特性,我採用了查表+泰勒級數插值的快速演算法。畢竟,為“人的手”最佳化還是為“機器的二極體”最佳化,演算法的目標是不同的。
回覆列表
運用乘法定理,2*2=4,3*3=9,13*13=169,然後將4、9、169開平方根得到2、3、13。需要充分了解乘法定理就能運用自如。
根號二可以使用計算器運算,結果開出來近似於1.4145926。
擴充套件資料:
平方根,又叫二次方根,表示為〔±√ ̄〕,其中屬於非負數的平方根稱之為算術平方根。一個正數有兩個實平方根,它們互為相反數;0只有一個平方根,就是0本身;負數有兩個共軛的純虛平方根。
一般地,“√ ̄”僅用來表示算術平方根,即非負數的非負平方根。例如:數學語言為:√ ̄16=4。語言描述為:根號16=4。