“教”电脑怎么做加法？

Question

问题是教计算机做加法。计算机知道一个数字:他“知道”1等于2，2等于3，以此类推。有了那个数据计算机就可以很容易地得到下一个数字。

其次，计算机有x+0=x和x+(y+1)=(x+1)+y的知识。这个公理让计算机做加法。例如，要将5和3相加，计算机会生成以下代码：5+3 = 5+(2+1) = (5+1)+2 = 6+2 = 6+(1+1) = (6+1)+1 = 7+1 = 8。

但是，以这种方式添加数字太长了。问题是利用数学和逻辑的规则来开发程序来改进这种加法方法。目标应该是加法必须在O(log(N))时间内执行，而不是O(N)时间，N是加数的大小。

这个项目有没有什么科学价值？有没有什么程序可以做这样的事情？

Answer 1

那些不懂算术的automatic theorem provers会按照你的建议去做:每次需要的时候，他们都会试图从定义中重新定义算术。结果呢？它的效果不是很好。您可以通过提供有关算术的更高级别的一般事实来帮助这些证明者(或者作为公理，或者如果您是严格的，就像引理单独证明的那样)。例如:结合性，交换性，...

它仍然不能很好地工作。似乎总是有一个更直观的显而易见的事实，即您需要为工具提供您感兴趣的特定证据。例如，x>y => x>=y，z要么是奇数，要么是偶数，这样的属性...

为了弥补这个问题，一些自动定理证明器确实在内部处理算术。在这种情况下，结果会更好。Simplify和alt-ergo就是这样的两个例子。

Answer 2

我不认为这里有太多的智慧。您的“计算机”可以remember以前添加的结果。具有无限的内存和足够长的训练周期，它将为任意两个数字建立(X，Y) -> X+Y的映射，这允许执行O(1)中的加法。任何智慧都无法超越这一点。

Answer 3

好吧，考虑一下这一点:计算机只处理二进制数，因此所有的计算都是在二进制级进行的。当比较两个数字时，计算机应该检查两个数字的长度是否相同，并在最短数字的左侧添加0。然后，当两者长度相同时，计算机开始从左到右比较位。只要两者都是1，它们就是相等的。如果两者都是0，那么它们是相等的。如果一个是0，则是较小的数字，而另一个是较大的数字。这就是如何确定数字的顺序。

现在加上两个数字。这一次从右边开始，如果两位都为0，则结果为0。如果一个是1，另一个是0，则结果为1。如果两个都是1，则结果为0，并将1加到左侧的两位上。向左移动一个，然后重复。然后将您刚刚移动的1添加到结果字节，这可能会导致另一个1向左移动。有趣的是，你只需要在左边加一次1。在任何情况下，你都不需要向左移动两个1。

基本上，这就是处理器如何学会将两个数字相加。

当你开始处理大于0和1的数字时，你只会增加数学问题的复杂性。考虑到你的例子，你已经把它分成了1。基本上，如果你要添加5+3，你会把它分成(1+1+1+1+1)+(1+1+1)，也就是8个1。把它翻译成二进制，你就会得到101+011。右边的两个1转换为0，移动1。然后1+0为1。加上被移位的1，它又回到了0，向左移动了1。然后你得到0+1，它又是1。加上你记住的1，结果是0，向左移动1。那里没有数字，所以假设两者都是0。0加1等于1。没有更多的班次，所以计算完成了，你得到1000。

许多年前，当他们开发出第一台计算机时，你可能已经考虑到了你所想要的东西，但二进制方法更有效。(尤其是在处理大量数据时。)