4 ms·
log_32(2^48) is <= 10. Your computer cannot access anywhere close to 2^48 items. I appreciate a little pedantry as much as the next guy, but if you can come up
by lomnakkus 12y ago
log_32(2^48) is <= 10. Your computer cannot access anywhere close to 2^48 items.
I appreciate a little pedantry as much as the next guy, but if you can come up with an equally concise way of saying it than "effectively constant" then please do so.
- rawnlq 12y agoHere you go: Õ (read soft-O) See: http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_the_Bachmann.E2.80.93Landau_notations http://en.wikipedia.org/wiki/Big_O_notation#Extensions_to_th... (basically means ignore multiplicative log factors) Also, to play devil's advocate, why not say all log factors are effectively constant? Note that 5 * log_32(x) = log_2(x) or to use your example, log_2(2^48) <= 50.
- lomnakkus 12y agoInteresting. I was not aware of that notation, thank you. Re: "all log factors": Agreed, as long as the base of the logarithm is high enough, obviously :). I'm well aware that the base doesn't matter mathematically, but in practice it actually does. Especially since 32 is the number of bits in a CPU word, and thus neatly fits into cache lines, is easily manipulable by CPU instructions, etc. etc. (See Bagwell's papers for details.)