You are not logged in. Please login at www.codechef.com to post your questions!

×

Built-in Power Function Complexity

 0 Hi! Could anyone please tell me what is the complexity of built-in pow(a,b) function in header file? Is it naive O(n) or O(log(n))? Thanks. asked 29 Dec '14, 22:56 3●1●1●4 accept rate: 0%

 0 Hello Sidharthanegi Complexity of inbuilt pow function. for c or c++ O(log(N)) but as we know c++ does not support any inbuilt datatype which can handle such large values even 2^100 .. It is usually avoided for large values . for python O(log(N)) even there are other option available in that language . answered 29 Dec '14, 23:02 1★mhungry 62●2 accept rate: 18% @mhungry Thank You! That was helpful. (30 Dec '14, 13:37) In python u can use function with mod tooo...such a great feature pow(a,b,mod) . (10 Feb, 00:39)
 2 @sidharthanegi : i just want to share something useful related to your question. if a and b are very large numbers the overflow might occur. In that case u can use Logarithmic Exponentiation which whose complexity is O(logn). Below is the link for a problem in spoj where the exponent is a very large number .. in that case you must use Logarithmic Exponentiation method to get the desired result and get accepted. Also see the explaination by wikipedia below answered 12 Jan '15, 02:16 906●5●12 accept rate: 0%
 0 I exactly didn't get the intention behind your doubt I once had it though :P). But the main point is, complexity is what we call the estimation of the growth of the function with respect to the given input variable n. pow function always take same number of inputs, thus, constant input size, so there's no point thinking about its complexity. But if we think in terms of bits, i.e. how every operation in measure of bits is happening internally, how the processor is computing it, then it depends on your underlying architecture(specifically processor). For a x86 processor, it is constant because it is calculated this manner: //Assembly language code 2^(y*log2(x))  Instructions FLY2X and F2XM1 are used for this computation, for this see here. Because I have been working on assembly language and hardware side last weeks, I believe in this: For other functions of the math library and even this, they are implemented in microcodes inside microprocessors. A C compiler will generate codes that will call these assembly instructions. Nowadays, these instructions are sometimes quite inaccurate and are therefore rarely used anymore. Most other processors do not have instructions for sine and cosine because calculating them in software gives more flexibility, and may even be faster. Many implementations may be provided by the library we are using, no one software algorithm is efficient, this depends on our input size and the computations required. So, the first job of the library is to look which implementation of the given and required function will be appropriate. Read more here, awesome answers.. :) answered 29 Dec '14, 23:18 3★damn_me 2.6k●2●13●36 accept rate: 24% @damn_me What I meant by O(n) was infact O(b), the second argument of pow() funtion. My bad, I didn't express myself clearly. Thanks though! (30 Dec '14, 13:40)
 toggle preview community wiki:
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×944

question asked: 29 Dec '14, 22:56

question was seen: 17,636 times

last updated: 10 Feb, 00:39