4 ms·
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,
by patrickthebold 7y ago
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.
- baddox 7y agoThere'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. :)
- ouid 7y agoit's a little more complicated than that.
- patrickthebold 7y agohow so?
- ouid 7y agowell I can hold somewhat arbitrarily large integers in memory with the ackermann function, for instance.