5 ms·

Can someone explain this sentence to me? (In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?)

by lokedhs 10y ago

Can someone explain this sentence to me? (In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?) f(a, b) produces at most a or b, whichever is greater: f(a, b) ≤ max(a, b) As far as I can tell, the result can never be greater than the smaller of a and b. I can't come up with a counterexample. Is there one?

eximius 10y ago
I think you're right. By definition it can't have any more 1's that the lesser has and it might have less 1's than the lesser has.
nthacker 10y ago
Yeah for an AND function, f(a,b) <= min(a,b)
deleted 10y ago
[deleted]
Gankro 10y ago
You're correct, it can be changed to `min(a, b)`. A rough proof: * assume WLOG `a = min(a, b)` * `a & b` takes the set bits of `a` and produces a subset of them * the value of an integer is `SUM 2^j` where the j-th bit is set * removing positive elements from a sum can only make it smaller * therefore & can only produce a value smaller than `a` (the minimum)
- deleted 10y ago
  [deleted]
Strilanc 10y ago
A counterexample is 0 & -1 == 0.
- thedufer 10y ago
  The given function is clearly only defined over naturals. In the first part using bits, there's no indication of how to encode negatives, and in the second part with the sum equation, f(-1,-1) >= 0 (and thus not equal to -1) for any reasonable definition of the modulo function paired with any `b`, which breaks one of the stated identities. In fact, that's true if you replace mod with _any_ function.
  - Strilanc 10y ago
    > The given function is clearly only defined over naturals. The post doesn't specify. Programming languages do define it over the negatives, however. I just didn't want anyone going into python and asserting that a & b >= min(a,b). > there's no indication of how to encode negatives Just do the standard thing: use 2s complement arithmetic [1]. More concretely: set b to infinity and take the limit under the 2-adic metric [2]. For example, -2 & -1 has partial sums 0, 10, 110, 1110, 11110, etc. It's limiting to ...1111110, which is the 2's complement representation of -2. 1: https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement 2: https://en.wikipedia.org/wiki/P-adic_number https://en.wikipedia.org/wiki/P-adic_number
    - TTPrograms 10y ago
      I'm not quite sure they have enough paper for numbers with infinite boolean expansions.
    - thedufer 10y ago
      The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?
      - Strilanc 10y ago
        Pick any `b` you want, even infinity, and evaluate: sum_n^b 2^n (floor(0/2^n) mod 2) (floor(-1/2^n) mod 2) sum_n^b 2^n * 0 * 1 sum_n^b 0 0
escape_goat 10y ago
There is not, and there cannot be. However, even if he was figuring this all out from scratch, he could not have come up with the hand-written charts without realizing that. I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance. However, I cannot present to you the crucial difference between the maximum of two numbers and the minimum of two numbers that explains what he was thinking. This must exist for my hypothesized explanation to make sense.
- thaumasiotes 10y ago
  > I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance. It's worse than that; he mentions the identity function only to make a gross error about it. The identity function on (a, a) is (a, a), not a.
  - coinomega 10y ago
    I don't think you need to be so unforgiving? If you want extra precision, a -> f(a, a) is Id. Knowing that helped me understand one property of the chart, never said that was the most stunning of properties, and the best articulated one :-)
    - thaumasiotes 10y ago
      > If you want extra precision, a -> f(a, a) is Id. What does this mean?
      - coinomega 10y ago
        The function which to any integer a associates f(a, a) with f defined as in the article is the identity function on the natural integer set.
bnegreve 10y ago
> In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧? '∧' usually denotes the logical AND operator, which does not operate on integer values, (i.e. writing 22 ∧ 78 = 6 is weird). So it's not a bad idea to give this function a different name. He could have made that explicit though.
- deleted 10y ago
  [deleted]

by lokedhs 10y ago

eximius 10y ago

I think you're right. By definition it can't have any more 1's that the lesser has and it might have less 1's than the lesser has.

nthacker 10y ago

Yeah for an AND function, f(a,b) <= min(a,b)

deleted 10y ago

[deleted]

Gankro 10y ago

You're correct, it can be changed to `min(a, b)`. A rough proof: * assume WLOG `a = min(a, b)` * `a & b` takes the set bits of `a` and produces a subset of them * the value of an integer is `SUM 2^j` where the j-th bit is set * removing positive elements from a sum can only make it smaller * therefore & can only produce a value smaller than `a` (the minimum)

deleted 10y ago
[deleted]

Strilanc 10y ago

A counterexample is 0 & -1 == 0.

thedufer 10y ago
The given function is clearly only defined over naturals. In the first part using bits, there's no indication of how to encode negatives, and in the second part with the sum equation, f(-1,-1) >= 0 (and thus not equal to -1) for any reasonable definition of the modulo function paired with any `b`, which breaks one of the stated identities. In fact, that's true if you replace mod with _any_ function.
- Strilanc 10y ago
  > The given function is clearly only defined over naturals. The post doesn't specify. Programming languages do define it over the negatives, however. I just didn't want anyone going into python and asserting that a & b >= min(a,b). > there's no indication of how to encode negatives Just do the standard thing: use 2s complement arithmetic [1]. More concretely: set b to infinity and take the limit under the 2-adic metric [2]. For example, -2 & -1 has partial sums 0, 10, 110, 1110, 11110, etc. It's limiting to ...1111110, which is the 2's complement representation of -2. 1: https://en.wikipedia.org/wiki/Two%27s_complement https://en.wikipedia.org/wiki/Two%27s_complement 2: https://en.wikipedia.org/wiki/P-adic_number https://en.wikipedia.org/wiki/P-adic_number
  - TTPrograms 10y ago
    I'm not quite sure they have enough paper for numbers with infinite boolean expansions.
  - thedufer 10y ago
    The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?
    - Strilanc 10y ago
      Pick any `b` you want, even infinity, and evaluate: sum_n^b 2^n (floor(0/2^n) mod 2) (floor(-1/2^n) mod 2) sum_n^b 2^n * 0 * 1 sum_n^b 0 0

escape_goat 10y ago

There is not, and there cannot be. However, even if he was figuring this all out from scratch, he could not have come up with the hand-written charts without realizing that. I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance. However, I cannot present to you the crucial difference between the maximum of two numbers and the minimum of two numbers that explains what he was thinking. This must exist for my hypothesized explanation to make sense.

thaumasiotes 10y ago
> I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance. It's worse than that; he mentions the identity function only to make a gross error about it. The identity function on (a, a) is (a, a), not a.
- coinomega 10y ago
  I don't think you need to be so unforgiving? If you want extra precision, a -> f(a, a) is Id. Knowing that helped me understand one property of the chart, never said that was the most stunning of properties, and the best articulated one :-)
  - thaumasiotes 10y ago
    > If you want extra precision, a -> f(a, a) is Id. What does this mean?
    - coinomega 10y ago
      The function which to any integer a associates f(a, a) with f defined as in the article is the identity function on the natural integer set.

bnegreve 10y ago

> In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧? '∧' usually denotes the logical AND operator, which does not operate on integer values, (i.e. writing 22 ∧ 78 = 6 is weird). So it's not a bad idea to give this function a different name. He could have made that explicit though.

deleted 10y ago
[deleted]