Hacker News Reader

Hacker News

Comment by goldenkey | Hacker News Reader

Full thread

goldenkey

A similar question, which is more apt for worthy discussion would be, is bool casting O(1), that is, constant time ?

And that might differ between JITs and compiled languages and different numerical types.

For any machine precision numerical types, if the code is compiled, it'll just become

TEST EAX, EAX ...set eax to 0 or 1 based on jmp...

So in most compiled languages, a bool cast on machine precision numerics, will be constant time.

View on HN

You are very close to making the same mistake as the interviewer did. The compiled program will not have any tests or casts or anything like that, because the condition is known at compile-time and the compiler just compiles it down to an unconditional jump.

I'm not making any mistakes. It wouldn't even be a jump at all, just static code if the statement was compile time optimized. I failed to mention it because it's trivial enough without the extra fluff of compile time magic

In some contexts, it is important to make a distinction between O(1) and constant-time. O(1) means you've got an constant upper bound for how long the operation could take, but constant time implies that the operation always takes the same amount of time.

Consider the case of converting an integer value to floating point. In order to normalize the floating point value, you'll have to do something equivalent to counting the number of leading zeros on the int, and many machines don't have an instruction for that, so you have to do a loop. Data-dependent timing like that needs to be studiously avoided in crypto code in order to prevent timing attacks. (Of course, crypto rarely uses floating point, but it's still a great example of how an O(1) operation can have variable execution time depending on the input.)

Time complexity is essentially the expression for computation time as a function of input size. Before you can discuss it you have to decide how you measure the size of the input. What you pick as the size of the input may vary from problem to problem and may be the list size, string length, number of penguins etc.

I wonder, how do you propose to measure the "size" of your input to bool cast?

That's why I mentioned machine precision. Bignums are going to be different and most languages don't handle big nuns or casts on them implicitly, it's mostly lib based

Technically any sort of type casting would end up being O(1), wouldn't it?

What about something like casting a bignum to float? It's easy to imagine a simple implementation optimization where any number smaller than the machine's maximum integer size is stored as a native value, so e.g. float(100) would be constant time but float(2^64 + 1) might not.

What's it mean to cast in non-constant time? Instead of O(1) performance, it's O(N). But in that case, performance is linear with respect to what? With respect to how big of a number is being casted?

I think that might be possible in dynamic languages like Lisp that can compile to assembly. Maybe Franz or Allegro Lisp compilers do something like that. For the JVM or .NET, I'm not sure that can happen. For C or C++, every typecast is constant time.

A conversion from string to int is O(n) in the length of the string (O(lg n) in the "size" of the number). Such a "cast" would be syntactically indistinguishable from builtin casts eg. in C++ which allows user-defined conversions.

I can see non-constant conversion times, especially with floats. Floats have lots of weird edge cases involved in them, especially when you get to the very big and the very small scales. If your number's too big, you have to see if you need to just throw back infinity and/or negative infinity. If your number's too small, positive and negative zero. Finally, if you're hanging out with tiny numbers near zero, a good floating point library will start to have to worry about denormal numbers, where you will start padding with zeroes, sacrificing precision to denote that the number isn't quite zero. So yeah, it would be N in respect to the size.

In Python you can: https://docs.python.org/2/library/stdtypes.html#truth-value-... https://docs.python.org/2/library/functions.html#bool

Reply on news.ycombinator.com