【老刘谈算法005】多次多项式的快速求值——字符串转双字函数分析（2）
本帖最后由 老刘 于 2019-3-5 15:39 编辑在Masm32Lib中给出了3个十进制的字符串转双字函数，其1和其2如下，
a2dw.Asm
```
; #########################################################################
; --------------------------------------
; This procedure was written by Iczelion
; 注释翻译、添加 by 老刘。
; --------------------------------------
.386
.model flat, stdcall; 32 bit memory model
option casemap :none; case sensitive
include \MASM32\INCLUDE\kernel32.inc
.code
; #########################################################################
a2dw proc uses ecx edi edx esi String:DWORD
;----------------------------------------
; Convert decimal string into dword value
; return value in eax
;----------------------------------------
xor ecx, ecx
mov edi, String
invoke lstrlen, String
.while eax != 0
xor edx, edx
mov dl, byte ptr
sub dl, "0" ; subtrack each digit with "0" to convert it to hex value
mov esi, eax
dec esi
push eax
mov eax, edx ;ascii对应的byte
push ebx
mov ebx, 10
.while esi > 0 ;num*10^esi
mul ebx ;结果到eax（低位）,edx（高位）中
dec esi
.endw
pop ebx
add ecx, eax ;ecx储存结果
pop eax
inc edi
dec eax
.endw
mov eax, ecx
ret
a2dw endp
; #########################################################################
end
```
atodw.asm
```
; #########################################################################
; ---------------------------------------------------------------
; 本程序最初由 Tim Roberts 编写
;
; Alexander Yackubtchik 优化了部分代码
; ---------------------------------------------------------------
.486
.model flat, stdcall; 32 bit memory model
option casemap :none; case sensitive
.code
; #########################################################################
atodw proc String:DWORD
; ----------------------------------------
; 十进制转dword
; eax储存返回值
; ----------------------------------------
push esi
push edi
xor eax, eax
mov esi,
xor ecx, ecx
xor edx, edx
mov al,
inc esi
cmp al, 2D ;检测负号
jne proceed ;不是负号就跳转
mov al, byte ptr
not edx ;FFFFFFFF
inc esi
jmp proceed
@@:
sub al, 30h ;ascii->byte
lea ecx, dword ptr ;ecx*=5
lea ecx, dword ptr ;ecx=ecx*2+eax
mov al, byte ptr
inc esi
proceed:
or al, al
jne @B ;非0（没处理完）上跳
lea eax, dword ptr
xor eax, edx
pop edi
pop esi
ret
atodw endp
; #########################################################################
end
```
粗略观察可得，两块代码采用了不同的多次多项式求值算法，本文将会探讨这两种算法的优劣，并引申出一种其它的算法。
其它细枝末节将会在《【老刘谈算法】字符串转双字函数分析系列》后续文章中做详细分析。
## 多项式在哪里？
字符串转dword，可以提取出一个数学模型：
设a~n~至a~1~为键入的数字转化为byte后从高位向低位的值，（若键入123，则a~3~=0x01，a~2~=0x02，a~1~=0x03）
则有dword=a~n~*10^n-1^+a~n-1~*10^n-2^+…+a~2~*10+a~1~，
这正是一个标准的多次多项式。
## 多次多项式算法
### 算法一：无脑直接算的算法
观察a2dw，其运算逻辑&步骤如下：
1. 清空ecx。
2. 计算a~n~*10^n-1^（从左向右顺序计算），累加到ecx，n=n-1。
3. 若只剩最低位了，直接加到ecx，否则重复步骤2。
设输入了n位数，则该算法
- 进行的乘法运算：0+1+2+⋯+(n-1)=(n-1)(1+(n-1))/2=0.5n^2^-0.5n 次
- 进行的加法运算：n-1 次
不难发现，该算法作了许多无用功，即等价下来每次都将10从1次计算到所需的次数。
那么如果倒序计算，并且保存已经计算的10的最高次幂，是否可以大大提高效率，达到效率最大化呢？
### 算法二：优化的多次多项式算法
该算法逻辑如下：依次计算并累加a~1~至a~n~*10^n-1^，将当前已经计算的10的最高次储存，以供后续使用。
这个算法的效率如何呢？
- 进行的乘法运算：0+1+2+2+…+2=0+1+(n-2)*2=2n-3 次
- 进行的加法运算：n-1 次
可见效率已有很大提高，但效率最大化恐怕还轮不到它。
### 算法三：秦九韶算法
秦九韶算法最早由我国古代数学家秦九韶提出，其原理如下：
设原多项式为：k~n~x^n^+k~n-1~x^n-1^+⋯+k~0~
可提取公因式，变型为：(…((k~n~x+k~n-1~)x+k~n-2~)x+⋯+k~1~)x+k~0~
若使用秦九韶算法计算，易得
- 乘法运算：n 次（最多）
- 加法运算：n 次（最多）
放到字符串转dword的情境中，若字符串有n位，则乘法、加法分别计算n-1次即可计算完成。
秦九韶算法是当今最先进的多项式求值算法之一。
而atodw.asm正是该算法的汇编实现。
## 其它
- lz才疏学浅，若有不足，请不吝赐教。
- 若乘加法所需次数计算错误，请告诉lz。
- 欢迎留言、回帖讨论。 论坛MarkDown不支持上下标，大家可以去我的博客看。 学习了 支持下lz
页:
[1]