Question

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

Answer 1

#include <stdio.h>

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++) {
        printf("pow(%d, %d) = %ld\n", 2, i, power(2, i));
    }
}


        
/*
run:

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

 

70+ SQL courses for beginners and professionals