Hacker News Reader

Comment by lokedhs | Hacker News Reader

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?

View on HN

> 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.

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.

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)

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.

> 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.

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 :-)

> If you want extra precision, a -> f(a, a) is Id.

What does this mean?

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.

Granted. g(a) = f(a,a) is indeed the identity function for all f such that f(a,a) = a. That seems pretty pointless as an observation. We have f, so we're observing that some other, unrelated function is the identity function?

Assuming you actually care about the answer, this just help me drew the exploratory graph, and this property was useful to fill in cells for which operands were equal. Finding obvious properties is a great way to learn a pattern without even computing things. Unlike what you may think, I had no idea what I was about to find - I had never seen this chart drawn before, and so this post is structured around how I thought about the exploration, not around how it may be presented to an audience who already knows way more than I do on bitwise operations. Sounds fair?

Sure it's fair. Bitwise operations produce pretty strange numeric results, so no, I wouldn't think you'd expect much going in. But I don't see where the identity function comes into it at all. It looks like the term "the identity function" stuck in your mind, and you reached for it when you found something subjectively similar. But shared semantic space isn't a good reason to say that a function which isn't the identity function, is. Your middle point is the observation "f(a,a) = a", which is perfectly valid, but is not the same finding as the finding you report. Using pretty-simple terms to state something true is generally preferable to using even simpler terms to state something false.

It is fair enough, that you find the law f(a,a) = a useful. Just don't call it the identity function when it is not.

The law x AND 1 = x is called the identity law.

The law x AND x = x is called the idempotence law.

Nothing to do with the identity function.

A counterexample is 0 & -1 == 0.

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.

> 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

2: https://en.wikipedia.org/wiki/P-adic_number

I'm not quite sure they have enough paper for numbers with infinite boolean expansions.

The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?

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

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?

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

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

Reply on news.ycombinator.com