From 7d55d5b018a5205268549c87a5eb7d545d300add Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Mon, 5 Aug 2013 21:16:53 +0100 Subject: [PATCH] utils/naf.c: Non-adjacent form calculator, from math/mpreduce.c. Rescue the plain old state machine, in case it's interesting later. --- utils/naf.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) create mode 100644 utils/naf.c diff --git a/utils/naf.c b/utils/naf.c new file mode 100644 index 0000000..550a271 --- /dev/null +++ b/utils/naf.c @@ -0,0 +1,30 @@ +#include +#include + +#include "mp.h" +#include "mptext.h" + + +int main(int argc, char *argv[]) +{ + mp *x; + mpscan sc; + unsigned long d, i; + enum { Z = 0, Z1 = 2, X = 4, X0 = 6 }; + unsigned st = Z; + + x = mp_readstring(MP_NEW, argv[1], 0, 0); + d = mp_bits(x); + + for (i = 0, mp_scan(&sc, x); mp_step(&sc); i++) { + switch (st | mp_bit(&sc)) { + case Z | 1: st = Z1; break; + case Z1 | 0: st = Z; printf("+ %lu\n", i - 1); break; + case Z1 | 1: st = X; printf("- %lu\n", i - 1); break; + case X | 0: st = X0; break; + case X0 | 1: st = X; printf("- %lu\n", i - 1); break; + case X0 | 0: st = Z; printf("+ %lu\n", i - 1); break; + } + } + if (st >= X) printf("+ %lu\n", i - 1); +} -- 2.11.0