今天下午的6级考试真是刺激阿，好久没做英语试卷了，做得狂慢。估计现在看编译原理也很慢，所以习惯慢慢看了。阅读听力都不担心，但是单项问题大了。每一题的每一个选项，没有一个单词认识的。改错也比较别扭，高考过后，还没有做过改错题。作文我奋笔疾书，真的是愤怒之笔阿，写了接近200字。最近，friends看多了，还有编译里面的英文都是比较简单的表达，所以这次作文，几乎没有用什么句式。

    4级就是一点没准备的，6级同样如此。不知道能得几分。不过本来也没有重视，随它去吧。今天考试前一个小时，我在看指环王，宿舍一个人在看friends，一个在看美女屏保同时听听力练习，还有一个在听英文歌。这就是我们为6级特别准备的复习。whatever，总算过去了。等候考试真是劳民伤财。

这是一道acm中国决赛题，在csdn上看到关于这道题的讨论。

有2个数，100，0000长度，要求计算两个数的乘积。要求2秒内给出结果。

测试文件格式如下：

input.txt

123,456

2,4

output.txt

56088

8

这道题用传统方法计算是绝对不可能出来结果的。如果只是用数组保存乘数，手动计算乘法的话，大概需要1个小时可以出来结果。网上有人提示用fft，当时没有想到怎么去做。我这几天看了一下信号与系统这本书，看到一条性质，有了一个解法。

这条性质是：x(t) * h(t) <-> X(e)H(e)

实际上，对照卷积和的概念，就会发现其实卷积和的运算和乘法运算很相似。卷积和要累加过去信号的响应，乘法要处理低位的进位。所以，如果把2个储存乘数的数组，一个看作信号，一个看作系统脉冲响应，做卷积和，得到的系统输出信号就是乘积。

这样，这题就可以变为，求两个100，0000长度的信号的卷积了。根据时域卷积对应于频域乘积，我们可以首先分别用快速傅里叶变换把2个信号变到频域，然后在频域做成绩，最后在反变换回来。就得到我们要的乘数了。

听起来复杂了很多，实际计算速度到底怎么样呢？

不妨设两个乘数长度都为n，传统的累加乘法，需要n^2次乘法和n次加法。而长度为n的快速傅利叶变换，首先不考虑n/2次计算e指数的计算，需要2nlog(n)的乘法和2nlog(n)的加法。两个信号加上反变换共是8nlog(n)次乘法 和8nlog(n)次加法。频域乘积是n次乘法。如果每次e指数计算，是常数次计算乘法，那n/2次e指数计算也是O(n)次计算乘法。所以，总的来说，粗略的估计，fft计算总共需要8nLog(n)+k(n)次乘法，8nLog(n)次加法。而传统需要n^2次乘法。我们令n= 100，0000。那么传统方法需要10^12次乘法，而快速傅里叶方法需要160*10^6 + k*10^6次乘法，k不会很大，据我所知，就算用泰勒公式展开e指数计算，计算10次已经收缩得误差很小了。那么，传统方法的乘法计算两还是fft方法的5*10^3倍，这意味着，传统方法计算1小时的数据，用fft只需要计算1.8秒。

现在比较忙，稍后几天我会做实验验证这个结果。

    明天是我和恋牵手一周年的日子。我清楚记得那天晚上发生的故事，胳膊被搂住的感觉，惶惶心跳的刺激还有迟到的尴尬。过去的一年发生很多事情，大家都变化好大，唯一不变的是记忆。

    明天又是12月18日了，我现在single，整天为作业忙的要死，星期日就拼命睡觉。偶然停住的时候，会想想，一年已经过来了，我的变化还真大，感谢恋。分手是我的责任，我没有把握住。

     今天早上很早就起床9点半不到，去殷巷买了一条刀鱼和6两虾。中午在宿舍清蒸刀鱼，晚上煮盐水虾。lift tastes good!

     发现自己做饭听不合算的，我清理鱼，打扮鱼花了接近1个小时，蒸熟又花了1个小时，所以我等了很久才吃到。第一次蒸不是很成功，好似生姜味重了一点，不过吃起来还是相当的好地，比食堂那等阿扎破才好多了。

    下午睡午觉睡到晚上8点半，起来剪虾，然后学我叔叔，葱没有切，整个的放进去，煮好后葱一起捞出来丢掉。虾煮的时候红的很快，不过感觉还是生虾更有诱惑力，看着透明的虾肉就想咬，但是没有酒，也没有亲自看人做过醉虾，所以暂时不敢乱来，害怕吃出问题。煮虾的时候，闻起来非常的香，煮好后吃起来感觉就没有闻起来好，不知道为什么！！虾煮的很好吃的，但是感觉就是没有闻起来好，太奇怪了，跟方便面一样，闻起来很不错，吃起来差远了。

    这周过的比较糜烂，昨天吧，起来吃了饭就睡了，晚上起床吃了饭，又睡了。今天，早上起来忙午饭，吃过就睡了，晚上起来，现在刚吃完。还没打算睡，要写作业

    上学期的奖学金发下来了。上学期一共2门必修课都得到了单科奖学金，概率和信号与系统。信号现在回想还是心有余悸的科目，呵呵。上学期概率上课基本没听，谁让他早上1，2节开课，我怎么可能听课。还有，概率老师总是唠唠叨叨，就盼着我们重修，我才不跩他呢！概率的满分就是对传统教育方式的挑战！你说我们必须听课才能及格我就偏偏不听课，看你能把我怎么样。不过老师还是有师德的，没有因为我上课睡觉扣我1分。曹老头威力强筋阿！当然，坦诚的说，我概率只是考好了而已，因为我作弊了——我看了前几年的考试卷，我还做了很多习题。

    今天的讲座效果还不错，因为准备的比较多，所以讲的时候也有东西讲，同时，能够把office用的比较熟的人还是很少很少的，比能把C++用好的人少多了。

    今天以后就可以休息一下，开始好好学习了，好多作业要补阿。这几天准备的很卖力阿，上学期学3D的时候都没有这么拼命。的确很累，不过还是有收获的，我的office应用技术大为提高，我以后可以很自信的说我会使用office了。

    前天在桃园食堂吃饭的时候和桃园美眉打了hi，她回我hi。感觉美死了！旁边的同学疾呼“什么天理阿！”美啊，我和“林志玲”打招呼了。如果告诉本部的人，我和湘园美眉打招呼了，他们也会馋死的吧，哈哈，呵呵，hoho！

    2周前做的简单的3D图形库的数学变换和映射部分。还不知道怎么取样会比较好，所以只是显示了几个单色面。也作了简单的光线折射。下一步要做的就是逆映射和采样了。不知道。net里面有没有类似汇编语言的东西，如果有，不知道有没有simd指令，有的话就可以大大提高运算效率了。上图：这是渲染得一个立方体。可执行文件下载

    今天scda的联谊会搞得很不错，由衷地说。可惜地面太滑，我们的双节棍表演被滑倒2次。跳舞的时候，舞协的人教的太快了，根本没学会。屁股扭得跟黄瓜藤似的，就是扭的不像拉丁。今天的舞会上，后期，女生比男生多，真让我吓了一跳，东大除了女生宿舍还会有女生比男生多的地方，真是怪哉。而且，不少女生还是质量不错的。可惜没找到合适的猎物阿，我这个猎手还不够职业。不过能找陌生女孩跳舞已经很需要勇气了，不是脸皮阿。

    我开始担心我们社团的元旦晚会能不能搞得比这个更好了。毕竟，可以看出来，她们准备很辛苦，而且很关键的她们女生很多。 这在东大绝对是战略性资源。ch同志压力重大啊。

    晚会到最后跳兔子舞，全场跳，这个时候当然要找个女生扒着了，呵呵。很久不运动了，调了一半， 岔气。这个身体啊，都熬夜熬坏了。

    今天来的人比我们预期的少很多。最后的我的演示没能正常运行，学校的机器没有.net fw2.0。不过我当时准备的就是尽量简短，因为当初安排的时候就是这么收到通知的。不过，短的有点夸张了。我应该带笔记本的。不过，总算结束了。这周实在是累得半死。腰都几乎直不起来了。周三做verylog到凌晨6点钟才做好，现在休息了一下，才感觉身体累得走路都困难。闭上眼睛就能感觉到眼睛的酸涩不堪。明天跳舞，要好好开心一下。顺便狩猎，哈哈，我没有那么坏啦。

    下周就是我们Double S组的活动了，还要忙一忙。