Challenge: you can code, but can you can efficiently ?

Question

Using only basic operations (+ - * /) code a fastexp function returning x^p using the smallest possible number of basic operations for any p<1000.

Answer 1

Yosh!

https://code.sololearn.com/W7obo9sGvQgr/?ref=app

Answer 2

Here's my Python solution:
https://code.sololearn.com/cK6O4WWD5VNb

Answer 3

My previous solution, while better than others, was still not optimal, and had O(p) complexity in average case.
I found a better solution which really gives O(log(p)).
The following code includes the original solution plus the more efficient code. It also measures and prints the efficiency of the two. In SoloLearn env the time calculations don't work, but it still counts the number of operations. In regular OS it also shows the actual time it took.

https://code.sololearn.com/c72gCKYe1M3l

Answer 4

In C++ :
x is a decimal number positive or negative,
p is an integer positive or negative.

https://code.sololearn.com/cmBJl9657C5x/?ref=app

Answer 5

Sivan's solution is the best so far, but you can do a little bit better ! Maz and Jojo : if p=999 you do 999 multiplications...

Answer 6

This is a good example of how a good algorithm even with a slow language (Python) can be faster than an average algorithm with a fast language (C++ or any compiled language or even assembler).

Nb: >> and & are usually faster than *

https://code.sololearn.com/cWqyF1QagEm1/?ref=app

Answer 7

The recursion might look elegant but it runs VERY slowly... Just run the following code to see how much. Also this code proposes a faster version relying on binary operations (<< &) which are usually much faster
https://code.sololearn.com/cn4f5No80UvM/?ref=app

Answer 8

What is funny too is that logarithmic algorithms can lose against naive ones depending on how they are implemented....

Answer 9

Also with p=1000 a logp algo with a big constant ( is C.logP) can be slower than a very 'dry' P