arcaea吧 关注:56,438贴子:871,535

【真·科普】利用Arcaea的bug科普计算机原理

只看楼主收藏回复

这是一个关于计分bug的研究和修复建议,也是计算机科学的科普。这个bug的症状就是排行榜低分居上和实时分和结算分不同。如果仔细看,还可以发现当打出同样分数时,偏差值有时是+0,有时是-0。
为了通俗起见,我已经略去了很多专业术语,因此可能存在纰漏。计算机大佬麻烦纠正。
本bug已经向官方反馈,但是仍未收到明确答复
下面开始正文:


IP属地:广东来自iPhone客户端1楼2018-04-19 16:46回复
    在科普这个知识点之前,先出个小quiz:计算机中(20/200)*400和(20* 400)/200相等吗?


    IP属地:广东来自iPhone客户端2楼2018-04-19 16:47
    回复
      先介绍计算机储存数字的格式。有2种:整型和浮点型(这里只涉及正数)
      整型:只储存整数,方式是数位权值(和十进制一样的方式,每位权值的底数由10改为2,具体自行推断)
      浮点型:可以储存整数和小数,方式和科学计数法相似(类似于1.5 x 10^3),数据由指数和尾数2部分组成
      因为硬件原因,除非使用多个数据模拟,计算机无法直接计算分数


      IP属地:广东来自iPhone客户端3楼2018-04-19 16:56
      回复
        emmm楼·被·吞·了,现在申请恢复ing


        IP属地:广东来自iPhone客户端4楼2018-04-19 17:02
        收起回复


          IP属地:福建来自Android客户端5楼2018-04-19 17:04
          回复
            继续发下面的:
            浮点型的数据域
            先问一下:十进制中,如果不能用分数以及循环小数格式,如何表达1/3?答案是用近似,用0.33333333……来近似真值。那么问题是:如何用有限的储存空间来储存无限长的表达式?不可能的。由此可见,浮点型虽然可以表示小数,但是对于小数中的循环小数只可以通过近似来表达。它甚至不能精准表达0.1,因为其在二进制下无限循环。
            另外,由于储存的尾数空间有限,指数越高,浮点数数域越稀疏,近似误差越大。


            IP属地:广东来自iPhone客户端6楼2018-04-19 17:08
            回复
              说到近似,那一定要提及近似规则。近似规则的不一致导致了数据的稳定性的降低。一般来说生活中我们近似方法是四舍五入、直接取整...方法很多,结果都不尽相同。对于计算机而言,浮点运算近似的法则由硬件设计决定,即即使是同一个厂商的产品,不同的型号的计算器,计算出来的结果亦可能不同。甚至因为计算过程中对随机数的使用,即使是同一个主板上,算出来的结果亦会因时间而异。


              IP属地:广东来自iPhone客户端7楼2018-04-19 17:11
              回复
                相对而言,整型可以在最大数位约束的精确表达所有整数。


                IP属地:广东来自iPhone客户端8楼2018-04-19 17:29
                回复
                  说完储存说运算。整型的加减乘法是精确的,除法则是整除,直接截断,过程不产生小数。(具体可以看一下如何用Minecraft搭建计算器)


                  IP属地:广东来自iPhone客户端9楼2018-04-19 17:43
                  回复
                    浮点运算则复杂得多,在此不累述,但是可以算出1.0+0.00000001-1.0 = 0(还可能不是真正的0)。且稳定性很差。
                    换而言之,整型运算误差可能大于浮点运算,但是其稳定性远大于浮点运算,且不因设备而异。


                    IP属地:广东来自iPhone客户端10楼2018-04-19 17:45
                    回复
                      现在回到前面的quiz。后式结果分解:20*400 = 8000,8000/200 =40
                      前式分解:20/200 若为整除,结果为 0(int),最终结果是0;若为浮点运算除法(当前Arcaea算分方法),结果约为0.1(不等,原因上文)最终结果约为40.0(误差累积了)
                      现在虽然看不出来有什么不一样,但是如果精确到小数点后9位左右,误差就显现出来了。【现在arcaea就差不多这么精确】


                      IP属地:广东来自iPhone客户端11楼2018-04-19 18:07
                      回复
                        对于排行榜这种稳定度要求高的数据库,对象针对多平台的情况,最禁忌的就是在量程分度值级数相差悬殊的情况下使用浮点数进行运算(因为排序条件不可控而有失公平)


                        IP属地:广东来自iPhone客户端12楼2018-04-19 18:08
                        回复
                          所以if(abs(当前分数-历史最高分)<=e),e代表某个极小的数,这种方式是最好的,然而并没有什么卯用


                          IP属地:陕西来自手机贴吧14楼2018-04-19 20:21
                          回复
                            不你没有get到我的意思,我是指不要在计算分数时引入浮点计算


                            IP属地:广东来自iPhone客户端15楼2018-04-19 20:47
                            回复
                              虽然不太懂,但是好像很腻害的样子


                              IP属地:广东来自Android客户端16楼2018-04-20 13:46
                              回复