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

highgear · 发表于 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次乘法。
更不要说《三角函数逼近快速算法(正余弦)》需要用到浮点数运算，执行速度和效率更低~~~

发表于 2011-10-11 08:03

综上，还是highgear老师提出的一个很简单的题目:
完全用整数运算完成sin, atan 函数，所点内存资源少，运算速度最快。

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

发表于 2011-10-11 08:35

很给力的算法。。。。。:hug::victory::kiss:

发表于 2011-10-13 10:37

哈哈。顶起

发表于 2011-10-13 12:31

:L擂台

发表于 2011-10-13 14:30

继续灌水~~~

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

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

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

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

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

highgear · 发表于 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);
}
}

发表于 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

发表于 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);
}
}

发表于 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

发表于 2011-10-13 14:38

呼╭══╮　┌══════┐
╭╯让路║═║╰纯属路过╮║
╰⊙═⊙╯　└══⊙═⊙═~

发表于 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题目都出错了，和实时时限根本没关系，我在吃饭时，你再饥饿也得等。根本没有时限。

   否则就是猪。

、、

发表于 2011-10-13 19:57

本帖最后由刘前辈于 2011-10-13 20:13 编辑

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

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

、、

发表于 2011-10-13 21:04

顶老刘！给老刘鼓掌！

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

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

发表于 2011-10-13 21:46

很激烈啊……围观

发表于 2011-10-13 21:47

支持一下

发表于 2011-10-14 06:44

继续灌水~~~

发表于 2011-10-14 10:38

两位施主,佛法无边,回头是岸..... 阿弥陀佛.....:victory:

发表于 2011-10-14 16:04

看刘前辈解说，一定有很优秀的解决方法，期待刘前辈的代码，让小菜的我开开眼。

发表于 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年都解不出来，如今还在这摇头晃脑装，谁还陪你玩？

、、

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

评分

评分

浏览过的版块

核心会员奖章

坚毅之洋流

七世轮回

技术高手奖章

欢快之小溪

以坛为家

希望之星奖章

伴坛终老

技术奇才奖章

社区建设奖章