整数除法仅使用加法，乘法，减法和最大值 [英] Integer division using only addition, multiplication, subtraction and maximum

问题描述

假设我们有一种编程语言&＃x2124;其语法如下：

Suppose we have a programming language ℤ which has the following syntax:

ℤ := 0 | 1 | (+ ℤ ℤ) | (* ℤ ℤ) | (- ℤ ℤ) | (max ℤ ℤ)

为方便起见，我们可以用我们的语言定义新的绑定表格，如下所示： / p>

For convenience, we can define new binding forms in our language as follows:

1. （不是x）=（ - 1 x）


2. （abs x）=（ - （最大0（+ xx））x）


3. （min xy）=（ - 0（max（ - 0 x）（ - 0 y）））


4. （零x）=（不（min 1（abs x）））

1. (not x) = (- 1 x)
2. (abs x) = (- (max 0 (+ x x)) x)
3. (min x y) = (- 0 (max (- 0 x) (- 0 y)))
4. (nil x) = (not (min 1 (abs x)))

这种语言足够强大到表达分支和比较运算符：

This language is powerful enough to express branching and comparison operators:

1. （如果xyz）=（+（* xy） （*（不是x）z））


2. （eq xy）=（nil（ - xy））


3. （ne xy）=（not（eq xy））


4. （le xy）=（nil（max 0（ - xy）））


5. （gt xy）= （不是（le xy））


6. （ge xy）=（le yx）


7. （lt xy）=（not（ge xy））

1. (if x y z) = (+ (* x y) (* (not x) z))
2. (eq x y) = (nil (- x y))
3. (ne x y) = (not (eq x y))
4. (le x y) = (nil (max 0 (- x y)))
5. (gt x y) = (not (le x y))
6. (ge x y) = (le y x)
7. (lt x y) = (not (ge x y))

现在，问题是我们是否可以定义整数除法是这种语言：

Now, the question is whether we can define integer division is this language:

1. （div xy）=？


2. （rem xy）=（ - x（* y（div xy）））

1. (div x y) = ?
2. (rem x y) = (- x (* y (div x y)))

我不认为可以定义（div xy）因为&＃x2124;没有循环。但是，我不知道如何证明这一点。请注意，如果可能，那么（div x 0）的结果无关紧要。因此，要么定义（div xy），要么证明不可能这样做。

I don't think that it's possible to define (div x y) because ℤ doesn't have loops. However, I don't know how to prove it. Note that if it's possible then the result of (div x 0) doesn't matter. Hence, either define (div x y) or prove that it's impossible to do so.

推荐答案

这是不可能的。

调用函数 f：Z - > Z 最终是多项式如果存在多项式 p ，则整数系数和阈值 t 这样，对于每个 x> t ，我们有 f（x）= p（x）。设 d（x）= [x / 2] 为二等分。 d 最终不是多项式，因为 d 的差分序列具有无限多个零（ f （2y）= y = f（2y + 1）对于所有 y ），而每个非常数多项式的差分序列有限许多。它足以证明所有可实现的函数最终都是多项式的。

Call a function f : Z -> Z eventually polynomial if there exists a polynomial p with integer coefficients and a threshold t such that, for every x > t, we have f(x) = p(x). Let d(x) = [x/2] be floor division by two. d is not eventually polynomial, because the difference sequence of d has infinitely many zeros (f(2y) = y = f(2y+1) for all y), whereas the difference sequence of every non constant polynomial has finitely many. It suffices to show that all implementable functions are eventually polynomial.

证明通过结构归纳来进行。 0 和 1 是多项式。直接表明最终多项式函数的和，乘积和差异最终是多项式：使用两个阈值的最大值以及在这些操作下闭合多项式集合的事实。剩下的就是 max 下的关闭。

The proof proceeds by structural induction. 0 and 1 are polynomial. It's straightforward to show that sums, products, and differences of eventually polynomial functions are eventually polynomial: use the max of the two thresholds and the fact that the set of polynomials is closed under these operations. All that remains is closure under max.

让 f 最终通过多项式 p 多项式， g 最终通过多项式 q多项式。如果 p = q ，那么显然 x | - > max（f（x），g（x））最终通过相同的多项式进行多项式。否则，请注意 p - q 有多少实根。将阈值设置为根的上限，我们观察到max函数最终是多项式的，通过 p 或 q 因为max的另一种情况永远不会在这里触发。

Let f be eventually polynomial via a polynomial p, and g be eventually polynomial via a polynomial q. If p = q, then clearly x |-> max(f(x), g(x)) is eventually polynomial via the same polynomial. Otherwise, observe that p - q has finitely many real roots. Setting the threshold to an upper bound on the roots, we observe that the max function is eventually polynomial via p or q since the other case of the max never triggers here.

这篇关于整数除法仅使用加法，乘法，减法和最大值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！