Re:When your data doesn’t fit in memory: the basic techniques
by patrickthebold on Monday November 11, 2019 @08:12PM
(#21510601)
The amount of memory needed to hold an integer is log(N). That's just because the log is about how many digits it has. That fact doesn't depend on the hardware, it's just a math fact.
[ Parent
| on HN ]
Re:When your data doesn’t fit in memory: the basic techniques
by baddox on Monday November 11, 2019 @08:58PM
(#21510852)
There's generally an assumption that the elementary values we're using fit into native hardware values, and that some elementary operations on those values can be done in constant time (e.g. a CPU instruction).
If you want to talk about something like supporting arbitrarily large integers or defining the memory of the physical computer we're using, we need to be explicit about that, because it changes a lot of things. After all, a finite-memory computer is not Turing complete, and everything it can compute can be computed in constant time. :)
Re:When your data doesn’t fit in memory: the basic techniques
by ouid on Monday November 11, 2019 @09:17PM
(#21510939)
it's a little more complicated than that.
Re:When your data doesn’t fit in memory: the basic techniques
by patrickthebold on Monday November 11, 2019 @09:26PM
(#21510984)
how so?
Re:When your data doesn’t fit in memory: the basic techniques
by ouid on Tuesday November 12, 2019 @12:38AM
(#21511790)
well I can hold somewhat arbitrarily large integers in memory with the ackermann function, for instance.