谁能帮我设计个产生最小代码量的除法

lovehebut

RT

该除法是 K/4.35，如果直接这样，代码量太大了

谁能给个简单算法，K的取值是0-4096，要求12位精度

wajlh

考虑一下用移位做

yajira

K/4.35
相当于
K*0.2299
=k*2299/10000

cowboy

【2楼】 yajira ,把K/4.35变换成 K*2299/10000，相当于要做两次16位整数的乘除法，与直接的 K/4.35 一次浮点运算的效率相差不多。

用移位法，效率应该有不少的提升：

例如  K=(K-(K>>4)-(K>>6)-(K>>10))>>2;    //舍弃小数
或者  K=(K-(K>>4)-(K>>6)-(K>>10)+2)>>2;  //小数四舍五入

运算误差均在 正负1之内,如果觉得精度不够，还可以这样：

      K=((K<<2)-(K>>2)-(K>>4)-(K>>8))>>4;    //舍弃小数
或者  K=((K<<2)-(K>>2)-(K>>4)-(K>>8)+8)>>4;  //小数四舍五入

运算误差均在 正负0.25之内。

lovehebut

yajira 您好

我是不想用除法做

除法产生的代码量真的很大

有没有什么其他办法呢？

lovehebut

【3楼】 cowboy

您好，能把您的思路给我讲一下吗？

是想用移位移出0.2299 来吗？

cowboy

是的，我3楼的思路就是通过移位得到乘以固定常数0.2299的方法。
K=(K-(K>>4)-(K>>6)-(K>>10))>>2
可以看成
K=(K>>2)-(K>>6)-(K>>8)-(K>>12))
设K为1，则
K = (1>>2)-(1>>6)-(1>>8)-(1>>12)
  = 0.25-0.015625-0.00390625-0.000244140625
  = 0.230224609375
已经和0.2299很接近了。

litchiate

想知道，式子中移多少位怎么算出来的。 我数学没学好想不出来。

lovehebut

【6楼】 cowboy

谢谢你的帮忙，不过这样移位产生的代码量似乎比直接除还要大啊

搞不明白了

我看了一下反汇编，似乎也调用了个函数，是个移位函数

lovehebut

【7楼】 litchiate 草真多

6楼给算的已经很详细了啊

longquan

路过，右移一位是除以二，再移除四，加减组合，四分之三出来了，很老的Z80都是这样算的，它没有乘法器

KuJJ

上面移位数据应该是用工具算出来的吗，牛仔透露一下吧

cowboy

不知楼主是用哪种MCU，用AVR的代码量可能较少，其它的视乎各自情况可针对性优化。总的来说代码量可能少不了多少，但速度肯定有一定的提高。

lovehebut

【12楼】 cowboy

不管怎么样，还是要谢谢您，让我学到了些知识

还有个问题想请教您

我现在产品出的问题不是代码量的多少，而是我的主程序算了很多东西，同时我开了个UART终端，每次连续接收八个字节

当我主程序中的调用程序太多的时候，UART接收中断接收到得第一个字节就是错误的

当我把主程序中注释掉一部分的时候，UART接收的第一个字节就正确了

搞了2天了还没搞明白是怎么回事呢


您能帮我分析一下吗？

cowboy

用Keil C51测试了一下，直接浮点除法需用396字节，先乘再移位需用128字节，3楼第一例移位法只用71字节。

【13楼】 lovehebut 蓝色风暴，按你的描述，很难分析哪里出问题，只能粗略估计，是否主程序处理中激活其它中断事件，导致UART中断处理延误?

lovehebut

我开始开了2个TIMER中断，并且在中断中处理了LED显示，事实证明我的UART经常丢数据，也就是本应该接受8个，结果只收到了3 4 个，后来我把程序改了，只开了一个TIMER中断，并且只是在TIMER中断中改变了标志位，然后就能完整收到8个数据了

可是同时就出现了我上面说的问题，以前从没碰到过这样的问题，我主程序中没有激活其他中断事件

void_c

【14楼】 cowboy
学习了。

IAR 8051试了下，移位比直接乘法快多了。

//1000*0.2299=229.9


unsigned int test1(unsigned int K)
{
  return ((K<<2)-(K>>2)-(K>>4)-(K>>8)+8)>>4;
}

unsigned int test2(unsigned int K)
{
  return K*2299UL/10000UL;
}



int main()
{
  asm("nop");
  
  x=test1(1000);   //240周期，结果是230

  asm("nop");
  
  y=test2(1000); //2061个周期，结果是229
  
   asm("nop");
     
  while(1);
  
}

litchiate

我说的不清楚么？ 问的和

【11楼】 KuJJ
积分：112
派别：
等级：------
来自：重庆

是一样的问题。

“上面移位数据应该是用工具算出来的吗，牛仔透露一下吧  ”

jim20090418

如果使用的MCU是AVR的MEGA系列,
使用乘法算是最快的,
先將乘數人工算好,
如65536/4.35=15065(捨去小數點後)
假設K=1000
K放在R19(高位),R18(低位)
乘數放在R17(高位),R16(低位)
結果在R7(高位),R6(低位)

        LDI        R16,Low(15065)
        LDI        R17,High(15065)
        LDI        R18,Low(1000)
        LDI        R19,High(1000)

        CLR        R4
        CLR        R5
        CLR        R6
        CLR        R7

        MUL        R16,R18
        ADD        R4,R0
        ADC        R5,R1
        MUL        R16,R19
        ADD        R5,R0
        ADC        R6,R1
        MUL        R17,R18
        ADD        R5,R0
        ADC        R6,R1
        MUL        R17,R19
        ADD        R6,R0
        ADC        R7,R1

這樣只要24個週期,程序也只佔20個WORD.

抱歉!!我只用ASM寫程式,C僅僅只有看得懂的程度,
所以我沒辦法給出C的代碼.

void_c

楼上的的确最快了。

——————————————————————————
第一种方法：
级数逼近，移位运算，运算较快。

第二种方法：
直接乘除法，为避免溢出，需要提升整型，运算很慢。

第三种方法：
直接乘除法改进，只做一次乘法，且不用整型提升，运算飞快。
但是，C语言并没有16位*16位=32位的乘法，需要用汇编来实现。
（折中办法是进行整型提升，不用汇编）

new007

*2299/10000明显不合理,应当*15066/65536,直接弃低16位

cowboy

对于带硬件乘法器的MCU，【18楼】 jim20090418 确为最快捷方法。
51也带硬件乘法器，按【18楼】方法测试结果，占用代码39字节，速度44机器周期

;入口参数：R6R7（大端储存形式）
;出口参数：R6R7（大端储存形式）
;占用资源：ACC，B，R5，R6，R7，PSW

SUB_DIV435:        
        ;-----------------------
        mov     a,r6
        mov     b,#low(15066)
        mul     ab
        mov     r5,b
        ;---------------------
        mov     a,r7
        mov     b,#high(15066)
        mul     ab
        add     a,r5
        mov     r5,a
        clr     a
        addc    a,b
        mov     r7,a
        ;---------------------
        mov     a,r6
        mov     b,#low(15066)
        mul     ab
        add     a,r5
        mov     a,r7
        addc    a,b
        xch     a,r6
        ;---------------------
        mov     b,#high(15066)
        mul     ab
        add     a,r6
        mov     r7,a
        clr     a
        addc    a,b
        mov     r6,a
        ret

【16楼】 void_c 上官先生
按你test1，Keil C51下编译运行才90周期，怎么IAR 8051需240周期，不会和Keil相差这么远吧。


【11楼】【17楼】的疑问，并没有使用工具，按6楼方式用2的负N次方逐步逼近。

HYLG

k*2299/10000=k*x/8192
x=1883
所以应该是K（16位）乘1883（16位）然后除8192即（32位积）带进位右移13次即可得结果，
我就是这样做的。
16位AD转换2.5V对应65535
65535的AD值要转换成2.5000V的显示结果就得用上述方法

yajira

哈哈，其实我想给出移位的。
然后懒了，觉得整数乘除都差不多。

void_c

【21楼】 cowboy  
按你test1，Keil C51下编译运行才90周期，怎么IAR 8051需240周期，不会和Keil相差这么远吧。

————————————————————————————————————————————

看来，IAR 8051速度优化的确不怎么样。
比KEIL差老远。

lovehebut

同意楼上的，我用IAR觉得优化也就那么回事~~~ 没有传说中那么厉害

void_c

【25楼】 lovehebut 蓝色风暴

IAR 8051确实有些问题，同样是IAR，感觉IAR8051优化比IAR AVR差老远。
另外IAR速度优化相比空间优化逊色。

lin135

做一个16位除16的除数可以固定，怎么样用乘法指令实现呢？我现在用的是移位减法。总共是30多行汇编。但要循环16次花时间较多。
如果能用乘法指令能实现除法就好啊。

jim20090418

16/16,除數固定的話可以用我上面提供代碼,
但有一點需要注意的,這種方式會有一定程度的誤差,
改善誤差的方法就是提高計算的位數.

公式:
A = 被除數
B = 除數
S = 結果
K = 位數(也就是最後計算完捨去的位數,最怏的方式K=8 OR 16 ...以8為單位)

公式
S = A * (2^K / B) / 2^K
至於程序還要看你實際除數的值,
如果在可接受的誤差範圍內除數可以控制在8位以內的話,
程序可以比我上面提供的代碼更短,
執行週期也可以更快.

lin135

如果除数不固定的话就没办法用乘法指令实现除法了吧。现在新出的单片机大部分都没有乘除法指令，有一部分有乘法指令。16位乘16位可以用8位的乘法指令。要做无误差的除法的话还是得用移位减法，做一个24位除16的要移位24次，花的时间较多

hzn1948

试试以下方法:
K*0xEB4C/0x40000=0.229885*K

hzn1948

2字节乘2字节乘法运算加右移18次

jim20090418

lin135 wrote:
如果除数不固定的话就没办法用乘法指令实现除法了吧。现在新出的单片机大部分都没有乘除法指令，有一部分有乘法指令。16位乘16位可以用8位的乘法指令。要做无误差的除法的话还是得用移位减法，做一个24位除16的要移位24次，花的时间较多


只要被除數或除數有一方是固定的,就可以用我上述的原理用乘法去運算,
至於被除數與除數兩方皆不固定,那就只能使用正規的移位減法來做了.

hzn1948

"K*0xEB4C/0x40000=0.229885*K"

不好意思,搞错了
应为:
K*60236/(4*65536)=0.229782*K   有一点误差
但是
16位乘16位可以用8位的乘法指令,所以代码量很小
/65536 不需要运算,实际只要执行2次右移
所以我还是觉得这可能就是最佳方案了,而且精度也可能够了

shenxf

可以用Q定标数进行定点运算
K Q0表示（16位）
1/4.35=0.229885，Q15表示，定点数是7532（16位）
结果最大值941.379，Q6表示
计算：
val=K*7532;
结果：val>>6;//右移6位

lovehebut

【34楼】 shenxf

能把您的算法详细说一下,我觉得这个算法很好

shenxf

计算：
val=K*7532;
结果：val>>6;//右移6位
笔误应为：
计算：
val=K*7532;
结果：val>>9;//右移9位

shenxf

这种算法在DSP中很常见，可Google一下
如果x是浮点数，那么它的Q定点数(可以是16位，也可是32位的，16位用的比较多）：
X=x*2^Q
则Q表示小数位数，或者是小数点所在的位。这样有Q0,,Q15定点数，表示数的范围：
Q0：有符号数-32768~32767，无符号数0~65535
。。
Q15: 有符号数-1~0.999969482421875，无符号数0~1.999969482421875
Q16:只有无符号数0~0.9999847412109375
Q定点数运算原则就是对齐小数点。加减法先对齐小数点再运算，乘除先运算在移位。
实际应用主要的问题是如何确定Q的值：依据浮点数的范围来确定。
本例计算K/4.35
K的Q定点数的Q=0，Qk表示，（1/4.35)定点数的Q=15，Qc表示，这样
m=K/4.35=Qk/2^0*Qc/2^15=(Qk*Qc)/2^(0+15)=（Qk*Qc）/2^15
积m的最大值=941.379，可以用Q=6的定点数Qm表示
m=Qm/2^6=(Qk*Qc)/2^15，因此
Qm=（Qk*Qc）/2^9;//注意（Qk*Qc）结果是32位的）

hzn1948

val=K*15059  其中低位两字节为小数部分

lovehebut

【37楼】 shenxf

受教了~~~

容我先好好理解一下~ 嘿嘿

hzn1948

【37楼】 shenxf 的理论是正确的,

m=K/4.35=Qk/2^0*Qc/2^15=(Qk*Qc)/2^(0+15)=（Qk*Qc）/2^15

但是最后说到的Qm令人费解

不如变换一下:

m=K/4.35=(Qk*Qc）/2^15=2*(Qk*Qc）/2^16=2*K*7532/2^16=K*15064/2^16

K*15064/2^16------"K*15064  其中低位两字节为小数部分"

我在33楼,38楼给出的数字存在计算错误,正确的应为K*15064  ....

luojiyin

学习了

wwwdege

学习了

xurenhui

好帖子，学习，希望后来者补充更详细些就更好了

khuohuo

4455/1024=4.35

skype

mark   
               

qq335702318

cowboy 发表于 2009-5-1 21:07
【2楼】 yajira ,把K/4.35变换成 K*2299/10000，相当于要做两次16位整数的乘除法，与直接的 K/4.35 一次浮 ...

mark一下
翻这个帖子翻了好久找不到...

t3486784401

的确是个不错的帖子，标记学习了

lhj200304

放大用整数就可以了