霍恩规则的正确性验证

系统管理员 2022-02-16 09:21 185阅读 0赞

## 霍恩规则计算求值多项式 ##

P(x) =  ∑ k − 0 n \\sum\_\{k-0\}^n ∑k−0n a k a\_k ak x k x^k xk  
霍恩规则：P(x) =  a 0 a\_0 a0 \+ x( a 1 a\_1 a1 \+ x( a 1 a\_1 a1 \+ x( a 2 a\_2 a2\+ … +x( a n − 1 a\_n-1 an−1 \+ x\* a n a\_n an))))

## 伪代码： ##

y = 0
    for i = n downto 0
    	y = a[i] + x*y

## 利用循环不定式检验正确性 ##

1.  每次迭代开始时有以下表达式成立：  
    y =  ∑ k − 0 n − ( i + 1 ) \\sum\_\{k-0\}^\{n-(i+1)\} ∑k−0n−(i\+1) a k + i + 1 a\_\{k+i+1\} ak\+i\+1 x k x^k xk
2.  循环结束后：  
    y =  a i a\_i ai \+ x \* y  
    y =  a i a\_i ai \+ x \*  ∑ k − 0 n − ( i + 1 ) \\sum\_\{k-0\}^\{n-(i+1)\} ∑k−0n−(i\+1) a k + i + 1 a\_\{k+i+1\} ak\+i\+1 x k x^k xk  
    y =  a i a\_i ai \+  ∑ k − 0 n − ( i + 1 ) \\sum\_\{k-0\}^\{n-(i+1)\} ∑k−0n−(i\+1) a k + i + 1 a\_\{k+i+1\} ak\+i\+1 x k + 1 x^\{k+1\} xk\+1  
    y =  ∑ k − 0 n − i \\sum\_\{k-0\}^\{n-i\} ∑k−0n−i a k + i a\_\{k+i\} ak\+i x k x^k xk （式1）  
    i = i - 1（以上表达式i未更新：i\_old）  
    i = i\_old + 1  
    代入式1：  
    y =  ∑ k − 0 n − ( i + 1 ) \\sum\_\{k-0\}^\{n-(i+1)\} ∑k−0n−(i\+1) a k + i + 1 a\_\{k+i+1\} ak\+i\+1 x k x^k xk
3.  即完成一次循环后，等式仍然成立
4.  利用以上等式验证，i=0进入循环后，获取终止时的表达式：  
    y =  ∑ k − 0 n \\sum\_\{k-0\}^n ∑k−0n a k a\_k ak x k x^k xk
5.  综上所述：霍恩规则正确

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关身份证的验证规则

class IdentityCard { / 校验身份证号是否合法 @param string $num

傷城~/ 2023年02月11日 04:36/ 0 赞/ 91 阅读

相关 php使用身份证的验证规则

function validation_filter_id_card($id_card){ if(strlen($id_card)==18){

谁践踏了优雅/ 2023年02月11日 03:30/ 0 赞/ 19 阅读

相关 pytorch pth 模型转 onnx模型，并验证结果正确性

> pytorch 模型部署很重要的一步是转存pth模型为ONNX，本文记录方法。转存 onnx 建立自己的pytorch模型，并加载权重 model

刺骨的言语ヽ痛彻心扉/ 2022年12月23日 00:37/ 0 赞/ 453 阅读

相关 yii验证规则

//必须填写 array('email, username, password,agree,verifyPassword,verifyCode', 'required'),

浅浅的花香味﹌/ 2022年07月29日 10:50/ 0 赞/ 216 阅读

相关 JQuery validate验证规则

//定义中文消息 var cnmsg = \{ required: “必选字段”, remote: “请修正该字段”, email: “请输入正确格式的电子邮

朱雀/ 2022年06月17日 11:38/ 0 赞/ 238 阅读

相关分布式系统的正确性验证方法

分布式系统的正确性验证方法 1. Jepsen框架 Jepsen是一个开源的分布式一致性验证框架，可用于验证分布式数据库、分布式消息队列、分布式协调系

矫情吗；*/ 2022年06月09日 03:09/ 0 赞/ 188 阅读

相关利用GUID/UUID生成token及验证token的正确性

本来有JWT这种生成token验证的强大工具，但有时考虑到项目的实际需求，会利用GUID/UUID来生成token，当然GUID/UUID能生成很多具有唯一性的验证结果，所以这

布满荆棘的人生/ 2022年05月23日 09:39/ 0 赞/ 263 阅读

相关霍恩规则的正确性验证

霍恩规则计算求值多项式 P(x) = ∑ k − 0 n \\sum\_\{k-0\}^n ∑k−0n a k a\_k ak x k x^k xk 霍恩规则：P(

系统管理员/ 2022年02月16日 09:21/ 0 赞/ 186 阅读

相关 php通用验证规则

php通用验证规则: <?php / Created by PhpStorm. User: jiqing Date: 18-7-24 Time:

雨点打透心脏的1/2处/ 2021年10月20日 00:34/ 0 赞/ 309 阅读

相关正则表达式验证邮箱email正确性

每个邮箱地址都符合“名称@域名”规则，字符“@”在邮箱地址的“名称”和“域名”之间。进一步观察发现，邮箱地址名称只允许由英文字母、数字、下划线组成，当然现在也允许包含

比眉伴天荒/ 2021年09月27日 15:28/ 0 赞/ 485 阅读