when i use pow(x,y) in C, is such a thing calculated in constant or linear runtime?
Name:
Anonymous2012-08-25 0:42
Such a thing is implementation dependent.
It wouldn't surprise me if most compilers took advantage of y being a constant, if y is in an integer you could do it recursively in logarithmic time (if you allow the result to be slightly altered, floating point math is rarely associative).
Name:
Anonymous2012-08-25 2:37
pow(x, y) is a function call (or a macro but usually not), so anything can happen. If you want to know exactly what's going on, get a debugger.
Name:
Anonymous2012-08-25 3:07
Never use pow unless the exponent isn't constant and you need full IEEE 754 precision. Most implementations are really slow.
x^y can be implemented in hardware giving a constant time result (with an enormous constant). I doubt it's done that way though since it's so bad in area requirements and much simpler to do using a digit recurrence algorithm in microcode (slightly larger upper bound constant)
technically, if x and y have a limited range of values, like 0, 1, 2, ... 2^64, for example, then the performance of pow(x, y) can always be bounded by a constant, assuming that pow(x, y) terminates for each x and y.
Name:
Anonymous2012-08-25 22:12
>>1-12 `
>2012
>not just looking up pre-computed values in a hash table
ISHYGDDT