打印

PK 使人进步:highgear 向网友刘前辈提出很简单的切磋请求

[复制链接]
楼主: highgear
手机看帖
扫描二维码
随时随地手机跟帖
41
Cortex-M0| | 2011-10-9 04:31 | 只看该作者 回帖奖励 |倒序浏览
顶~~~

刷屏党 蛋疼期作品:求SinX

算法学习了,精度是提高了,只是有点违规,highgear老师要求的只能使用整型变量(最大32bit),刷屏党在计算过程中,引入了大于整型变量范围的蛋疼变量,属于严重作弊~~~  :lol

使用特权

评论回复
42
lhj200304| | 2011-10-9 09:49 | 只看该作者
mark  sin值计算

使用特权

评论回复
43
lixiaoxu2meng| | 2011-10-9 14:52 | 只看该作者
坐等PK大赛 顺便学习学习操作系统:victory:

使用特权

评论回复
44
Cortex-M0| | 2011-10-10 10:10 | 只看该作者
这几天在玩邓喵老师的 非典250  16/32位 BIN ----> BCD 程序。

邓喵老师的 非典250 算法确实超级NB,  连用中颖的 16/8位 除法器的速度都难以追上邓喵老师的 非典250 算法~~~

详情请见:
https://bbs.21ic.com/viewthread.php?tid=51848

使用特权

评论回复
45
陈永宾0| | 2011-10-10 10:59 | 只看该作者
哇塞 好厉害 向你们学习

使用特权

评论回复
46
mayduan| | 2011-10-10 12:52 | 只看该作者
看看吧……估计没戏。

使用特权

评论回复
47
DownCloud| | 2011-10-10 13:37 | 只看该作者
44# Cortex-M0
这个我也有兴趣啊,M0你现在从事什么工作啊?

使用特权

评论回复
48
Cortex-M0| | 2011-10-10 13:58 | 只看该作者
回LS兄弟

俺专门负责打杂~~~

使用特权

评论回复
49
Cortex-M0| | 2011-10-10 14:02 | 只看该作者
有点空余时间时,喜欢将像 highgear老师,邓喵老师这些超一流高手的小题目,拿来消化一通~~~

使用特权

评论回复
50
windertakers| | 2011-10-10 15:18 | 只看该作者
这么多次了 有PK成功的没???

使用特权

评论回复
51
DownCloud| | 2011-10-10 16:30 | 只看该作者
47# DownCloud
M0兄弟如此有才,看你解题收获良多。俺一毕业等于失业。自惭~

使用特权

评论回复
52
Cortex-M0| | 2011-10-10 17:22 | 只看该作者
呵呵~~~

俺几十年没玩技术啦,这些老掉牙的东东还依稀记得一点~~~

哪能跟你们年轻一代相比,你们是8-9点钟刚刚升起的太阳。自惭~~~

使用特权

评论回复
53
highgear|  楼主 | 2011-10-10 21:13 | 只看该作者
顶楼上各位兄弟。

关于 sin 函数的快速算法,网上有很多的讨论,值得关注的是这一个
http://www.coranac.com/2009/07/sines/
以及:
http://lab.polygonal.de/2007/07/18/fast-and-accurate-sinecosine-approximation/
(中文翻译在此: http://friendz.blog.163.com/blog/static/857571322011288505934/)

除了以上的数种方法外,还有一个著名的算法: CORDIC (COordinate Rotation DIgital Computer),这种方法非常适用与硬件运算,但由于逐次逼近需要大量判断,以及没有很好的利用硬件乘法器,对于带有硬件乘法器的 cpu 来说效率不是很高,所以下面我只简单的讲解一下原理:
根据欧拉公式:
cos(x+y) + jsin(x+y) = e^j(x+y) = e^jx * e^jy
= (cos(x) +jsin(x)) * (cos(y) + jsin(y))
= (cos(x)*cos(y) - sin(x)*sin(y)) + j(cos(x)*sin(y) + sin(x)*cos(y))
= cos(y) * (cosx - sinx * tany) + j cosy *(cosx*tany + sinx)

任何一个角度 x 可以分解得更细小,即:
x = x0 + x1 + x2 + ... = ((((x0 + x1) + x2) + x3) + ...)

结合上面的公式,如果我们挑选不同的 y, 可以让 tany = +-(/2, 1/4, 1/8, 1/16, ....) 那么
cos(y) * (cosx - sinx * tany) + j cosy *(cosx*tany + sinx)这个公式则可以变得极为简单,cosx, sinx 是上次的计算值,而tany 变成了移位,至于 cosy, cos(x0)*cos(x1)*cos(x2)*.... 为一个常数。

从 cordic 可以看出,整数运算的另一个技巧之一是恰当的选择一些系数,可以使用移位操作来代替乘法或除法运算,使得整个运算简化。

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
Cortex-M0 + 1
54
Cortex-M0| | 2011-10-11 04:10 | 只看该作者
highgear老师讲解的真透彻,学习了~~~

使用特权

评论回复
55
Cortex-M0| | 2011-10-11 04:14 | 只看该作者
继续灌水~~~ :lol

何为电工?   
答: 电工 ==  农民工(靠体力干活)

何为高级电工?
答: 高级电工 ==  理论(抄书)+ 实践(靠体力干活,取得经验)

使用特权

评论回复
56
Cortex-M0| | 2011-10-11 07:06 | 只看该作者
继续灌水,将highgear老师提出的一个很简单的题目:
完全用整数运算完成sin, atan 函数,要求精度可达 0.001。
改为要求:完全用整数运算完成sin, atan 函数,要求精度可达 0.0001,精度要求提高十倍,这才有点搞头~~~

受highgear老师 53楼 非典中的经典算法启示,俺也来个压缩算法,只运行 4次 16位 * 16位 = 16位 精度的定点小数乘法,就能玩转 sin函数~~~

使用刘前辈最喜欢的C51编写, 让计算 sin函数变得十分简单山寨,速度超级快,精度也不低,完全达到预定指标 0.0001,力争做山寨中的战斗机~~~

为简单起见,本程序只作输入弧度 0-PI/2 之运算,超过上述范围的需先自行转换,如范围在 PI/2-PI之间,可利用sin函数的对称性求得,计算范围在 PI-2PI之间,先减去一个 PI, 再将sin计算结果取负即可。

由于去掉了符号,再利用定点小数运算,这样的好处是变相增加了2bit位,极大地提高了16位定点运算精度。

使用特权

评论回复
57
Cortex-M0| | 2011-10-11 07:20 | 只看该作者
计算公式还是用俺的最爱,切比雪夫创造发明的 切比雪夫幂级数缩减法,直接把
Y =  SIN((PI/2) * X) 的泰勒级数缩减成如下公式:
SIN((PI/2) * X)  =  0.07185 * X^5 - 0.64215 * X^3 + 1.57036 * X
由于系数 1.57036 大于 1,  超出了定点小数的计算范围,无法用定点小数表示,再进一步化简成:
SIN((PI/2) * X)  =  X + (0.57036 - (0.64215 -0.07185 * X^2) * X^2) * X
这样,完全可以使用快速的 16位定点小数运算,完成 sin函数的求值,并且精度达到预定的 0.0001 。                                 
  式中:  X 取值范围:0 <= X < 1

使用特权

评论回复
58
Cortex-M0| | 2011-10-11 07:23 | 只看该作者
使用不同的输入值,测试结果令人满意~~~

无图无真相,上片片~~~



使用特权

评论回复
59
Cortex-M0| | 2011-10-11 07:30 | 只看该作者
从上图可以看出,sin求解程序很简单,超级山寨,只需指定 FX 值,编译运行后,程序输出两个值,fy为定点小数求解sin值,再转换成浮点数供观看,fy1为调用标准的C51浮点函数库计算sin, 供测试结果对比验证用。


/***************************************************************************************
Model  : main.c
Description : 中颖单片机C51定点小数 SIN((PI/2) * X)运算函数,DEMO测试程序。
               SIN((PI/2) * X) = 0.07185 * X^5 - 0.64215 * X^3 + 1.57036 * X
                        = X + (0.57036 - (0.64215 -0.07185 * X^2) * X^2) * X
     
       X 取值范围:0 <= X < 1
Author  : CLR
Create Time : 2011-10-11
Version ID  : 1.5
用  途      :中颖SH79/88/89F51系列MCU
作  者      :许意义
21ic  ID    :LAOXU
中颖论坛    : bbs.21ic.com   
****************************************************************************************/
#include <DEFINE51.H>
#include <global.h>
#include <intrins.h>
#include <math.h>
#include <Sinowealth\SH88F4051.H>
#define FX      1.234567L     
#define K0       37379            // 0.57036
#define K1       42084            // 0.64215
#define K2        4709           // 0.07185
#define PI      3.1415926L   
#define  X      (FX * 2 / PI) * 0x10000   
uint16  y;
float   fy, fy1;

uint16 dsin(uint16 x)  //SIN((PI/2) * X) = X + (K0 - (K1 - K2 * X^2) * X^2) * X  
{   uint16 a, b;
if(x<0xfe88)
      { a = dmul16(x, x);
        b = K1 - dmul16(K2, a);
     b = K0 - dmul16(b, a);
     x += dmul16(b, x);
   }
else
   { x = 0xffff;
   }
return(x);
}
void main(void)   
{  // 中颖单片机C51定点小数 SIN((PI/2) * X)运算函数,DEMO测试程序。
// 调用中颖单片机C51专用运算库函数,加速运算速度        
  y  = dsin(X);
fy = (float)y / 0x10000;
fy1 = sin(FX);
_nop_();      
while(1);
}



测试程序打包上传:

sin.rar (32.91 KB)

使用特权

评论回复
60
Cortex-M0| | 2011-10-11 07:36 | 只看该作者
如不用中颖单片机,需将 16位定点小数函数
c = dmul16(uint16  a, uint16  b);
改写成:
c = (uint16)(((uint32)a * (uint32)b) >> 16);
实际运行速度慢一些~~~

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则