打印

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

[复制链接]
楼主: highgear
手机看帖
扫描二维码
随时随地手机跟帖
61
Cortex-M0| | 2011-10-11 07:52 | 只看该作者 回帖奖励 |倒序浏览
highgear老师推荐的 三角函数逼近快速算法(正余弦)。
中文翻译在此:
http://friendz.blog.163.com/blog/static/857571322011288505934/

经简化后的所用公式为:
Q * (4/pi * x - 4/pi^2 * x^2) + P * (4/pi * x - 4/pi^2 * x^2)^2
其中 x^2 要做一次乘法,上式中,至少要执行 6次乘法,继续将上述公式化简,改写成:
(4/pi * x - 4/pi^2 * x^2) = ((4/pi - 4/pi^2 * x) * x)
代入后,也仅仅减少一次乘法,至少要执行 5次乘法,比俺在 57楼的算法多用 1次乘法。
更不要说《三角函数逼近快速算法(正余弦)》需要用到浮点数运算,执行速度和效率更低~~~

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
highgear + 1
62
Cortex-M0| | 2011-10-11 08:03 | 只看该作者
综上,还是highgear老师提出的一个很简单的题目:
完全用整数运算完成sin, atan 函数,所点内存资源少,运算速度最快。

紧跟highgear老师,邓喵老师,继续玩“非典”~~~

使用特权

评论回复
63
hq_y| | 2011-10-11 08:35 | 只看该作者
很给力的算法。。。。。:hug::victory::kiss:

使用特权

评论回复
64
zbb564833642| | 2011-10-13 10:37 | 只看该作者
哈哈  。顶起

使用特权

评论回复
65
uniquehope| | 2011-10-13 12:31 | 只看该作者
:L擂台

使用特权

评论回复
66
Cortex-M0| | 2011-10-13 14:30 | 只看该作者
继续灌水~~~

因电机的加减速算法,要用到开平方,在小系统中,俺不太喜欢用浮点数,太耗资源,想弄个整数的~~~

网上搜了一下,号称“快速”、“极速”的开平方算法程序一大把,经下载测试,速度都慢的像蜗牛~~~

倒是老外的经典开平方算法,速度快些~~~

俺将其改写后,用C51编译后,再手工优化,经测试,效率还是满高的,远比国内的号称“快速”、“极速”的开平方算法,要快很多~~~

上传给感兴趣的盆友参考~~~

使用特权

评论回复
67
Cortex-M0| | 2011-10-13 14:32 | 只看该作者
16位整数开平方 C程序


/**********************************************************************************************
* uint16  isqrt(uint16 value1)
*    16位整数开平方

        用  途      :中颖SH79/88/89F51系列MCU
        作  者      :许意义
        21ic  ID    :LAOXU
        中颖论坛    : bbs.21ic.com   
        日    期    : 2011-10-11  

**********************************************************************************************/

unsigned int isqrt(unsigned int x)      // 16位整数开平方
{ unsigned int xr, xr1;
  unsigned int q2;
  xr = 0;                    
  q2 = 0x4000;         
  do{ xr1 = xr + q2;
      if(xr1 <= x)
        { x -= xr1;
                  xr = (xr >> 1) + q2;
        }
      else  
            { xr >>= 1;            
        }
    }while(q2 >>= 2);         
  if(xr < x)
    { return(xr + 1);        
    }
  else
    {
          return(xr);
    }
}

使用特权

评论回复
评分
参与人数 1威望 +1 收起 理由
highgear + 1
68
Cortex-M0| | 2011-10-13 14:34 | 只看该作者
16位整数开平方 经优化后的 ASM程序,可编译成库。


 
$NOMOD51
NAME ISQRT
/**********************************************************************************************
* uint16  isqrt(uint16 value1)
*    16位整数开平方

用  途      :中颖SH79/88/89F51系列MCU
  作  者      :许意义
  21ic  ID    :LAOXU
  中颖论坛    : bbs.21ic.com   
日    期    : 2011-10-11  

**********************************************************************************************/

?PR?_ISQRT?ISQRT  SEGMENT CODE
PUBLIC _ISQRT
RSEG  ?PR?_ISQRT?ISQRT
;---- Variable 'x?040' assigned to Register 'R6/R7' ----
_ISQRT:  CLR   A        // 16位整数开平方
; { unsigned int xr, xr1;
;   unsigned int q2;
;   xr = 0;                    
;---- Variable 'xr?041' assigned to Register 'R2/R3' ----
   MOV   R3,A
   MOV   R2,A
;  R6>40H, q2 = 0x4000; R6>10H, q2 = 0x1000; R6>04H, q2 = 0x400; R6>01H, q2 = 0x100;           
;  R7>40H, q2 = 0x40;   R7>10H, q2 = 0x10;   R7>04H, q2 = 0x4;   R7>01H, q2 = 0x1;           
   MOV   DPH,A
   MOV   DPL,A
   MOV   A,#040H
   CJNE    R6,#40H,$+3
   JNC     ISQRT_7
   CJNE    R6,#10H,$+3
   JNC     ISQRT_8
   CJNE    R6,#04H,$+3
   JNC     ISQRT_9
   CJNE    R6,#01H,$+3
   JNC     ISQRT_10
   CJNE    R7,#40H,$+3
   JNC     ISQRT_11
   CJNE    R7,#10H,$+3
   JNC     ISQRT_12
   CJNE    R7,#04H,$+3
   JNC     ISQRT_13
   RR      A
   RR      A
ISQRT_13: RR      A
   RR      A
ISQRT_12: RR      A
   RR      A
ISQRT_11: MOV   DPL,A
   SJMP    ISQRT_1
ISQRT_10: RR      A
   RR      A
ISQRT_9: RR      A
   RR      A
ISQRT_8: RR      A
   RR      A
ISQRT_7: MOV   DPH,A
;   do{ xr1 = xr + q2;
ISQRT_1: MOV   A,DPL
   ADD   A,R3
   MOV   R5,A
   MOV   A,DPH
   ADDC  A,R2
   MOV   R4,A
;---- Variable 'xr1?042' assigned to Register 'R4/R5' ----
;       if(xr1 <= x)
   SETB  C
   MOV   A,R5
   SUBB  A,R7
   MOV   A,R4
   SUBB  A,R6
   JNC   ISQRT_2
;         { x -= xr1;
   CLR   C
   MOV   A,R7
   SUBB  A,R5
   MOV   R7,A
   MOV   A,R6
   SUBB  A,R4
   MOV   R6,A
;     xr = (xr >> 1) + q2;
   MOV   A,R2
   CLR   C
   RRC   A
   MOV   R4,A
   MOV   A,R3
   RRC   A
   ADD   A,DPL
   MOV   R3,A
   MOV   A,DPH
   ADDC  A,R4
   MOV   R2,A
;         }
   SJMP  ISQRT_3
;       else { xr >>= 1;            
ISQRT_2: MOV   A,R2
   CLR   C
   RRC   A
   MOV   R2,A
   MOV   A,R3
   RRC   A
   MOV   R3,A
;         }
;     }while(q2 >>= 2);         
ISQRT_3:    MOV   R4,DPH
   MOV   A,DPL
   MOV   R0,#02H
   INC   R0
   SJMP  ISQRT_5
ISQRT_4:    XCH   A,R4
   CLR   C
   RRC   A
   XCH   A,R4
   RRC   A
ISQRT_5:    DJNZ  R0,ISQRT_4
   MOV   DPH,R4
   MOV   DPL,A
   ORL   A,R4
   JNZ   ISQRT_1
   MOV   R4,A     // R4/R5 清0
   MOV   R5,A
;   if(xr < x)
   CLR   C
   MOV   A,R3
   SUBB  A,R7
   MOV   A,R2
   SUBB  A,R6
   JNC   ISQRT_6
;     { return(xr + 1);        
   MOV   A,R3
   ADD   A,#01H
   MOV   R7,A
   CLR   A
   ADDC  A,R2
   MOV   R6,A
   RET   
;     }
;   else { return(xr);
ISQRT_6: MOV   A,R2
   MOV   R6,A
   MOV   A,R3
   MOV   R7,A
;     }
; }  
   RET   
; END OF _ISQRT
   END

使用特权

评论回复
69
Cortex-M0| | 2011-10-13 14:35 | 只看该作者
32位整数开平方 C程序


/**********************************************************************************************
* uint32  lsqrt(uint32 value1)
*    32位整数开平方

        用  途      :中颖SH79/88/89F51系列MCU
        作  者      :许意义
        21ic  ID    :LAOXU
        中颖论坛    : bbs.21ic.com   
        日    期    : 2011-10-11  

**********************************************************************************************/

unsigned long lsqrt(unsigned long x)      // 32位整数开平方
{ unsigned long xr, xr1;
  unsigned long q2;
  xr = 0;                    
  q2 = 0x40000000L;         
  do{ xr1 = xr + q2;
      if(xr1 <= x)
        { x -= xr1;
                  xr = (xr >> 1) + q2;
        }
      else  
            { xr >>= 1;            
        }
    }while(q2 >>= 2);         
  if(xr < x)
    { return(xr + 1);        
    }
  else
    {
          return(xr);
    }
}

使用特权

评论回复
70
Cortex-M0| | 2011-10-13 14:36 | 只看该作者
32位整数开平方 经优化后的 ASM程序,可编译成库。



 
$NOMOD51
NAME LSQRT
/**********************************************************************************************
* uint32  lsqrt(uint32 value1)
*    32位整数开平方

用  途      :中颖SH79/88/89F51系列MCU
  作  者      :许意义
  21ic  ID    :LAOXU
  中颖论坛    : bbs.21ic.com   
日    期    : 2011-10-11  

**********************************************************************************************/
?PR?_LSQRT?LSQRT  SEGMENT CODE
?DT?_LSQRT?LSQRT  SEGMENT DATA OVERLAYABLE
EXTRN CODE (_ISQRT)
EXTRN CODE (?C?ULCMP)
EXTRN CODE (?C?ULSHR)
PUBLIC _LSQRT
RSEG  ?DT?_LSQRT?LSQRT
?_LSQRT?BYTE:
x?040:      DS   4
  ORG  4
xr?041:     DS   4
  ORG  8
q2?042:     DS   4
;xr?043:    DS   4  ---> DPL:DPH:DPL1:DPH1
DPL1       EQU   84H
DPH1     EQU   85H
RSEG  ?PR?_LSQRT?LSQRT
_LSQRT:     MOV   A,R4
   ORL     A,R5
   JNZ     LSQRT_1      // 16位整数开平方
   LJMP    _ISQRT
LSQRT_1: MOV   x?040+03H,R7    // 32位整数开平方
   MOV   x?040+02H,R6
   MOV   x?040+01H,R5
   MOV   x?040,R4
; { unsigned long xr, xr1;
;   unsigned long q2;
;   xr = 0;                    
   CLR   A
   MOV   xr?041+03H,A
   MOV   xr?041+02H,A
   MOV   xr?041+01H,A
   MOV   xr?041,A
;  R4>40H, q2 = 0x40000000; R4>10H, q2 = 0x10000000; R4>04H, q2 = 0x4000000; R4>01H, q2 = 0x1000000;           
;  R5>40H, q2 = 0x400000;   R5>10H, q2 = 0x100000;   R5>04H, q2 = 0x40000;   R5>01H, q2 = 0x10000;           
   MOV   q2?042+03H,A
   MOV   q2?042+02H,A
   MOV   q2?042+01H,A
   MOV   q2?042,A
   MOV     R0,#x?040
   MOV     R1,#q2?042
   MOV     R2,#2
   MOV   A,#40H
LSQRT_10:   CJNE    @R0,#40H,$+3
   JNC     LSQRT_2
   CJNE    @R0,#10H,$+3
   JNC     LSQRT_3
   CJNE    @R0,#04H,$+3
   JNC     LSQRT_4
   CJNE    @R0,#01H,$+3
   JNC     LSQRT_5
   INC     R0
   INC     R1
   DJNZ    R2,LSQRT_10
   DEC     R1
LSQRT_5: RR      A
   RR      A
LSQRT_4: RR      A
   RR      A
LSQRT_3: RR      A
   RR      A
LSQRT_2: MOV   @R1,A
;   do{ xr1 = xr + q2;
LSQRT_6: MOV   A,xr?041+03H
   ADD   A,q2?042+03H
   MOV   DPH1,A
   MOV   A,xr?041+02H
   ADDC  A,q2?042+02H
   MOV   DPL1,A
   MOV   A,xr?041+01H
   ADDC  A,q2?042+01H
   MOV   DPH,A
   MOV   A,xr?041
   ADDC  A,q2?042
   MOV   DPL,A
;       if(xr1 <= x)
   MOV   R7,x?040+03H
   MOV   R6,x?040+02H
   MOV   R5,x?040+01H
   MOV   R4,x?040
   MOV   R3,DPH1
   MOV   R2,DPL1
   MOV   R1,DPH
   MOV   R0,A
   SETB  C
   LCALL ?C?ULCMP
   JNC   LSQRT_7
;         { x -= xr1;
   CLR   C
   MOV   A,x?040+03H
   SUBB  A,DPH1
   MOV   x?040+03H,A
   MOV   A,x?040+02H
   SUBB  A,DPL1
   MOV   x?040+02H,A
   MOV   A,x?040+01H
   SUBB  A,DPH
   MOV   x?040+01H,A
   MOV   A,x?040
   SUBB  A,DPL
   MOV   x?040,A
;     xr = (xr >> 1) + q2;
   MOV   R7,xr?041+03H
   MOV   R6,xr?041+02H
   MOV   R5,xr?041+01H
   MOV   R4,xr?041
   MOV   R0,#01H
   LCALL ?C?ULSHR
   MOV   A,R7
   ADD   A,q2?042+03H
   MOV   xr?041+03H,A
   MOV   A,R6
   ADDC  A,q2?042+02H
   MOV   xr?041+02H,A
   MOV   A,R5
   ADDC  A,q2?042+01H
   MOV   xr?041+01H,A
   MOV   A,R4
   ADDC  A,q2?042
   MOV   xr?041,A
;         }
   SJMP  LSQRT_8
;       else { xr >>= 1;            
LSQRT_7: MOV   R7,xr?041+03H
   MOV   R6,xr?041+02H
   MOV   R5,xr?041+01H
   MOV   R4,xr?041
   MOV   R0,#01H
   LCALL ?C?ULSHR
   MOV   xr?041+03H,R7
   MOV   xr?041+02H,R6
   MOV   xr?041+01H,R5
   MOV   xr?041,R4
;            }
;     }while(q2 >>= 2);         
LSQRT_8:    MOV   R7,q2?042+03H
   MOV   R6,q2?042+02H
   MOV   R5,q2?042+01H
   MOV   R4,q2?042
   MOV   R1,#02H
   MOV   R0,#02H
   LCALL ?C?ULSHR
   MOV   q2?042+03H,R7
   MOV   q2?042+02H,R6
   MOV   q2?042+01H,R5
   MOV   q2?042,R4
   MOV   A,R4
   ORL   A,R5
   ORL   A,R6
   ORL   A,R7
   JZ    $ + 5H
   LJMP  LSQRT_6
;   if(xr < x)
   MOV   R7,x?040+03H
   MOV   R6,x?040+02H
   MOV   R5,x?040+01H
   MOV   R4,x?040
   MOV   R3,xr?041+03H
   MOV   R2,xr?041+02H
   MOV   R1,xr?041+01H
   MOV   R0,xr?041
   CLR   C
   LCALL ?C?ULCMP
   JNC   LSQRT_9
;     { return(xr + 1);        
   MOV   A,xr?041+03H
   ADD   A,#01H
   MOV   R7,A
   CLR   A
   ADDC  A,xr?041+02H
   MOV   R6,A
   CLR   A
   ADDC  A,xr?041+01H
   MOV   R5,A
   CLR   A
   ADDC  A,xr?041
   MOV   R4,A
   RET   
;     }
;   else { return(xr);
LSQRT_9: MOV   R7,xr?041+03H
   MOV   R6,xr?041+02H
   MOV   R5,xr?041+01H
   MOV   R4,xr?041
;        }
; }
   RET   
; END OF _LSQRT
   END

使用特权

评论回复
71
zal430521| | 2011-10-13 14:38 | 只看该作者
呼╭══╮ ┌══════┐
╭╯让路║═║╰纯属路过╮║
╰⊙═⊙╯ └══⊙═⊙═~

使用特权

评论回复
72
刘前辈| | 2011-10-13 19:38 | 只看该作者
本帖最后由 刘前辈 于 2011-10-13 20:08 编辑
23# highgear
多任务的实现说穿了很简单,就是利用定时中断打断当前运行的任务,把当前所使用的寄存器 push 到栈中,然后把切换到下一个任务的栈点,pop 出这个即将运行的任务现场,最后把运行权交给这个任务。可以看到,多任务的实现的关键点是中断,在 windows 下要实现打断运行的任务得到控制权,不是做不到,但非常复杂,所以在 PC 中应在 DOS 下实现,DOS 支持 bios 的0x10定时中断,稍加改造就可以是支持 1ms 的中断。


哈哈……几天没上21IC,不知道所长一直追着我PK。看来所长前一阵把5个哲学家喂成了猪,太有悖于“天下第一”的称号,如今一定要把自己21IC元老的声誉捞回来?

    算了吧,连题意还没搞清呢:大多数人都像所长23#似地,以为RTOS是多任务按时间片切换。为了防止临界区内切换,于是各种保护数据机制,互斥、信号量、消息传递……

     你也不想想,哲学家就餐,是RTOS 么?我正在吃饭,你按时间片来抢夺我的叉子!“别吃啦,到时间该我吃啦……”然后调度切换。你块头比我大?你是乌克兰猪?还什么“稍微的优先级”,——如今也觉得自己当时创新的OS理论很好笑吧。
  
     当今世界,OS理论研究早就成熟。十年前,20年前就有大师说OS理论研究已经结束。各种机制早就成熟,没有任何遗留问题。——咱中国的21IC所长突然创新了个什么“些微优先级”机制。在抢占和非抢占之间调度?呵呵,中国讲习所长的名字要载入世界OS发展史册了。

   DOS,LInux 早期版本都是非抢夺式内核;——我吃完饭,自动放弃2个叉子资源,同时唤醒两边饥饿等待的伙伴。——是让等待的伙伴重新再检测资源,还是我帮助伙伴检测他的叉子资源?这又是2种机制。

    所以,所长还是玩你的裸奔“些微优先级”吧,还什么RTOS?——连PK题目都出错了,和实时时限根本没关系,我在吃饭时,你再饥饿也得等。根本没有时限。

      否则就是猪。



、、

使用特权

评论回复
73
刘前辈| | 2011-10-13 19:57 | 只看该作者
本帖最后由 刘前辈 于 2011-10-13 20:13 编辑

“哲学家就餐”问题,咱早就研究透了。把独创的实验代码贴在这?所长你看得懂么?

呵呵,告诉LZ,3种解法:同步ASR通信机制,信号量AND集机制,管程机制。——前2种都是同步机制,(和时间片中断根本没关系。后一种管程机制纯粹是故意加上时间片抢夺式调度实验一下而已。)所长还是玩你的BIOS  1ms 中断吧。——连修改时间片都不会?书上有啊。每个哲学家的think/eat  模拟时间至少应该2秒钟以上,让人看得出停顿才行吧。LZ几百ms一闪而过,谁知道你的程序在干什么。



、、

使用特权

评论回复
74
highgear|  楼主 | 2011-10-13 21:04 | 只看该作者
顶老刘!给老刘鼓掌!

说真的,我们还真的没有看过老刘|冷漠 写过的代码,除了那个空间换时间”算法“的代码(当然那不是老刘的真正水平),甚至在哲学家就餐的问题上,仍然是口水一堆,代码全无,抄了一段代码,还不完整。
老刘,73 74楼不值得回复,喷口水没有意义。希望老刘能够用代码展示水平, 让众网友开开眼,让 highgear 无地自容一回。
.
.
.

请老刘在下一帖子简单地给一个回复:
1)  接受
2)  不接受

使用特权

评论回复
75
浪迹天涯WAN| | 2011-10-13 21:46 | 只看该作者
很激烈啊……围观

使用特权

评论回复
76
浪迹天涯WAN| | 2011-10-13 21:47 | 只看该作者
支持一下

使用特权

评论回复
77
Cortex-M0| | 2011-10-14 06:44 | 只看该作者
继续灌水~~~

使用特权

评论回复
78
SeaSun| | 2011-10-14 10:38 | 只看该作者
两位施主,佛法无边,回头是岸..... 阿弥陀佛.....:victory:

使用特权

评论回复
79
DownCloud| | 2011-10-14 16:04 | 只看该作者
看刘前辈解说,一定有很优秀的解决方法,期待刘前辈的代码,让小菜的我开开眼。

使用特权

评论回复
80
刘前辈| | 2011-10-14 18:28 | 只看该作者
本帖最后由 刘前辈 于 2011-10-14 19:04 编辑

呵呵,highgear 真是太看不起我了:中国你找不到一个教授像我这样写的“哲学家就餐”解法,那是我研究生优秀论文。我也只给教授看才舍得拿出来换个学位,到万方数据下载还得付40元,——每页2元。你舍得吗?
    你当我垃圾程序往这贴?你的喂猪程序还差不多。连个arr[2][3]都搞不清楚的人,还玩什么操作系统经典程序?
     透露一点点:所有人都用资源同步并发机制来解哲学家就餐问题,只有老刘一个人用的任务同步机制玩的就餐经典问题。(哈,所有的人向左,我必向右。)这令教授评委大跌眼镜,行吗?行不行我实验板显示给你看。结果优秀论文是肯定的,第一名只有一个;其他人都差不多一样,抄抄书而已,看谁能吹了。

    “如果没有实验(显示),任何理论(机制)都是对的”——丁肇中。(吹破天你也拿不了诺贝尔奖,哪怕喂猪都有人说你有新意,要向你学习。)

      所长你看不懂,你神童也没读过OS内核设计与实现专业研究生。在这扯什么劲,我没写过程序?我记得以前送你一篇我的论文“现场总线中的环形网”,结果让你尴尬不已。“这跟我有什么关系……”哈哈,看不懂恼羞成怒了。如果再送你一篇“哲学家就餐问题的管程解法”,那你不得背过气去?谁都知道,你没学过操作系统原理;所以没必要在这装懂。没学过你就看得懂OS程序?还在这装腔作势BIOS ?

     哈哈,没事,需要的话我贴一个proteus 图,带上我的hex 文件,让你开开眼看看5个哲学家是怎么轮转就餐的。

       你的呢?拿得出来?一堆乱码,——C++,C#,JAVA 一块儿上,就是没有输出给人看。结果仔细一看:切,玩裸奔呢——5个哲学家成了按顺序排队吃饭,假若每个人吃一小时,那么最后一个正餐还没吃完,第一个已经到了晚餐时间。——如此整天喂猪,我跟你PK?给你点面子不笑你就行了。

      我贴出来实验图有意思吗?除了让你无地自容。于是,又追着我PK下一个题目啦……脸皮太厚了吧……

       以前输给1952 多少次?输得下跪拜佛的情景我都旁观**了。如今又赖上我啦?有完没完?……

        要不要我把你怎么输给1952 的帖子挖坟都挖出来?忘了自己怎么被1952 涮出论坛的?如今连“讲习所长”的id 都不敢张扬了;——被人羞辱过了。

        提醒一下:1952 的“一道题……”事过3年,如今所长还是解不出来吧。这么简单的OS并发问题3年都解不出来,如今还在这摇头晃脑装,谁还陪你玩?



、、

使用特权

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

本版积分规则