#include <stdio.h>
#include <stdlib.h>
unsigned long long rpow(int n, int p) {
return p ? p==1 ? n : n * rpow(n,p-1) : 1;
}
int main(int argc, char **argv) {
if(argv[1])
if(argv[2]) {
int n = atoi(argv[1]);
int p = atoi(argv[2]);
printf("%llu\n",rpow(n,p));
}
return 0;
}O(log n) time.
int main() {
main();
}pow algorithm.
pow function, you have to load or generate the table. Never did I say that you would do this more than once or every time you call pow. The point is, the work you do in loading or generating the table will not be paid off by a single call to pow, you will have to an equivalent amount of work in pow calls as you did in loading the table for the amortization argument to work at all.#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
uint64_t rpow_aux(uint64_t, uint64_t, uint64_t) __attribute__ ((const, always_inline, flatten));
uint64_t rpow(uint64_t, uint64_t) __attribute__ ((const, always_inline, flatten));
uint64_t rpow_aux(uint64_t n, uint64_t p, uint64_t a)
{ return p == 0 ? a : rpow_aux(n, p - 1, a * n); }
uint64_t rpow(uint64_t n, uint64_t p)
{ return p < 1 ? 1 : rpow_aux(n, p, 1); }
int main(void)
{ printf("%" PRIu64 "\n", rpow(2, 63));
return 0; }loeb = fix (fmap . flip id =<<)
fibs = loeb (map const [0, 1] ++ map (uncurry (flip (.)) . ((take 2 .) . genericDrop *** genericIndex [\[a, b] -> b * (2 * a + b), sum . map(^2)]) . (\(q, r) -> (q + r - 1, r)) . flip divMod 2)[2..])