C++ calculate the power of a number without using pow or loop

Question

I am a beginner C++ user and have been given a task to code a function that calculates the power of a number but we are not allowed to use the pow function or a loop.

The user of the function has to input the base and exponent in the command window.

What is a good place to start?

something that needs a loop but you are not allowed to use a loop should ring a bell called: recursion — 463035818_is_not_an_ai, Nov 14 '19 at 16:27
And in the real world, you learn how to convert ill-advised recursion back to loops. The two are mathematically related, but reality has a strong preference. — MSalters, Nov 14 '19 at 16:59

score 10 · Accepted Answer · answered Nov 14 '19 at 16:31

10

pow(x, y) can be written as exp(y * log(x)). As far as I can tell that satisfies the question constraints.

With real x and y, any alternative to that is difficult. Sure, there are silly alternatives using recursion for integral y but using recursion for linear problems is never a particularly good approach.

answered Nov 14 '19 at 16:31

Bathsheba

231,907
34
361
483

5

i like this spirit. Teachers asking silly questions should be ready to accept clever answers ;) – 463035818_is_not_an_ai Nov 14 '19 at 16:37
1

@Shawn not really although clearly it’s related otherwise this answer would not be possible. From a mathematical standpoint exp(x) can be defined as a function whose value equals its gradient. – Bathsheba Nov 14 '19 at 18:49
2

...with a condition `exp(0)=1`. – Evg Nov 14 '19 at 18:56

Evg · Answer 2 · 2019-11-14T17:37:02.140

void start_here(unsigned int n) {
    if (n > 0)
        start_here(n - 1);
}

start_here(2019);

Then you write:

double pow(double x, unsigned int exp) {
    if (exp > 0)
        return x * pow(x, exp - 1);
    else
        return 1;
}

Then you improve:

double pow(double x, unsigned int exp) {
    if (exp > 0) {
        const auto p2 = pow(x, exp / 2);        
        return p2 * p2 * ((exp & 1) ? x : 1);
    }
    else
        return 1;
}

The last algorithm is known as binary exponentiation.

And finally you learn templates:

template<unsigned int exp>
constexpr double pow(double x) {
    if constexpr (exp > 0) {
        const auto p2 = pow<exp / 2>(x);        
        return p2 * p2 * ((exp & 1) ? x : 1);
    }
    else
        return 1;
}

Edit. Tail recursion optimization. Let's take a look at the assembly code generated for the first version of pow() without optimizations (-O0):

pow(double, unsigned int):
        push    rbp
        mov     rbp, rsp
        sub     rsp, 16
        movsd   QWORD PTR [rbp-8], xmm0
        mov     DWORD PTR [rbp-12], edi
        cmp     DWORD PTR [rbp-12], 0
        je      .L2
        mov     eax, DWORD PTR [rbp-12]
        lea     edx, [rax-1]
        mov     rax, QWORD PTR [rbp-8]
        mov     edi, edx
        movq    xmm0, rax
        call    pow(double, unsigned int)
        mulsd   xmm0, QWORD PTR [rbp-8]
        jmp     .L3
.L2:
        movsd   xmm0, QWORD PTR .LC0[rip]
.L3:
        leave
        ret
.LC0:
        .long   0
        .long   1072693248

We see a recursive call pow(double, unsigned int).

Now let's add some optimizations (-O2 -ffast-math):

pow(double, unsigned int):
        movapd  xmm1, xmm0
        movsd   xmm0, QWORD PTR .LC0[rip]
        test    edi, edi
        je      .L4
.L3:
        mulsd   xmm0, xmm1
        sub     edi, 1
        jne     .L3
        ret
.L4:
        ret
.LC0:
        .long   0
        .long   1072693248

Where is the recursive call? It's gone! The compiler employs the tail call optimization and transforms a recursive call into a simple loop. This assembly code is equivalent to this C++ one:

double pow(double x, unsigned int exp) {
    double p = 1;
    if (exp == 0)
        return p;
  loop:
    p *= x;
    if (--exp > 0)
       goto loop;
    return p;     
}

This optimization is not possible without -ffast-math option due to non-associativity of floating point multiplication.

And finally, 1.d's is represented in memory by 8 bytes:

3F F0 00 00 | 00 00 00 00  (base 16)

After conversion into two long numbers, they become:

1072693248  | 0            (base 10)

These are two magic numbers that can be spotted in the assembly code.

Yup, upvote for exponentation by squaring. Bonus point if you mention the possibility of tail recursion optimisation. — Bathsheba, Nov 14 '19 at 16:43

score 0 · Answer 3 · answered Nov 14 '19 at 16:32

0

Here is how you will do it.

int exponent(int , int );

int main()
{
    cout<<exponent(3,8);
    return 0;
}
int exponent(int x , int y )
{
    if(y==0)
        return 1;
    return (x*exponent(x,y-1));
}

Let me know if you found it hard to digest.

answered Nov 14 '19 at 16:32

Nikhil Badyal

1,589
1
9
20

hm I dont think this is what OP will **do**. I rather think it is too tempting to simply copy your code. Please at least explain what the code does – 463035818_is_not_an_ai Nov 14 '19 at 16:33
Using` int` means your function is vulnerable to overflow. – Bathsheba Nov 14 '19 at 16:34
It is not only integers that can be raised to a power, and nor are powers required to be integers. – underscore_d Nov 14 '19 at 16:36
@Bathsheba why it's an overflow. i haven't stored exponent anywhere? I'm just returning it. – Nikhil Badyal Nov 14 '19 at 16:36
The largest `int` can be as small as 32767. Surprisingly small `x` and `y` will cause that. At the very least use an `unsigned` type. – Bathsheba Nov 14 '19 at 16:37
So what's the deal ? No one is going to compute 32767 ^ 32767 using recursion. – Nikhil Badyal Nov 14 '19 at 16:38
I can't write unsigned power can be negative. Writing unigned will make overflow. – Nikhil Badyal Nov 14 '19 at 16:38
why not? No such constraints are mentioned in the question, but yet you suggest to use recursion ;) – 463035818_is_not_an_ai Nov 14 '19 at 16:38
Note : you might want to compute `exponent(x,y / 2)` and save a lot of computation. Also, using `long` as a return value is safer. – Arnaud Denoyelle Nov 14 '19 at 16:39
But there exist efficiency and common sense. That's why i thought no one goona final 32767^32767 with recursion. – Nikhil Badyal Nov 14 '19 at 16:40
@Problematic: Please. What do you think 256 * 128 is? I don't see those as particularly large numbers. Use an unsigned long long, pretty please with sugar on top. And who said a linear recursion was the best idea? There are other ways than a simple linear recursion to solve this, e.g. exponentation by squaring. – Bathsheba Nov 14 '19 at 16:41
@Bathsheba It's 37488. But thing is I'm just returning the return it's tail recursion so no need to worry if it's in range of int. – Nikhil Badyal Nov 14 '19 at 16:42
You are aware that the behaviour of signed integral type overflow is undefined? – Bathsheba Nov 14 '19 at 16:43
But as you said to use unsigned it's even more disastrous. – Nikhil Badyal Nov 14 '19 at 16:44
What makes you say that? At least the wraparound behaviour is defined. – Bathsheba Nov 14 '19 at 16:45
What if someone provide (-2,2) as input and i define variable as unsgined. Can you predict ? – Nikhil Badyal Nov 14 '19 at 16:45
Or (2, -2) then the fun really does begin... For your case you can always put the sign back in but I'm clutching at straws here. – Bathsheba Nov 14 '19 at 16:46
That's why I didn't use unsigned but you asked me to use unsgined type. – Nikhil Badyal Nov 14 '19 at 16:48

ark1974 · Answer 4 · 2019-11-14T16:38:55.730

0

Solution using recursion:

double power(double x, double n, double product = 1) {
    if (n <= 0) return product;
    product *= x;
    return power(x, n - 1, product);
}

int main()
{
    cout << power(10, 2);
}

edited Nov 14 '19 at 16:38

answered Nov 14 '19 at 16:33

ark1974

615
5
16

score 0 · Answer 5 · answered Nov 14 '19 at 17:53

Assuming integral base and exponent, why not just do loop unrolling then. Assuming sizeof(int) = 4 bytes = 32 bits.

long long power (int base, int exponent)
 {
  long long result = 1;
  long long powOf2 = base;

  if (exponent%2)
    result *= powOf2;
  exponent >>= 1;
  powOf2 *= powOf2;

  if (exponent%2)
    result *= powOf2;
  exponent >>= 1;
  powOf2 *= powOf2;

  (copy paste 30 more times)

  return result;
 }

If sizeof(int) = 8, copy paste 62 more times instead of 30.

C++ calculate the power of a number without using pow or loop

5 Answers5