Comment by krackers
18 hours ago
>instead of costs scaling with the size/precision of the number
But isn't the assumption that arithmetic is "atomic" standard in TCS? Costs do scale with the bit length, presumably they aren't assuming that addition is "constant time" with respect to # of bits (which would defeat the whole point of the exercise).
Maybe I'm missing something, but none of the things mentioned in that blogpost seem particularly "surprising" to me, most of it focuses on the fact that computational models used in TCS don't align with the real-world model of computers, but that seems like something you learn in day 1 of algorithm analysis? If you want something closer to real-world you'd use word ram model.
The model I like is assuming the numbers you manipulate in O(1) time are bounded by some polynomial in the size of the input. Or, O(log n) bits. This seems reasonable, as just addressing a size n input uses addresses of O(log n) bits.
One can do some interesting things in this model, such as the van Emde Boas data structure for O(log log n) integer set queries, and tricks where O(log n) size subproblems are converted to lookup tables.
That's passable model assumption if your algorithm didn't create intermediate numbers/strings of arbitrarily growing length. Otherwise the thing that you're considering a constant is not actually bounded.
Whether it's an oversight in just this work, or TCS more broadly, I do not know. But it's a fundamental point nonetheless.