3 ms·

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
      - thedufer 10y ago
        Excellent. I'm glad we agree. You'll notice that the stated identity f(x,x) = x fails to hold over x < 0. I hope this is sufficient to make it clear that the equation does not consider the negatives?
        Strilanc 10y ago
        Seems to work fine for -1: f(-1, -1) = sum_{n=0}^b 2^n (floor(-1/2^n) mod 2) (floor(-1/2^n) mod 2) = sum_{n=0}^b 2^n * 1 * 1 = 1 + 10 + 100 + 1000 + ... [in binary] = ...11111 [in the 2-adics] = -1

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
    - thedufer 10y ago
      Excellent. I'm glad we agree. You'll notice that the stated identity f(x,x) = x fails to hold over x < 0. I hope this is sufficient to make it clear that the equation does not consider the negatives?
      - Strilanc 10y ago
        Seems to work fine for -1: f(-1, -1) = sum_{n=0}^b 2^n (floor(-1/2^n) mod 2) (floor(-1/2^n) mod 2) = sum_{n=0}^b 2^n * 1 * 1 = 1 + 10 + 100 + 1000 + ... [in binary] = ...11111 [in the 2-adics] = -1