Hacker News new | ask | show | jobs
by crimsonpowder 1046 days ago
Probably because add, sub, and mul are int -> int and div is int -> real. The fundamental operation maps from ℵ0 to ℵ1, which the other operations don't do. Intuitively, the complexity comes from this fact.
1 comments

1. We're discusing here floored integer division, which outputs an integer, not something more general like a real.

2. Even if we were discussing exact division, the ratio of two integers is a rational. The rationals are countable. More generally, any image of a countable set is countable, and the cartesian product of two countable sets is countable; there is no way you could get something uncountable from something like this.

3. Aleph_1 is not (necessarily) the same thing as the cardinality of the reals, which is 2^(aleph_0). The statement that these are the same is known as the continuum hypothesis and is undecideable in standard mathematics.

...and, also, none of this really relates to the complexity of performing integer division, even ignoring the fact that these statements are false.