left-to-right-binary-exponentiation.c

#include <stdio.h>
#include <stdint.h> // uint64_t
#include <stdlib.h> // realloc
#include <stdbool.h> // bool

// How to use:
// ./left2right_pow <num> <power>

typedef struct { bool* array; size_t size; } boolarray;

boolarray getbase2rep (uint64_t ninput)
{
    bool* result = NULL;
    size_t i = 0, size = (ninput == 0) ? 0 : 1;

    for (bool* tmp = NULL; ninput != 0; (ninput /= 2) ? ++size, ++i
             : false /* Don't increment size & i when test about to fail. */) {
        tmp = realloc (result, sizeof (bool) * size);
        if (!tmp) {
            perror ("realloc error");
            return (boolarray){ result, size - 1 };
        }
        result = tmp;
        result[i] = ninput % 2 == 0 ? false : true;
    }
    return (boolarray){ result, size };
}

uint64_t left2right_powers (uint64_t ninput, uint64_t power)
{
    boolarray bpower = getbase2rep (power);
    uint64_t pow = ninput;

    if (!(&bpower)->array)
        return 0;

    for (int i = (&bpower)->size - 2; i >= 0; --i)
        pow *= (&bpower)->array[i] == 0 ? pow : pow * ninput;

    return pow;
}

int main (int argc, char* argv[])
{
    uint64_t ninput, npower, ans;

    ninput = strtol (argv[1], NULL, 10);
    npower = strtol (argv[2], NULL, 10);

    ans = left2right_powers (ninput, npower);
    printf ("%lu\n", ans);

    return 0;
}