最初看到这个问题是初中的时候买了一本有关数学谜题的书里面概率论的一张的课后拓展就是说到三门问题,当时作为一个扩展阅读看了一下,里面说到了一个世界智商最高的女人秒杀了美国一大群的数学高材生的精彩故事(比较夸张),当时对这个问题也是似懂非懂。

Read More

这个是今天看的一个小视频,分享给大家。

如今互联网的出现颠覆了很多东西,给我们带来了很多的方便,但是我们渐渐发现,我们似乎也正在失去一些很珍贵的东西。

Read More

1.快速求幂算法

在这篇文章我会展示怎样通过求一个数的幂的基本思路来引导我们发现一些抽象的东西比如半群和含幺半群。

有一个很有名的对一个数求幂的算法,也就是说,求一个数x的n次方或者这样简单表示:x^nDonald KnuthTAOCP4.63节 求幂值中提出这个算法。

这个算法很简单的实现就是x乘以自己n次,但是在这里当然会提供一种比这种方式更快的算法。正在谈论的算法通常被称作二进制法(binary method)梯度求幂(the powering ladder)或者反复平方法(repeated-squaring algorithm)

假设我们想计算2^23,在这里x = 2,n = 23,这个算法首先把23表示成二进制的形式10111.扫描这个二进制数(10111)每当遇到01,则相应的求x的平方或者乘以x

这个方法有一个问题就是它扫描二进制表示的数是从左到右进行的,但是对于计算机通常以相反的方向能够更容易实现,因此Knuth提出一个替代的算法。

Read More