Category Archives: 计算机

伪随机数使用之误(一)

给定一个伪随机数生成器rand(),假定它已达到一个理想状态,即输出的值满足0到RAND_MAX上的均匀分布。

对于小于RAND_MAX的正整数n,如何通过rand()得到一个0到n之间的随机数?

常规方法是这样的:

result = rand()%(n+1);

事实上,得到的结果并非均匀分布。例如:当n=RAND_MAX*2/3时,result为0 — n/2中某个数的概率是其为n/2+1 — n中某个数的概率的两倍。(这是差距最大的一种情况)

应该使用这种方法:

do{

    result = rand();

}while( result > n );

但这种方法有个缺点:rand()的运算次数满足几何分布,故期望为:(RAND_MAX+1)/(n+1)。当n较小时,效率太低。

一种折中方案是:

do{

    result = rand();

}while( result >= (RAND_MAX+1)/(n+1)*(n+1) );

result = result%(n+1);

这种算法具有较好的效率,唯一的缺点是:在实际使用时,需考虑RAND_MAX+1是否会造成溢出。

我们的下一个问题是:

对于大于RAND_MAX的正整数n,如何通过rand()得到一个0到n之间的随机数?

 

读《C专家编程》

图书馆有本《C专家编程》,但似乎没有被人读过。这是本值得翻一翻的书。

理解C语言,最重要的在于认识它的设计思想及优劣。

C与Unix是相辅相成的,两者的思想也几乎一致。

比如,C强调一切由程序员实现,也因此,程序员需要保证自己程序的准确。malloc了内存,需要delete,而没有runtime的垃圾回收;在数组操作中,不对下标进行越界检查,如果要程序稳健,就自己实现吧。伴随着这些不便的,是程序员对程序无比精确地掌控,你永远都能(至少理论上能)了解自己的程序做了什么。

Continue reading

Windows or *nix?

技术人员总是乐于争论Windows和Unix/Linux的优劣,而且hack程度越高,越是偏向于后者。

其实作为终端用户,我们完全不必偏执。

技术实现不同、历史发展不同、社区文化对立……了解、理解就够了,何必非得分出孰是孰非。

举个例子。微软的Office是最为便捷强大的所见即所得办公软件,而充满Unix文化的各类TeX系统,则一直骄傲于自己对排版的精确控制独一无二。

然而LaTeX的发明者Leslie Lamport 被问到“当前为什么没有(基于TeX的)高质量所见即所得排版系统?”时,回答道:“门槛太高了,一个所见即所得的排版系统要做到 LaTeX 当前的水平,工作量之大不是单枪匹马所能完成的。微软这样的大公司可以做,但是市场太小了。”

在Windows还是*nix上,始终兼容并包,至少有三种好处:

1、作为用户,哪种合适用哪种,有益于自己的工作;

2、作为开发者,认识自己的不足、吸纳对方的优点、分析差距的原因,有助于改进产品,让世界更美好;

3、作为旁观者,没有什么比中立地看两个人辩论更长见识的了。

所以写下这篇日志,防止自己哪天又头脑一热拜倒在Unix/Linux的石榴裙下。