基于牛顿迭代法的高精度快速开方算法

第28卷第3期 2008年3月 电力自动化设备 ElectricPowerAutomationEquipment V01．28No．3 Mar．2008o 基于牛顿迭代法的高精度 快速开方算法 张小呜1，一，李永新1 (1．南京理工大学机械工程学院，江苏南京210094； 2．江苏工业学院计算机科学与x-4r--．Y_系，江苏常州213164) 摘要：针对全波傅氏算法中的开平方运算较耗时影响微机保护瞬动性问题，提出一种选取接近定 点数开方真值的牛顿迭代初值的方法。该方法利用数字信号处理器(DSP)的移位指令、256个单元 的查 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 技术和DSP的硬件乘法器，通过1次查表和1．2次乘法运算，就能快速确定迭代误差小于 2’9的迭代初值。在TIDSP集成开发平台上。运行牛顿迭代开平方汇编程序。运算结果表明：该算法 对范围在00000004．0000H～01FFFFFF．FFFFH的定点数抽样开方运算，迭代次数均不大于3次，就 达到2娟以上迭代精度．且占用内存小。非常适合带有硬件乘法器的嵌入式微处理器实现。 关键词：开平方；迭代；微机保护；DSP 中图分类号：TM744 文献标识码：A 文章编号：1006—6047(2008)03—0075—03 基于交流采样的微机保护测量算法中最常用的 是并联补偿全波傅氏算法[1】。该算法计算谐波幅值 时，要进行谐波实部平方和虚部平方的开平方运算。 因嵌入式微处理器无专门的开方指令。目前常见的开 平方算法主要有牛顿迭代(Newton．Raphson)算法[21 和逐位循环算法C3-6]。在微处理器应用场合，通常用 牛顿迭代法实现开方运算。牛顿迭代法每次产生1 个开方数．直到前后2次迭代的误差小于希望的精 度为止。若取固定的迭代初值且被开方数较大时， 迭代非常慢。一般10次以上才能达到精度。若迭代 初值越接近开方结果，则迭代收敛的速度越快[7．¨]。 这里研究了定点数直接牛顿迭代开方初值的快 速选定算法，减少牛顿迭代次数，提高定点数牛顿迭 代开方结果的速度．使定点数开方牛顿迭代快速算 法能充分发挥定点CPU快速处理定点数的优势。 1 被开方定点数数据格式定义 微机保护系统测量的电流、功率等变化范围较 大，为了达到较高的牛顿迭代开方精度1．5X10～，设 置被开方定点数数据格式为8Byte，其中6Byte(即 3个字)为整数部分，2Byte(即1个字)为小数部分， 小数点默认位置如图1所示。匡亟习望堕丑圈．区囹 图l被开方定点数数据格式 Fig．1Dataformatoffixed-pointnumberforevolution 因此，在牛顿迭代公式：X。l-(X。+A／X。)／2中， A／X。用64位除以32位除法子程序运算，保证每次 产生的32位商中，小数始终保持16位，以便迭代结 收稿日期：2007—03—06；修回日期：2007—05—10 束条件满足： 占=lXn+l-X。I≤2。16 (1) 2牛顿迭代初值选取新算法 假设具有图l数据格式的被开方数A最大为 1FFFFFF．FFFFH．用下列二进制通式表示： A=口。a，l⋯alao．口一la一2⋯口一m+l口一。、(2) 将式(2)展开为以2为底的权展开和形式[12】： A=口。×28+Ⅱn一1x28—1+⋯+口lx21+口o×20+口一l×2—1+ a一2×2—2+⋯+n—m+1×2一刖。1+口一m×2一肌(3) 其中，O≤乃≤24，1≤m≤16，口。=‘0’或‘1’，口。= ‘0’或‘l’。 将式(3)中最高含‘1'的二进制位数n的权力作为 公因子提到公式最左边．即在a。=‘1’的情况下，有 A=2”×(1+口。1×2-1+⋯+o】×2—4“+口o×2一“+口一1× 2—1一“+口一2x2-2-n+⋯+口一，¨l×2-m+1-n+口一。×2—“4) 、／万一=2n／2×(1+口。一lx2—1+⋯+口lx2-n+I+ aox2咄+Q一1x2-I-n+口一2x2-2-n+⋯+ 口一。+l×2一”+1一”+口一。×2一”””)172 (4) 从公式(4)可看出，、／丁的值由2个乘积项组 成，若牛顿迭代初值仅取第1项2n／2试验表明，迭 代次数不大于5次．若考虑第l项2“／2与第2项的乘 积作为迭代初值，则迭代次数会进一步减少。但是， 第2项是一个开方运算。不能再用牛顿迭代法计算， 可以用查表法解决开方问题。考虑最大的开方数 aM=‘1’，则第2项的小数部分最大有23项，如果完 全把这些数E[1．0，1．999)的开方运算均采用查表求 解．则需要存放查表数据的内存字单元223=8M．不 仅占用内存资源太大，而且开方运算蜕变为完全查 表法，若用嵌入式系统实现，其性价比很差。考虑到 牛顿迭代初值选取较接近开方真值时，收敛速度较 万方数据 。 电力自动化设备 第28卷 快．取小数部分的最高8位就能进一步加快收敛速 度．即第2项近似取值为 V1+口。l×2-1+⋯+口。一s×2—8(7) 其中，a。一。到a棚是最高含‘1’的二进制位数乃 向右从高到低截取的8位。至此，提出牛顿迭代初 值选定新算法的实现步骤。 a．检测被开方数A整数部分含‘l’的最高位， 记录该位的位长。记为n(从0开始计数)。 b．截取含‘1’的最高位右边的8位数，记为厂o c．将从a得到的含‘l’的最高位的位长n除以 2所得商．该商数是该位以2为基底的权的开方数 的幂次方数，若该位长n(=2k)是偶数，直接将该商 数作为2的幂次方数转换成一个单字的二进制数， 即2‘；若该位长几(=2k+1)是奇数，则该商数作为2 的幂次方数转换成一个单字的二进制数后，再乘以 、／丁。即2kx、／丁的乘积取整为单字。 正将从b得到的8位小数厂’去查1．厂对应的开 方数表格，获得1．厂的16位开方数，其中高8位整数， 低8位小数。 e．将从d得到的开方结果单字与从c得到的整 数单字相乘．得到32位乘积。该乘积就是牛顿迭代 开方较精确的迭代初值。 注意：b截取含‘1’的最高位右边的8位时，若 位长不足8位，则应顺序截取到被开方数的16位小 数部分。 3牛顿迭代初值误差 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 牛顿迭代初值误差6(截取误差)定义为 6=(1+口plx2—1+⋯+ol×2一“+1+口ox2—4+口一l×2—1—4+ a一2×2-2-+4-⋯+口一m+lx2一m+1咄+口一m×2一”卜8)1／2一 (1+口肛I×2—1+⋯+口肛8×2—8)172 X=l+2—1+⋯+2—8．Y=2—9+⋯+2—1“4 则 6=V霸了一、／可=[(、／丽一、／i)z]1／2= 、／i、／丽=(1+Y／X)1／2x= f1+y／(2x)]“2X= [X+Y／2-Y2／(8X)](9) 其中，(I+Y／X)1／2按泰勒级数展开，由于l，《1， 故(I+Y／X)忱一1+Y／(2X)-YV(8X2)代入式(9)得到。 将式(9)代人式(8)，得到：’ 6=2X+Y-2卜手一盖])l／2=赤㈣， 因为X=1+2—1+⋯+2一，故1≤、／x≤1．412，最大 截取误差6≤Y／2≤(1／2)(1／28)=1／29=1．95×104。 由此可见．牛顿迭代初值的选取值与开方真值的 误差小于等于1．95x10—3．因此．要求牛顿迭代精度 不大于1．5×10～，只需迭代次数不超过3次，就能达 到精度要求。 4试验结果 在TIDSP集成开发平台CCS2．2及TMS320LF 2407实验装置上．运行基于TMS320C2XXDSP汇编 指令编写的牛顿迭代开方子程序，用牛顿迭代初值 选取新算法进行开方数运算试验，抽样运算结果见 表1．在00000004．0000H～01FFFFFF．FFFFH数值 开方范围内。抽样数开方结果迭代精度达到2—6 以上的迭代次数均不大于3次。 对于范围在0000．8000H一0003．FFFFH的小定 点数开方，迭代精度仍保持不变，但迭代次数出现超 过3次的情况．这是因为所编写的定点数多字节除法 子程序在对小于4的数进行除法时，由于被除数放大 的倍数有限。产生的商数精度有所下降所致。对于 微机保护而言。当用输入电压量程为0—5V的10 位A／D转换器对电流信号采样，量化成的数字量 在4以下时，相当于0．02V以下的模拟电压采样。占 满量程的l％以下，完全不在微机保护范围内，故本 算法在较大交流信号幅值范围内，满足高精度、快速 (2x+y一2订、／iaF)1／2 (8) 开方的要求。 表l牛顿迭代初值选取新算法迭代次数试验 Tab．1Iterationtimesandpreeisionsof8cIuareroot operationusinginitialvalueselectionalgorithm 万方数据 第3期 张小鸣，等：基于牛顿迭代法的高精度快速开方算法 啷 J^ 5结语 所介绍的定点数开方新算法是一种结合256个 字单元查表和DSP硬件乘法器快速确定接近开方 真值的迭代初值的牛顿迭代开方算法。DSP芯片具 有专用的单周期查表指令TBLR、单周期16位乘法 指令MPYU等快速指令。使这种算法可充分利用 DSP的软硬件资源，达到快速选取迭代初值的目的。 DSP仿真试验表明：在所规定的开平方数值范围内， 无论被开方数大小，迭代次数总是小于等于3次，就 能达到2一e以上的开方精度．比取固定初值的牛顿 迭代开方运算速度平均提高约3倍，且软硬件开销 很小．尤其适合带有16位以上硬件乘法器的嵌入式 微处理器实现。可满足微机保护中全波傅氏算法开 方运算的实时性要求。具有良好的工程应用价值。 参考文献： [1]李晨，张杭，张爱民，等．一种能滤除衰减直流分量的新递推离散 傅氏算法[J]．继电器，2005，33(17)：17—20． LIChen，ZHANGHang，ZHANGAimin，eta1．Arecursivedis— creteFourieralgorithmforfilteringdecayingDCcomponent[J]． Relay．2005，33(17)：17—20． [2]孙志忠。袁慰平，闻震初．数值分析[M]．2版．南京：东南大学出 版社．2002． [3]孙志忠，裴亚强，胡仁杰．移位技术在交流采样计算中的应用 研究[J]．电气电子教学学报，2003，25(5)：30一33． SUNZhizhong，PEIYaqiang．HURenjie．StudyODtheappli· cationofshiftinstructioninthecomputationofACsampling[J]． JournalofEEE，2003，25(5)：30—33． [4]赵伟，王晶芝，白慧华．快速相对移位法开平方运算的研究与实 现[J]．吉林工学院学报，2000，21(3)：40-42． ZHAOWei，WANGJingzhi，BAIHuihua．Researchandappli· cationofthehighspeedsquarerootcalculationbytherelative shiftingmethod[J]．JournalofJilinInstituteofTechnology， 2000，21(3)：40．42． [5]林志谋，卢贵主．一种适合FPGA实现的开平方算法[J]．厦门 大学学报，2006，45(2)：199．201． LINZhimou．LUGuizhu．Asquarerootalgorithmbasedon FPGA[J]．JournalofXiamenUniversity，2006，45(2)：199—201． [6]郑华．刘笃仁．基于ASIC的重置逐比特移位相减开平方计算[J]． 计算机技术与发展．2006，16(6)：196．197． ZHENGHua，LIUDuren．Binaryrestoringshift／subtractMlllare -rooterbitbybitbasedonASIC[J]．ComputerTechnologyand Development，2006．16(6)：196—197． [7]方寿海．一种开平方的加速算法[J]．南京化工大学学报，1996， 18(4)：98—101． FANGShouhai．QIlickarithrnatieofextractionofsquareroot [J]．JournalofNanjingUniversityofChemicalTeehnoloy， 199H6，18(4)：98一t01． [8]涂时亮，姚志石．单片微机MCS一96／98实用子程序[M]．上海： 复旦大学出版社．1991． [9]杨鹏，史旺旺．电力系统微机保护中开平方浮点算法的改进[J]． 电力自动化设备。2000．20(1)：7．8． YANGPeng，SHIWangwang．Studyonsquarerootalgorithm in microcomputerprotection[J]．ElectricPowerAutomation Equipment．2000，20(1)：7—8． 【10]杨鹏，史旺旺．微机测量中数据表示与开平方算法的改进[J]． 扬州大学学报，2000，3(2)：63．65． YANGPeng．SHIWangwang．Studyon$quarerootalgorithm inmicrocomputerbasedtest[J]．JournalofYaIlgzllⅫUniver— sity，2000，3(2)：63—65． [11]曹海欧，袁宇波，郑建勇．微机保护开平方计算中牛顿迭代法的 改进[J]．江苏电机工程，2006，25(5)：45—46． CAOHaion，YUANYubo，ZHENGJianyong．Theimprovement ofNewtoniterationmethodin thesquarerootcalculationof microcomputerprotection[J]．JiangsuElectricalEngineering， 20016．25(5)：45—46． [12]周明德．微型计算机硬件软件及其应用[M]．北京：清华大学出 版社．1982． (责任编辑：李玲) 作者简介： 张小鸣(1958一)，男，安徽合肥人，教授，研究方向为嵌入 式系统应用及电力监控系统(E-marl：xm0298@163．corn)。 High-precisionandfastsquarerootalgorithm basedonNewtoniterationmethod ZHANGXiaomin91,2,LIYongxinl (1．SchoolofMechanicalEngineering，NanjingUniversityofScience&Technology， Nanjing21,0094，China；2．DepartmentofComputerScienceandEngineering， JiangsuPolytechnicUniversity，Changzhou213164，China) Abstract：Asthesquarerootcalculationoffull-waveFourieralgorithmtakeslongertime，thereal -timeperformanceofmicrocomputer-basedprotectionis seriouslyinfluenced．Amethodbasedon NewtoniterationiSproposed．Toreducetheiterationtimes．itcanselecttheinitialvalueveryclose totherealsquarerootwitherrorlessthan2一byonlyexecutingdisplacementinstruction，referring a 256一unittableonce，anddoingonceortwicemultiplyoperationswithDSPhardwaremultiplier． ThealgorithmisprogrammedwithassemblylanguageandtestedonTIDSPintegrateddevelopment ：platform．Theresultsofsamplingtestsshowthat，theiterationtimeofthesquarerootoperationfor thefixed—pointnumbersrangingfrom00000004．0000Hto01FFFFFF．FFFFHisnotgreaterthan3 withtheiterationprecisionbetterthan2一M．Thismethodneedssmallermemory，verysuitableforthe ‘embeddedmicrocomputerwithhardwaremultipliers． -Keywords：squareroot；iteration；microcomputer-basedprotection；DSP 万方数据 基于牛顿迭代法的高精度快速开方算法 作者： 张小鸣， 李永新， ZHANG Xiaoming， LI Yongxin 作者单位： 张小鸣,ZHANG Xiaoming(南京理工大学机械工程学院,江苏,南京,210094;江苏工业学院计算 机科学与工程系,江苏,常州,213164)， 李永新,LI Yongxin(南京理工大学机械工程学院,江 苏,南京,210094) 刊名： 电力自动化设备 英文刊名： ELECTRIC POWER AUTOMATION EQUIPMENT 年，卷(期)： 2008，28(3) 被引用次数： 0次 参考文献(12条) 1.李晨.张杭.张爱民 一种能滤除衰减直流分量的新递推离散傅氏算法[期刊论文]-继电器 2005(17) 2.孙志忠.袁慰平.闻震初 数值分析 2002 3.孙志忠.裴亚强.胡仁杰 移位技术在交流采样计算中的应用研究[期刊论文]-电气电子教学学报 2003(05) 4.赵伟.王晶芝.白慧华 快速相对移位法开平方运算的研究与实现[期刊论文]-吉林工学院学报(自然科学版) 2000(03) 5.林志谋.卢贵主 一种适合FPGA实现的开平方算法[期刊论文]-厦门大学学报(自然科学版) 2006(02) 6.郑华.刘笃仁 基于ASIC的重置逐比特移位相减开平方计算[期刊论文]-计算机技术与发展 2006(06) 7.方寿海 一种开平方的加速算法 1996(04) 8.涂时亮.姚志石 单片微机MCS-96/98实用子程序 1991 9.杨鹏.史旺旺 电力系统微机保护中开平方浮点算法的改进[期刊论文]-电力自动化设备 2000(01) 10.杨鹏.史旺旺 微机测量中数据表示与开平方算法的改进[期刊论文]-扬州大学学报（自然科学版） 2000(02) 11.曹海欧.袁宇波.郑建勇 微机保护开平方计算中牛顿迭代法的改进[期刊论文]-江苏电机工程 2006(05) 12.周明德 微型计算机硬件软件及其应用 1982 相似文献(10条) 1.期刊论文 杨鹏.史旺旺.YANG Peng.SHI Wang-wang 电力系统微机保护中开平方浮点算法的改进 -电力自动化设 备2000,20(1) 在分析开平方迭代算法收敛速度的基础上,提出了浮点数开平方的初值选取改进算法.该算法具有算法简单、迭代次数少、精度高等特点,较好地解决 了开平方运算时间较长的问题. 2.期刊论文 杨鹏.史旺旺.YANG Peng.SHI Wang-wang 微机测量中数据表示与开平方算法的改进 -扬州大学学报 （自然科学版）2000,3(2) 在分析开平方迭代算法收敛速度的基础上,提出了开平方的初值选取改进算法.本算法具有算法简单,迭代次数少,精度高等特点,较好地解决了开方运 算时间长的问题. 3.期刊论文 赵伟.王晶芝 一种新的基于单片机的多字节浮点快速开平方算法 -微计算机应用2003,24(1) 本文介绍一种可在单片微型计算机上由汇编语言完成的多字节浮点快速开平方运算的方法.它具有精度高、速度快和使用方便等特点.本文采用了"相 对移位"的新方法,将相对移位的试根区长度缩短了一倍,减少了移位时间,与普通的迭代算法平均迭代时间相比速度提高5～10倍. 4.会议论文 曹海欧.袁宇波.李澄 微机保护中一种新的快速开平方算法的讨论 2005 在分析了查表法以及迭代法的基础上，提出了一种新的开平方运算方法－综合法。该运算方法综合了查表法以及迭代法，运算过程中只需要一次牛 顿迭代计算，并且据精度要求可以定量的确定表格的大小。既具有运算速度快的特点，又具有精度高、占用内存小的特点。解决了长期以来开平方算法 存在耗时长、精度低、存贮数据值范围难以确定的问题。 5.学位论文 庞勤 基于FPGA的倾角传感器信号处理 2006 本论文选用FPGA作为载体来实现倾角传感器输出信号的处理。研究内容涉及倾角传感器的信号经A/D转换后，通过串口传入FPGA实验板，FPGA中的模 块包括端口模块，算术运算单元模块等，通过建立数学模型，输入倾角传感器的测量值，输出值为俯仰角θ和滚转角γ，其优势在于可以实时的处理倾 角传感器的测量值。所涉及的方面包括FPGA 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 流程、EDA工具、设计语言、硬件算法适用性比较。 在本论文的内部设计中包括系统自项向下设计的模块分解设计和总体模块综合，对于传感器的信号处理的数学模型的建立，建立传感器测量的坐标 轴体系，在算术模块设计中，针对不同算术模块采用了不同的硬件算法：乘法模块采用了Booth算法，在三角函数和开平方函数的实现中采用了CORDIC算 法，并分析CORDIC算法实现不同函数时初始值设定，迭代次数对精度的影响，优化了该算法的迭代结构，并通过仿真结果与一般的数值方法比较，可以 直观的看出算法的优势，针对本论文的要求设计了通用异步串口接收模块，包括串并转化和并串转换模块。并作了整个模块的信号处理的总体设计，分 析输出值的精度。 6.会议论文 曹海欧.袁宇波.李澄 电力系统微机保护中开平方运算的一种新的快速算法 本文在分析了查表法以及迭代法的基础上,提出了一种新的开平方运算方法-综合法.该运算方法综合了查表法以及迭代法,运算过程中只需要一次牛 顿迭代计算,并且据精度要求可以定量的确定表格的大小.既具有运算速度快的特点,又具有精度高、占用内存小的特点.解决了长期以来开平方算法存在 耗时长、精度低、存贮数据值范围难以确定的问题. 7.期刊论文 曹海欧.袁宇波.郑建勇.CAO Hai-ou.YUAN Yu-bo.ZHENG Jian-yong 微机保护开平方计算中牛顿迭代法 的改进 -江苏电机工程2006,25(5) 在分析了查表法以及牛顿迭代法的基础上,对开平方计算的牛顿迭代法进行了改进.改进方法综合了查表法以及牛顿迭代法,运算过程中只需要一次牛 顿迭代计算,根据精度要求定量地确定表格大小.通过实例验证了该方法具有运算速度快、精度高、占用内存小的特点,解决了长期以来开平方算法存在耗 时长、精度低、存贮数据值范围难以确定的问题. 8.期刊论文 汪振.程文锋.周文辉 基于DSP TMS320LF2407A的浮点数开平方算法的研究 -中国高新技术企业 2007,""(4) 研究DSP TMS320LF2407A浮点数开平方的理论方法,采用改进Newton下山算法为Newton迭代法提供了更为精确的初值,从而使得收敛速度加快,精度更 高.在DSP TMS320LF2407A上编写了一套算法,计算结果与理论分析基本吻合.该算法思路新颖,精度高,速度快,可移植到其它浮点数运算的单片机上. 9.期刊论文 赵俊奇.郭志勇.张志成 基于DSP TMS320F240的浮点数开方的研究 -测试技术学报2003,17(1) 研究 DSP TMS320F240 浮点数开平方的理论方法, 采用牛顿迭代法完成浮点数开方运算. 在 DSP TMS320F240 上编制了一套算法, 其结果基本符合 理论要求. 该方法思路新颖、精度高、速度快, 可移植到其它浮点数运算的单片机上. 10.期刊论文 徐雷.郭立.陈希.杨帆.XU Lei.GUO Li.CHEN Xi.YANG Fan MBE的分析与优化技术的研究 -计算机工程 与应用2009,45(33) 多带激励语音压缩(MBE)算法广泛应用于保密通信中,近来,随着语音压缩编解码技术的进步,信息隐藏载体的多样化发展,出现了以MBE为载体的密写 文件.为了保障保密通信安全.提出了一种MBE算法的分析与优化技术.通过对算法的清浊音判决模块优化,浮点转定点,牛顿迭代法实现开平方,对超越函数 查表实现等方法,并采用基于SOC/Leon3微处理器架构的现场可编程门阵列(FPGA)实现,减少了近45%硬件资源的消耗.并且运算实时性能提升了约29%,为针 对MBE的隐写分析提供了一个很好的平台. 本文链接：http://d.g.wanfangdata.com.cn/Periodical_dlzdhsb200803018.aspx 授权使用：常州大学(jsgyxy)，授权号：b829125c-59f2-421e-804c-9e1c00b7d0e5 下载时间：2010年10月27日