102年高考計算機概論第2題 - 高考

※ 引述《hash (hash)》之銘言：
: ※ 引述《letterstar (letterstar)》之銘言：
: : [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
: : 題目:給定一函數f(X)= (X^6)+ 2(x^4)- 5(X^2)+ 2X+ 1
: : 請提出最有效率計算方式計算f(X0),其中X0=
: : 1.23456789.
: : 註:一個參考計算過程(不見得為正確答案)如下
: : let a=1
: : loop i=1 to 6
: : compute a=a*x
: : end loop
: : let b =1
: : compute c = a+b
: : 我自己的想法:
: : 因為這多項式好像不能分解
: : 所以先求出X^2
: : 再求X^4 (上式平方)
: : 再求X^6 (X^2)*(X^4)
: : 這樣就只用三個乘法
: : 之後像是2X就可用SHIFT代替乘法
: : 然後算出F(X0)
: : 請問各位高手還有什麼更有效率的方法嗎?


整理一下各種答案
1.
((((((x^2+2)x^2)-5)x+2)x)+1
共使用4個乘法 4個加減法

2.
let x=1
let fx=0
let x0=1.23456789
let a[7]={1,2,-5,0,2,0,1}
loop i=1 to 6
compute x=x*x0
compute fx += a[i] * x
endloop
compute fx += a[0]
答案就是; fx

共使用6個乘法 6個加法

3.
先計算 X^2 1個乘法
X^4=(X^2)^2 2個乘法
X^6=(X^2)*(X^4) 3個乘法

2(x^4)定點數直接使用SHIFT 1BIT可得
浮點數直接使用位元加一

2X 定點數直接使用SHIFT 1BIT可得
浮點數直接使用位元加一

5(X^2)=4(X^2)+(X^2)
4(X^2)
定點數直接使用SHIFT 2BIT可得
浮點數直接使用位元加2

之後計算
(X^6)+ 2(x^4)- 4(X^2)-(X^2) + 2X+ 1
3次加法 2個減法

共使用3個乘法 5次加減法
3個SHIFT(或浮點數位元區加法)





--