AVR中除10的优化算法

takashiki

AVR没有硬件除法，软件除法又是那么的消磨时光，/10，%10又是如此的常用，一直为之叹息。现在终于摸索出一个比较可行的方案了，如下

#define DIV10(Divider) (unsigned char)(((Divider) * 205u)>>8) >> 3

当Divider为unsigned char类型时，上述结果是正确的。事实上，
#define DIV10(Divider) ((Divider) * 205u ) >> 11
当0<=Divider<1029时，上述结果是正确的。

这样，/10只需要做一次乘法和三次移位就可以了。


=========================================================
修改原因：205已经超出了char数据类型的范围，改为205u，无符号字符型。
鉴于上文描述可能给用户带来不必要的麻烦，请使用
#define DIV10(Divider) (unsigned char)(((Divider) * 205u)>>8) >> 3

或（以下为GCC语法，其他编译器没用过，不知道）
__inline unsigned char DIV10(unsigned char Divider){
    return (unsigned char)(((Divider) * 205u)>>8) >> 3;
}

形成内联函数，省去CALL、RET调用的时间。

kevintang

取余呢

kevintang

回复【楼主位】takashiki 岚月影
AVR没有硬件除法，软件除法又是那么的消磨时光，/10，%10又是如此的常用，一直为之叹息。现在终于摸索出一个比较可行的方案了，如下
#define DIV10(Divider) (unsigned char)(((Divider) * 205)&gt;&gt;8) &gt;&gt; 3
当Divider为unsigned char类型时，上述结果是正确的。事实上，
#define DIV10(Divider) ((Divider) * 205 ) &gt;&gt; 11
当0&lt;=Divider&lt;1029时，上述结果是正确的。
这样，/10只需要做一次乘法和三次移位就可以了。
-----------------------------------------------------------------------

测试了一下，真的非常高效

voidx

typedef  struct
{
   uint8 quot;
   uint8 rem;
}udiv8_t;

typedef  struct
{
   uint16 quot;
   uint16 rem;
}udiv16_t;

typedef  struct
{
   uint32 quot;
   uint32 rem;
}udiv32_t;

udiv8_t u8_div_10(uint8 var)
{
udiv8_t ret;
  
  ret.quot=(uint8)(var*(((1U<<11)+9)/10)>>8)>>3 ;
  ret.rem=var-ret.quot*10;
  
  return ret;
}


udiv16_t u16_div_10(uint16 var)
{
udiv16_t ret;

  ret.quot=(uint16)((var*(((1UL<<19)+9)/10))>>16)>>3 ;
  ret.rem =var-ret.quot*10;
     
  return ret;
}


udiv32_t u32_div_10(uint32 var)
{
udiv32_t ret;

  ret.quot=(uint32)((var*(((1ULL<<35)+9)/10))>>32)>>3 ;
  ret.rem =var-ret.quot*10;
     
  return ret;
}


udiv8_t u8_div_10_(uint8 val_8)
{
   udiv8_t ret;
   uint8 temp;
   
   temp=0;
   if( val_8>=200 ) {temp+=20;val_8-=200;}
   if( val_8>=100 ) {temp+=10;val_8-=100;}
   
   if(val_8>=80) {temp+=8;val_8-=80;}
   if(val_8>=40) {temp+=4;val_8-=40;}
   if(val_8>=20) {temp+=2;val_8-=20;}
   if(val_8>=10) {temp+=1;val_8-=10;}

   ret.quot=temp;
   ret.rem=val_8;
   
   return ret;
}

udiv16_t u16_div_10_(uint16 val_16)
{
   udiv16_t ret;
   uint8 val_8;
   uint16 temp;
   
   temp=0;
   if( val_16>=40000 ) {temp+=4000;val_16-=40000;}
   if( val_16>=20000 ) {temp+=2000;val_16-=20000;}   
   if( val_16>=10000 ) {temp+=1000;val_16-=10000;}

   if( val_16>=8000 ) {temp+=800;val_16-=8000;}
   if( val_16>=4000 ) {temp+=400;val_16-=4000;}
   if( val_16>=2000 ) {temp+=200;val_16-=2000;}   
   if( val_16>=1000 ) {temp+=100;val_16-=1000;}
   
   if( val_16>=800 ) {temp+=80;val_16-=800;}
   if( val_16>=400 ) {temp+=40;val_16-=400;}
   if( val_16>=200 ) {temp+=20;val_16-=200;}   
   if( val_16>=100 ) {temp+=10;val_16-=100;}

   val_8=val_16;
   
   if(val_8>=80) {temp+=8;val_8-=80;}
   if(val_8>=40) {temp+=4;val_8-=40;}
   if(val_8>=20) {temp+=2;val_8-=20;}
   if(val_8>=10) {temp+=1;val_8-=10;}

   ret.quot=temp;
   ret.rem=val_8;
   return ret;
}


udiv32_t u32_div_10_(uint32 val_32)
{
   uint32 temp;
   uint16 val_16;
   uint8 val_8;
   udiv32_t ret;
   
   temp=0;
   if( val_32>=4000000000 ) {temp+=400000000;val_32-=4000000000;}
   if( val_32>=2000000000 ) {temp+=200000000;val_32-=2000000000;}   
   if( val_32>=1000000000 ) {temp+=100000000;val_32-=1000000000;}
   
   if( val_32>=800000000)  {temp+=80000000;val_32-=800000000;}
   if( val_32>=400000000 ) {temp+=40000000;val_32-=400000000;}
   if( val_32>=200000000 ) {temp+=20000000;val_32-=200000000;}
   if( val_32>=100000000 ) {temp+=10000000;val_32-=100000000;}

   if( val_32>=80000000)  {temp+=8000000;val_32-=80000000;}
   if( val_32>=40000000 ) {temp+=4000000;val_32-=40000000;}
   if( val_32>=20000000 ) {temp+=2000000;val_32-=20000000;}
   if( val_32>=10000000 ) {temp+=1000000;val_32-=10000000;}
  
   if( val_32>=8000000)  {temp+=800000;val_32-=8000000;}
   if( val_32>=4000000 ) {temp+=400000;val_32-=4000000;}
   if( val_32>=2000000 ) {temp+=200000;val_32-=2000000;}
   if( val_32>=1000000 ) {temp+=100000;val_32-=1000000;}
   
   if( val_32>=800000)  {temp+=80000;val_32-=800000;}
   if( val_32>=400000 ) {temp+=40000;val_32-=400000;}
   if( val_32>=200000 ) {temp+=20000;val_32-=200000;}
   if( val_32>=100000 ) {temp+=10000;val_32-=100000;}

   if( val_32>=80000)  {temp+=8000;val_32-=80000;}
   if( val_32>=40000 ) {temp+=4000;val_32-=40000;}
   if( val_32>=20000 ) {temp+=2000;val_32-=20000;}
   if( val_32>=10000 ) {temp+=1000;val_32-=10000;}
   
   val_16=val_32;
   if( val_16>=8000 ) {temp+=800;val_16-=8000;}
   if( val_16>=4000 ) {temp+=400;val_16-=4000;}
   if( val_16>=2000 ) {temp+=200;val_16-=2000;}   
   if( val_16>=1000 ) {temp+=100;val_16-=1000;}

   if( val_16>=800 ) {temp+=80;val_16-=800;}
   if( val_16>=400 ) {temp+=40;val_16-=400;}
   if( val_16>=200 ) {temp+=20;val_16-=200;}   
   if( val_16>=100 ) {temp+=10;val_16-=100;}
   
   val_8=val_16;
   if(val_8>=80) {temp+=8;val_8-=80;}
   if(val_8>=40) {temp+=4;val_8-=40;}
   if(val_8>=20) {temp+=2;val_8-=20;}
   if(val_8>=10) {temp+=1;val_8-=10;}

   ret.quot=temp;
   ret.rem=val_8;
   return ret;
}

hsztc

试了，好像常数是通过编译器直接生成结果。2T

用变量x

DIV10(x)需要126T  (这个剩法是16位的乘法，也有可能是32位的)

而直接用除法x/10需要206T

差不了多少啊，会少点，但不通用，只有除10有效。

我是用ICCAVR测试的

takashiki

回复回复【1楼】kevintang  
取余呢
-----------------------------------------------------------------------

取余麻烦一点，只能拿原数-商*10，还要进行多两次运算。幸好AVR的乘法还是那么高效。

iamseer

mark

takashiki

回复【4楼】hsztc  
-----------------------------------------------------------------------

我说的主要就是Divider为unsigned char类型的时候，怎么可能是16位/32位的乘法呢？是8位*8位的，AVR直接一条硬件乘法指令搞定，不可能达到126T的。下面那个倒是有可能，但是一点也不通用，因为0~1028这个区间实在是太窄了，根本没有多少使用的意义。下面那个我只是说明该宏可以应用的最大的取值范围而已。

这个只针对/10有效，不是通用的，而是因为它用的太多了，所以单拿出来说事。
205的取值来由：
x/10 => x*25.6/256 => x*204.8/2048
*204.8采用*205取代，误差范围为(205-204.8)/204.8= 0.0009765625，千分之一不到，因此可以替代。

hsztc

"当0<=Divider<1029时，上述结果是正确的。"

1028是 unsigned char类型吗？

就算只取255以内*205也是一个int型的数啊

takashiki

to 【8楼】 hsztc

请看清楚我的描述。

//================================================================================
AVR没有硬件除法，软件除法又是那么的消磨时光，/10，%10又是如此的常用，一直为之叹息。现在终于摸索出一个比较可行的方案了，如下

#define DIV10(Divider) (unsigned char)(((Divider) * 205)>>8) >> 3

当Divider为unsigned char类型时，上述结果是正确的。

我已经特别指明，Divider为unsigned char类型。

//================================================================================
至于后面的东西，我只是说，Divider可以达到的最大取值范围。是最大，我们没有必要非得就千篇一律都声明成unsigned int类型吧，那我还可以声明成unsigned long long类型呢。这个表达式当Divider=1029时是错误的。所以我给出可能的所有取值范围。

255以内*205只是8位*8位的乘法，结果为16位，而不是16位乘法，右移8位表示只取高8位即可。这些东西AVR的硬件中一条硬件乘法搞定的，如不信，请参见AVR的指令说明。


【3楼】 voidx 已经给出函数来了，你可以测试一下。

xuejianhua1986

mark

hecb999

mark

hsztc

好像是我搞错了哈哈

不过ICCAVR没有达到最佳优化也是一个问题
#define DIV10(Divider) ((Divider) * 205 ) >> 11

unsigned int xx;
unsigned char yy;

xx=DIV10(PINB);
PORTC=xx;    //95T  怀疑在做16位的移位

xx=PINB*205;
yy=xx>>8;
yy>>=3;   
PORTB=yy;    //11T 确实省哈哈

之前我只定义了一个int xx,所以编译器就生成了16位的乘法。。。

hsztc

又是我的错。。。
#define DIV10(Divider) (unsigned char)(((Divider) * 205)>>8) >> 3
用这个可以。。。13T

之前用的是#define DIV10(Divider) ((Divider) * 205 ) >> 11

qzf368

恩，收藏了，学习了

l503iu

MARK

xjmlfm1

mark

undeadhuman

思路挺好

hsztc

求余
#define MOD10(Divider) (Divider)-(((unsigned char)(((Divider) * 205)>>8) >> 3)*10)

takashiki

回复【3楼】voidx  
-----------------------------------------------------------------------

你这样算和我的原意不同了。
比如：
udiv8_t u8_div_10(uint8 var)
{
udiv8_t ret;
  
  ret.quot=(uint8)(var*((1U<<11)/10)>>8)>>3 ;  
  ret.rem=var-ret.quot*10;
  
  return ret;
}

你取的是204，我取的是205，你可以计算一下，取204时误差很大的。

我的取值205纯粹是通过圆整来的，不能随意切断去整。
对于具有16位*16位的单片机来说，可以这样实现：
#define DIV10(Divider) (unsigned short)(((Divider) * (unsigned short)((1ul<<19)/10.d+0.5))>>16) >> 3

同样，32*32的则是这样：
#define DIV10(Divider) (unsigned long)(((Divider) * (unsigned long)((1ull<<35)/10.d+0.5))>>32) >> 3

陷阱：
以上采用浮点数的可能精度不够，导致结果不正确。

经过分析，每次/10之后的小数位总是8，圆整时总是进位。因此你的通用算法可以写成这样：
udiv8_t u8_div_10(uint8 var)
{
udiv8_t ret;
  
  ret.quot=(uint8)(var*((1U<<11)/10 + 1)>>8)>>3 ;              //在这里加上一个1，就好了。其它的同理  
  ret.rem=var-ret.quot*10;
  
  return ret;
}

hsztc

....

我晕，答案已经在5楼了竟然没看到，还想了好久

rainyss

这是个基本的数学原理啊....

n / 10  =   n / 8    *    8/10

而8/10等于205(其实是204.8)右移8位,所以用n先乘以204再右移(3+8)位就行了.呵呵.

voidx

回复【20楼】takashiki 岚月影

ret.quot=(uint8)(var*((1U<<11)/10 + 1)>>8)>>3 ;              //在这里加上一个1，就好了。其它的同理   
-----------------------------------------------------------------------

多谢指正。
204，205是有区别的。

(10*205)>>11 = 1 ............0
(10*204)>>11 = 0 ........... 10

改成：
ret.quot=(uint8)(var*(((1U<<11)+9)/10)>>8)>>3 ;

kevintang

回复【3楼】voidx
-----------------------------------------------------------------------

上官金虹你的是C＋＋语法么？

antonine

MARK

zlj2008

mark

voidx

回复【26楼】kevintang
回复【3楼】voidx  
-----------------------------------------------------------------------
上官金虹你的是C＋＋语法么？
-----------------------------------------------------------------------

C语言语法

kevintang

回复【29楼】voidx
-----------------------------------------------------------------------

不像哪

udiv8_t u8_div_10(uint8 var)
{
udiv8_t ret;
   
  ret.quot=(uint8)(var*(((640064>1U<<640064>11)640064>+9)/640064>10)>>640064>8)>>640064>3 ;
  ret.rem=var-ret.quot*640064>10;
   
  0000FF>return ret;
}


udiv16_t u16_div_10(uint16 var)
{
udiv16_t ret;

  ret.quot=(uint16)((var*(((640064>1UL<<640064>19)640064>+9)/640064>10))>>640064>16)>>640064>3 ;
  ret.rem =var-ret.quot*640064>10;
      
  0000FF>return ret;
}

trueboy

好!

voidx

回复【30楼】kevintang
回复【29楼】voidx  
-----------------------------------------------------------------------
不像哪
udiv8_t u8_div_10(uint8 var)  
{  
udiv8_t ret;  
   
  ret.quot=(uint8)(var*(((640064&gt;1U&lt;&lt;640064&gt;11)640064&gt;+9)/640064&gt;10)&gt;&gt;640064&gt;8)&gt;&gt;640064&gt;3 ;  
  ret.rem=var-ret.quot*640064&gt;10;  
   
  0000FF&gt;return ret;  
}  
udiv16_t u16_div_10(uint16 var)  
{  
udiv16_t......
-----------------------------------------------------------------------

显示的问题。

kevintang

难怪了，我还以为是传说中的C＋＋呢

voidx

__always_inline__ uint8 u8_div_10_quot(uint8 var)
{
  return (uint8)(var*(((1U<<11)+9)/10)>>8)>>3;
}

__always_inline__ uint8 u8_div_10_rem(uint8 var)
{
  return var-u8_div_10_quot(var)*10;
}

__always_inline__ uint16 u16_div_10_quot(uint16 var)
{
  return (uint16)((var*(((1UL<<19)+9)/10))>>16)>>3 ;
}

__always_inline__ uint16 u16_div_10_rem(uint16 var)
{
  return var-u16_div_10_quot(var)*10;
}

rui.chan

好贴，收藏了，做个记号

gliet_su

MARK

yaya001

mark

gpzdc986

mark

bigZ

这个不仅AVR可用吧
其他MCU应该都可以用

zhangxun0712

mark

snail0204

多少T怎么计算出来的，看汇编程序吗？

jim20090418

去年有類似的除法討論,
原理都相同,而且去年的最佳算法只需做乘法不用再移位

去年的討論串
http://www.ourdev.cn/bbs/bbs_content.jsp?bbs_sn=3320280&bbs_page_no=1

snail0204

回复【43楼】voidx
回复【41楼】snail0204 瓜牛
多少T怎么计算出来的，看汇编程序吗？
-----------------------------------------------------------------------
u8_div_10_quot1:
//   11 {
//   12   return (uint8)(var*(((1U&lt;&lt;8)+9)/10)&gt;&gt;8);
        LDI     R17, 26
        MUL     R16, R17
        MOV     R16, R1
        RET
//   13 }
//   14  
u8_div_100_quot1:
//   21 {
//   22   return (uint8)(var*(((1U&lt;&lt;8)+99)/100)......
-----------------------------------------------------------------------

谢谢

takashiki

回复【42楼】jim20090418  
去年有類似的除法討論,
原理都相同,而且去年的最佳算法只需做乘法不用再移位
去年的討論串
http://www.ourdev.cn/bbs/bbs_content.jsp?bbs_sn=3320280&amp;bbs_page_no=1
-----------------------------------------------------------------------
我就是因为吃了不移位的亏，所以痛定思痛，终于捣鼓出这么个东西出来。
否则，自己计算一下
#define DIV10(Divider) ((Divider) * 26)>>8
当Divider位于0～255之间的数时，速度是快了，但是误差有多大？我算过，好像60以上的数中有很多不完全一致，因此最后决定还是采用移位方式。


回复【39楼】bigZ  
这个不仅AVR可用吧
其他MCU应该都可以用
-----------------------------------------------------------------------
都是可以的，没有限制。只是我所使用的CPU中，唯独AVR没有硬件除法指令，所以挂个名字。



回复【34楼】voidx  
-----------------------------------------------------------------------
强制内联是一种比较好的解决方案，谢谢改写。

voidx

多谢指正。移位不能省。

yusufu

好东西，好好学习~~

vr2whf

good analysis

jdw924

mark

ripplexu

而8/10等于205(其实是204.8)右移8位

俺比较愚钝，想半天不明白这是什么原理。

我一般是是把xx转换成0yyy，比如fe->0254,汇编基本十几行代码全部搞定。

hsztc

是右移11位的,2的11次方等于2048,右移11位就是除于2048

乘于204.8/2048就是除10的变形。

分成移8位再移3位，是因为移8位可以直接取高字节，一两条指令就可以完成了，然后再移三次。

这是我的理解。

ripplexu

这样啊，这样运行效率是比我的方法要高。

ggyyll8683

标记

elchb

标记

dream_ss

标记下

ifree64

mark

qinhya

mark