2009年4月2日 星期四

使用加法做開根及平方計算

主題:使用加法做開根及平方計算
使用範圍:整數計算開根及平方,計算慢,gate count少
參考資料:MATH toolkit for Real-Time Programming by Jack W. Crenshaw CMP Books
原理說明:
這是我們常用的公式(n+1)^2=n^2+2*n+1
改寫為(n+1)^2=n^2+n+(n+1),其中n^2在上次計算可得到,所以只剩n及(n+1)且只使用加法就可以進行。
設計演算法為
a=Count
b=Last Sum= Sum
c=Sum=Last Sum+Count
d=Squart=Sum+Last Sum
排表為
a b  c d
 0  0   0  0
 1  0   1  1
 2  1   3  4
 3  3   6  9
 4  6   10 16
 5 10   15 25
若要取得平方,就將輸入做為計算的次數。計算停下來時,取出d就是答案。
要做開方,就將輸入和輸出比較,超過時停下來,取出a就是答案。
若要使用到小數,則使用定點數方式可以得到。