Mengzelev's Blog

Lab1-乘法 实验报告

Word count: 1,428 / Reading time: 5 min
2018/10/12 Share

任务1:实现multimod

使用了高精度数乘法计算a*b,然后模拟手算除法的形式写了高精度除法(取模)。代码见文件p1.c.

正确性(伪)证明

使用python随机生成生成了1000000组a、b、m,0~9223372036854775807(int64_t的最大值)并计算对应答案,与p1.c的计算结果进行对比。

python随机数生成代码如下:

import random

MAX = 9223372036854775807

for i in range(1,1000000):
    a = random.randint(0,MAX)
    b = random.randint(0,MAX)
    m = random.randint(1,MAX)
    ans = (a * b) % m
    print (a,b,m,ans)

测试结果一百万组全对(从零开始计数的)

任务2:性能优化

由于是先听的课再做的lab,出于惰性直接按照jyy课上讲的方法做了(我去面壁)就不多解释了,代码见p2.c

时间测试思路

STFW找到了计算使用time.h库函数计算运行时间的方法,也有计算时钟周期的方法,但是后者使用了汇编代码,在对未知事物的恐惧(这样真的不好)的驱使下还是选择了比较好理解、比较好控制的前者。为了防止计算步骤被优化,又不能让多于的操作占用过多的时间,就使程序计算了正确的case的个数并输出。所以得到的时间应该比实际运行时间长一些。

运行时间


注:其中p1.c为任务一中的高精度实现,p2.c为任务二中的优化算法,p3.c为任务三中的神奇代码

运行时间分析

a,b,m的位数为n
高精度除法需要做O(n)次减法和比较,每次减法和比较的时间复杂度也都为O(n),因此总时间复杂度是O(n^2)
任务二中优化过的时间需要循环次数是O(n)的,每次循环的操作都能在常数时间O(1)内完成,因此总时间复杂度为O(n)
而神奇代码对任何输入消耗的时间都是相同的,时间复杂度为O(1)
从运行时间上来看的确是t(p1)>t(p2)>t(p3),符合预期
一个神奇的现象是,随着优化等级的升高,运行时间不一定缩短。尤其是p2.c的运行情况,O1和O2反而不如O0(虽然也只差了0.001ms),于是我反汇编对比了一下,发现multimodtestcasesmain几个函数的汇编代码几乎一模一样,但对应行的行数不同,可能是调用了不同的系统库函数。对优化的原理不太了解,暂时无法想到合理的解释。可能是因为这个程序的优化空间不是太大?但是编译器肯定比我智能多了,我想不到优化方法不能看不起编译器啊。

任务3:解析神秘代码

结论ab乘积不超过2^53次方,mint64_t范围内任意取值,可以保证multimod_fast总是能返回正确的数值

过程非常曲折,以下都是流水账碎碎念,老师嫌长可以不看,自己写着好玩,回头上传个人Blog

刚拿到手先试了一大堆随机数据,发现一百万组测试样例总只能过1w+组,正确率非常低。后来和同学讨论了一下,听说m比较小的时候结果最容易出错,我就把m的随机范围改成了1~3,果然错误率高了很多。大概是因为神秘代码中(int64_t)((double)a * b / m + 1e-8)强制类型转换后要除以m,如果m偏小,那么a*b的误差就很容易保存下来,引起答案出错。

保持m1~3的范围,我又试了几组大数。发现是在ab乘积为10^19左右的时候(a和b在算法找中地位是等价的,所以只需要关注ab的乘积的范围)会出现计算错误,于是在这个范围附近取了一些数,绝了,这个使结果正确的区间并不是连续的!然后理智烧却瞎测了几组数据,不太能发现规律,决定先冷静下来,从理论上思考一下算法。毕竟这次是关于数据表示形式的Lab嘛

这个神奇代码大概是把ab乘积转换为double类型。double类型能表示的范围是大于int64_t的,但是精度不够,尾数部分只有52位的精度(加上前面的1一共是53位),所以应该是只能保证这53位的精度,于是我打开python计算器计算了一下2^26.5 =,大概是94900000,于是我把任务一中随机数的生成范围改为了(0,94900000),测试了5次,每次一百万组,都是全对的。

到这里我就很想吐槽了,这范围怎么还能算int64_t的,保证结果正确的ab的范围int都达不到,如果能保证输入在这个范围之内,还不如直接用int64_t算呢,ab相乘肯定不会溢出的。但是如果ab乘积位表示下末尾零比较多,还是有可能正确的。所以这根本就是一份拼人品的神奇代码吗…..

目前尚未想通的问题:

  • 为什么要+1e-8
  • 为什么返回时需要判断t的正负并做相应修正?

最后,这个神奇代码毕竟是O(1)的,凭我的算法功底实在没办法优化到O(n)以下,所以神奇代码虽然正确率不高,但是效率还是很感人的

CATALOG
  1. 1. 任务1:实现multimod
    1. 1.1. 正确性(伪)证明
  2. 2. 任务2:性能优化
    1. 2.1. 时间测试思路
    2. 2.2. 运行时间
    3. 2.3. 运行时间分析
  3. 3. 任务3:解析神秘代码