在各种文明的算术发展过程中，乘法运算的产生是很重要的一步。一个文明可以比较顺利地发展出计数方法和加减法运算，但要想创造一套简单可行的乘法运算方法却不那么容易。我们目前使用的乘法竖式计算看似简便，实际上这需要我们事先掌握九九乘法口诀表；考虑到这一点，这种竖式计算并不是完美的。我们即将看到，在数学的发展过程中，不同的文明创造出了哪些不同的乘法运算方法，其中有的运算法甚至可以完全抛弃乘法表。
    古巴比伦数学使用60进制，考古发现的一块古巴比伦泥板证实了这一点。这块泥板上有一个正方形，对角线上有四个数字1, 24, 51, 10。最初发现这块泥板时人们并不知道这是什么意思，后来某牛人惊讶地发现，如果把这些数字当作60进制的三位小数的话，得到的正好是单位正方形对角线长度的近似值：1 + 24/60 + 51/60^2 + 10/60^3 = 1.41421296296…  这说明古巴比伦已经掌握了勾股定理。60进制的使用为古巴比伦数学的乘法运算发展带来了很大的障碍，因为如果你要背59-59乘法口诀表的话，至少也得背1000多项，等你把它背完了后我期末论文估计都已经全写完了。另一项考古发现告诉了我们古巴比伦数学的乘法运算如何避免使用乘法表。考古学家们发现一些泥板上刻有60以内的平方表，利用公式ab = [(a+b)^2 – a^2 – b^2]/2 可以迅速查表得到ab的值。另一个公式则是ab = [(a+b)^2 – (a-b)^2]/4，这说明两个数相乘只需取它们的和平方与差平方的差，再两次取半即可。平方数的频繁使用很可能加速了古巴比伦人发现勾股定理的过程。
    古巴比伦数学把除以一个数看作是乘以它的倒数，利用倒数表可以很方便的实现这种算法。倒数表开头的一部分是这个样子：

2      0; 30
3      0; 20
4      0; 15
5      0; 12
6      0; 10
8      0; 7, 30
9      0; 6, 40
10     0; 6
12     0; 5
15     0; 4
16     0; 3, 45
18     0; 3, 20
20     0; 3
….    ….

    
    古巴比伦人很早就发现，1/7是一个无限小数，怎么除也除不完。古巴比伦的倒数表里所有的数都是精确的小数，它们（在60进制中）都是有限小数。碰到无限小数时，他们会用取近似值的方法来解决。例如，古巴比伦人会通过1/13 = 1*(1/13) = 7*(1/91) ≈ 7*(1/90) = 7*(40/3600) = (7*40)/3600 来计算1/13的值。那个40就是查倒数表查出来的。

    古埃及数学使用了完全不同的乘法运算法。它们的乘法运算不需要借助任何辅助用表。古埃及人注意到，任何一个数都可以表示为若干个不同的2的幂的和。因此，你需要做的仅仅是不断将1和乘数进行翻倍。看看古埃及人如何计算46乘以22：

  46 x 22 = 1012
   1   22
   2   44     44
   4   88   + 88
   8  176  + 176
  16  352
  32  704  + 704
          ——-
            1012

    上面的演算中，左列是1不断翻倍的结果，右边是22不断翻倍的结果。选出左列的2, 4, 8, 32，它们的和正好就是被乘数46；那么把右列对应的数加起来就是乘法运算的最终结果。至于如何选出2, 4, 8, 32这四个数，一个简单的方法就是，不断选出左列里小于被乘数的数中最大的一个，然后当前被乘数减去它。比如，32是最大的数，用46-32后剩14；8是小于14的最大数，14-8后剩6；然后最大的小于6的数是4，6减去4后剩2，这样下来2+4+8+32正好就是被乘数46了。这其实就是二进制的经典应用，2, 4, 8, 32正好与46的二进制中的数字1一一对应。你可以在这里看到一些相关的东西。
    无独有偶，据说俄国农村曾产生过这样一种乘法算术法：将被乘数逐次减半，同时乘数依次加倍，那么找出所有左边的数是奇数的行，其右列的数的和就是答案。例如，下面的例子中，23, 11, 5和1都是奇数，于是右边对应的44, 88, 176和704的和就是乘法运算的结果。这个做法与古埃及的算术法完全一样，但看起来似乎更神奇一些。

  46 x 22 = 1012
  46   22
  23   44     44
  11   88   + 88
   5  176  + 176
   2  352
   1  704  + 704
          ——-
            1012

做人要厚道
转贴请注明出处

    Morpion Solitaire是一个非常简单的单人棋类游戏。游戏开始前棋盘上摆好了36个棋子，这些棋子排成一个空心的十字架形。以后你放上去的每个棋子都必须和已有的四个子连成一条线（左图所示，就像五子棋那样）。唯一需要注意的是，同一个棋子在同一个方向上只能使用一次（即同一方向上的连线不能重叠，否则你就可以一条直线无限摆下去了）。每放下一个新的棋子你就得到1分，再没有新的棋子可摆时游戏结束。
    人们开始好奇，游戏最多可以走多少步。上面的右图一共走了68步，这个记录从99年开始一直保持了7年，直到06年才有人改进到了74步。最近，又一个新的记录诞生了，有人找到了一种79步的解法。它的解法如下图所示：
  

    这个游戏看似简单，但你真正玩一下你会发现游戏变化莫测。很可能这一次你走了60多步，但下一次你却只能走40多步。这是一个打发时间的绝佳方法，仅仅需要一张纸和一支笔就可以混过大半节古代汉语课，没准一不小心就破了世界纪录。有兴趣的话不妨也写个程序来搜索一下，看看你的程序能不能跑出一个80的解来。目前解的上界是141，下界是79，任何改进都可以发信到这个页面里的电子邮箱。

    这个游戏的另一个版本则是要求构造新的连线时已有的四个子中任两个都还不曾连接过（而不是同一棋子同一方向只能用一次），你可以在这里玩到一个在线的Java版本。这个版本更是变化多端，运气不好只能走出40多步，RP爆发可以超过150步，目前已经证明的上界则是324步。如果你能走到160步，你可以联系这里给出的邮箱地址（为什么我要翻墙才能看到这个页面？）。目前的最好记录是170步，如下图所示：
  

    图灵机是1936年Alan Turing提出的一个计算机模型。这种计算机由一个一维数组（或者叫磁带）构成，还有一个可以左右移动的指针。磁带上每个格子里都有一种颜色（共可从m种颜色中选择），指针本身则可以是n种状态中的一种。给定一个m*n的表格，你就定义了一个图灵机。这个表格告诉机器，如果当前指针的状态是x，它所指的格子的颜色是y，那么下一步机器应该把这个格子染成什么颜色，然后指针应该左移一位还是右移一位，指针的新状态又是什么。有了一个图灵机后，我们便可以把它当做一个计算机进行数据处理了。我们可以给这个图灵机编写一个初始状态（也就相当于现在所说的程序和数据），让它按照这个表格不断执行下去，对数据进行处理并“输出”适当的结果来。
    能够模拟其它所有图灵机的图灵机叫做“通用图灵机”(UTM, Universal Turing Machine)。不是所有的图灵机都是通用的：很多图灵机只能完成一些特定的运算，而只有通用图灵机才能完成更一般的操作，是一台“通用的”机器。这些通用图灵机就像现代计算机一样，可以用来编程执行各种各样的操作，能实现现代计算机的各种功能。我们经常说一种程序语言是图灵完全的(Turing Complete)，指的就是这种语言等价于通用图灵机，能够执行任何一种复杂的数学运算。
    50年代起，科学家们疯狂地寻找通用图灵机，所需要的颜色数和状态数越来越小。最好的结果是1967年由Marvin Minsky得到的，他发现了一个7,4通用图灵机，即一个只需要7种状态，4种颜色的通用图灵机。人们开始好奇，最简单的通用图灵机是什么样子的。2002年，Stephen Wolfram（没错，就是MathWorld的那个Wolfram）做出了一个重大的突破：他发现了一个2,5通用图灵机，并且给出了一个很可能是通用图灵机的2,3图灵机。很早以前人们就证明了，不存在2,2的通用图灵机；因此如果Wolfram提出的2,3图灵机是通用图灵机的话，它就是最小的通用图灵机了。但Wolfram始终不能证明这个2,3图灵机是通用的，于是在今年三月份用25000美元悬赏征解。
    昨天，英国伯明翰大学的一名20岁在校大学生Alex Smith提交了一篇55页的论文，证明了Wolfram的2,3图灵机与另一个已知的通用机器等价，从而证明了2,3图灵机是最简单的通用图灵机，证实了这个很早就已经提出的猜想，解决了长期以来计算机科学界的一大疑问。这是一个意义非常重大的突破，无疑是信息学界中的一件激动人心的大事。

做人要厚道 转贴请注明出处
新闻来源：来源1 来源2

    最近，波士顿Northeastern大学的计算机科学家Daniel Kunkle证明了任何一个魔方可以在26步以内解开。这个结果打破了以往所有的记录。在解魔方的处理过程中，他构造了一些非常具有启发性的算法，这篇文章将简单地介绍一下这些算法。
    一个魔方大约有4.3 x 10^19种可能的初始状态，再牛的机器也不可能搜索完所有的可能。因此Kunkle和他的指导员Gene Cooperman想出了一些对魔方状态进行分类筛选的策略。
    Kunkle和Cooperman首先运用了一个小技巧将问题进行简化。如果魔方的每个面全是一种颜色，我们就认为魔方被解开，不管哪一面是哪一种颜色。换句话说，相互之间可以通过颜色置换得到的初始状态都是等价的。这样，“本质不同”的初始状态就减少到10^18种。
    接下来，他们开始观察一类更简单的问题：如果只允许180度转动(half-turn)，有多少状态可以被解决。在10^18种状态中，只有大约15000种状态可以仅用180度旋转来破解。对于普通计算机来说，这个数目也不大，只需要不到一天的时间就可以搜索出解开所有15000多个魔方各自需要的最少步数。他们发现，这类初始状态中任何一个都可以在13步以内解决。
    然后他们需要做的就是找出，需要多少步才能把任意一种状态转化为这15000种特殊状态中的一个。为了完成这一工作，首先他们把所有的初始状态划分为若干个等价类，每个等价类里的状态都可以仅用180度转动互相得到。这样，同一个等价类中如果任一状态可以变换为其中一种特殊状态，同样的转动步骤也可以使该等价类的其它所有状态都变成特殊状态。最后他们找到了1.4 x 10^12个不同的等价类，需要解决的状态数由最初的4.3×10^19减少到1.4×10^12。但无论如何，10^12仍然是一个恐怖的数字。
    现在他们用了一台超级计算机来完成这个工作，并且使用了一些很有技巧性的决策来加速搜索过程。计算机需要耗费大量的时间读取硬盘上的数据，为了加快速度，Kunkle和Cooperman将数据巧妙地进行了处理，使得数据的排列正好与计算机读取的顺序相符，这样就节省了搜索硬盘的时间。
    “这种方法可以应用在任何一个组合问题上”，Kunkle说。他提到了西洋跳棋、国际象棋、航班安排和蛋白质摺叠等一系列问题。一种类似的组合学方法最近被用于寻找西洋跳棋的最优策略中。
    63小时的计算后，超级计算机得到的答案是，任何一种状态都能在16步以内转化为15000种特殊状态。而这些特殊状态又只需要13步达到最终状态，因此这种方法最终得到的结论是：29步以内可以解决任何一个魔方问题。
    但这个数字还不足以创造出新的记录，去年瑞典就曾经得到过27步内解决魔方问题的结论。Kunkle和Cooperman意识到，要想打破这个记录，他们还需要削减3步才行。
    应用他们现有的算法，只有8×10^7个状态集合还不能做到26步以内出解。再次对这些相对较少的状态进行搜索，最终他们找到了26步以内解决所有魔方的方法。
    7月29日他们在ISSAC(International Symposium on Symbolic and Algebraic Computation,国际符号和代数计算会议)上公布了这一结果。
    现在Kunkle和Cooperman希望把最大步骤数减少到25。他们认为他们可以对所有需要26步的状态进行暴力搜索来寻找更优的方案。
    虽然他们已经获得了很大的成功，但这一结果很可能还有改进的空间。许多学者认为20步以内足以解决任何魔方，但现在没有人能够证明。

Matrix67翻译，原文地址
做人要厚道，转贴请注明出处