谷 峰

(浙江經(jīng)濟(jì)職業(yè)技術(shù)學(xué)院，浙江 杭州 310018)

在高級(jí)計(jì)算系統(tǒng)中，可以很容易地找到Bernstein多項(xiàng)式的算法[3]。 例如 ，在 Mathematica中 ，(t)可以用BernsteinBasis[n，i，t]計(jì)算。用高級(jí)語(yǔ)言編程計(jì)算 Bernstein多項(xiàng)式也非常容易。本文討論如何在基本計(jì)算系統(tǒng)(僅具備移位、加和邏輯運(yùn)算功能的計(jì)算系統(tǒng))中計(jì)算Bernstein多項(xiàng)式?；居?jì)算系統(tǒng)存在于許多系統(tǒng)中，例如工業(yè)控制系統(tǒng)、軍事應(yīng)用系統(tǒng)、醫(yī)療應(yīng)用系統(tǒng)等。典型的有單片機(jī)系統(tǒng)和FPGA(Field Programmable Gate Arrays)等。

CORDIC算法是可計(jì)算多種基本初等函數(shù)的移位-加算法[4-6]。參考文獻(xiàn)[7-8]擴(kuò)展了CORDIC算法，其收斂性和誤差估計(jì)在參考文獻(xiàn)[7]中做了分析。隨著硬件技術(shù)的發(fā)展，這些快速統(tǒng)一移位-加算法可以用硬件實(shí)現(xiàn)，而且不需使用乘法器[9]，成本較低，也可以用匯編語(yǔ)言編程實(shí)現(xiàn)。本文提出一個(gè)基于CORDIC算法的Bernstein多項(xiàng)式移位-加算法。

1 算法的描述

[7]中定義了符號(hào)函數(shù)和正規(guī)序列：

設(shè)ε為誤差上界。Bernstein多項(xiàng)式的移位-加算法包含一個(gè)主程序和一個(gè)子程序：

注：(1)算法中僅使用了移位運(yùn)算(即 2-i×t)和加法運(yùn)算。

(2)迭代次數(shù)N根據(jù)后面的定理1確定。

(4)計(jì)算實(shí)踐表明子程序運(yùn)行的迭代次數(shù)一般不超過(guò)28步，因此是個(gè)快速算法。

2 算法的收斂性和誤差分析

當(dāng) n充分大時(shí)，有 xn+1≈x，zn+1≈xy。

subprogram UV(u，v，ε)即基于迭代過(guò)程(1)。

(1)迭代過(guò)程(1)中的{xi}收斂于 x，且有|x-xN|≤δN-1。

(2)迭代過(guò)程(1)中的{zi}收斂于xy，且有誤差估計(jì)|zN-xy|≤|y|(1+|x|)(1+δN)δN。

(3)subprogram UV(u，v，ε)中的{zi}收斂于 xy，其計(jì)算誤差不大于ε。

(3)當(dāng)u=0或v=0時(shí)，程序輸出結(jié)果 uv=0。當(dāng)uv≠0時(shí)，u 和 v 在 subprogram UV(u，v，ε)中預(yù)處理為 uv=s×2m×u1v1。 這里 s為 1 或-1。u1和 v1在(0，1]中。 由(2)，計(jì)算結(jié)果 z′N(xiāo)有|z′N(xiāo)-u1v1|＜|u1|(1+|v1|)·δN-1≤2δN-1＜δN-2；迭代次數(shù) N 滿足δN-2≤2-m×ε。 所以最終結(jié)果 zN=s×2m×z′N(xiāo)滿足|zN-uv|＜2m×δN-2≤ε。 證畢。定理 2 主程序 Bernstein(n，t，ε)的輸出值 Bn

j(t)(j=0，…，n)是n次Bernstein多項(xiàng)式的計(jì)算值。計(jì)算誤差上界是ε。

3 數(shù)值實(shí)驗(yàn)

給定誤差上界ε=0.000 000 5，用本文給出的算法計(jì)算三次Bernstein多項(xiàng)式(t)(j=0，1，2，3)的數(shù)值。 計(jì)算值見(jiàn)表 1。 subprogram UV(u，v，ε)中的迭代次數(shù)不大于28。三次Bernstein多項(xiàng)式的函數(shù)值列表如表2所示。由此可見(jiàn)計(jì)算誤差符合要求。

參考文獻(xiàn)

[1]NATARAJ P S V，AROUNASSALAME M.A new subdivision algorithm forthe bernstein polynomialapproach to global optimization[J].International Journal of Automation and Computing， 2007，4(4):342-352.

[2]FARIN G.Curves and surfaces for computer-aided geometric design:a practical guide， 4th Ed.Academic Press， San Diego，1997.

[3]FENG Jieqing，PENG Qunsheng.Fast algorithm for composition of the bernstein polynomials[J].Journal of Computer-Aided Design&Computer Graophics， 2001，13(2).

[4]VOLDER J E.The CORDIC computing technique[J].IRE Transactions on Electronic Computers， 1959，8(9):330-334.

[5]MULLER J M.Elementary functions，algorithms and implementation.BirkhauserBoston， 1stedition，1997.2nd edition，2006:133-156.

[6]EKLUND N.CORDIC:elementary function computation using recursive sequences [C].InternationalConference on Technology，1998.

[7]GU Feng.Convergence and error estimation of coordinate rotating algorithm and its expansion[J].Chinese Journal of Numerical Mathematics and Applications， 2006，28(2):1-9.

[8]HU Xiaobo， HARBER R， BASS S.Expanding the range of convergence of the CORDIC algorithm[J].IEEE Transactions on Computers， 1991，40(1):13-21.

[9]ANDRAKA R.A survey of CORDIC algorithms for FPGA based computers[C].In Proceedings of the 1998 ACM/SIGDA Sixth International Symposium on Field Programmable Gate Arrays(FPGA)1998:191-200.

表1 三次Bernstein多項(xiàng)式的計(jì)算值

表2 三次Bernstein多項(xiàng)式的函數(shù)值