Question

How to write a function that calculates power in O(log(n)) time with C++

Answer 1

#include <iostream>

long power(long num, long n) {
 	if (n == 0) {
 	    return 1;
 	}
  	
  	long tmp = power(num, n / 2);
  	tmp = tmp * tmp;
  	if (n % 2 == 0) {
  	    return tmp;
  	}
  	
  	return tmp * num;
}

int main() {
    for (int i = 0; i < 15; i++) {
        std::cout << "i = " << i << " power = " << power(2, i) << "\n";
    }
}


        
/*
run:
        
i = 0 power = 1
i = 1 power = 2
i = 2 power = 4
i = 3 power = 8
i = 4 power = 16
i = 5 power = 32
i = 6 power = 64
i = 7 power = 128
i = 8 power = 256
i = 9 power = 512
i = 10 power = 1024
i = 11 power = 2048
i = 12 power = 4096
i = 13 power = 8192
i = 14 power = 16384
     
*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
 
long power(long num, long n) {
    if (n == 0) {
        return 1;
    }
 
    if (n == 1) {
        return num;
    }
     
    if (n % 2 == 0) {
        return power(num * num, n / 2);
    } else {
        return num * power(num, n - 1);
    } 
}
 
int main() {
    for (int i = 0; i < 15; i++) {
        std::cout << "i = " << i << " power = " << power(2, i) << "\n";
    }
}
 
 
         
/*
run:
         
i = 0 power = 1
i = 1 power = 2
i = 2 power = 4
i = 3 power = 8
i = 4 power = 16
i = 5 power = 32
i = 6 power = 64
i = 7 power = 128
i = 8 power = 256
i = 9 power = 512
i = 10 power = 1024
i = 11 power = 2048
i = 12 power = 4096
i = 13 power = 8192
i = 14 power = 16384
      
*/

 

 

70+ SQL courses for beginners and professionals

Answer 3

#include <iostream>

long power(long num, long n) {
    if (n == 0) {
        return 1;
    }

    if (n % 2 == 0) {
        return power(num * num, n / 2);
    } else {
        return num * power(num * num, n / 2);
    }
}

int main() {
    for (int i = 0; i < 15; i++) {
        std::cout << "i = " << i << " power = " << power(2, i) << "\n";
    }
}


        
/*
run:

i = 0 power = 1
i = 1 power = 2
i = 2 power = 4
i = 3 power = 8
i = 4 power = 16
i = 5 power = 32
i = 6 power = 64
i = 7 power = 128
i = 8 power = 256
i = 9 power = 512
i = 10 power = 1024
i = 11 power = 2048
i = 12 power = 4096
i = 13 power = 8192
i = 14 power = 16384
     
*/

 

70+ SQL courses for beginners and professionals