commit c4dd1ad7ffc32e2b2f3a5e7bd45161e133de30ae
parent eeac6f3367a26a7905ecd06132ad4bbf7bf8d82e
Author: olikru <olikru@tkruger.se>
Date: Tue, 16 Apr 2024 18:24:58 +0200
product tree stuffs
Diffstat:
5 files changed, 125 insertions(+), 3 deletions(-)
diff --git a/Makefile b/Makefile
@@ -24,7 +24,8 @@ hnp.o\
cyclefind.o\
pierre.o\
fmpzio.o\
-wiener.o
+wiener.o\
+prodtree.o
TOOLS=\
hnpsolve\
lcgfloyd\
diff --git a/fmpzio.h b/fmpzio.h
@@ -19,6 +19,16 @@ int read_next_fmpz(fmpz_t res);
*/
int read_next_hex_fmpz(fmpz_t res);
+/**
+ * Read a fmpz vector from stdin.
+ *
+ * The numbers are read from stdin, separated by whitespaces (spaces,
+ * tabs and newlines). Returns the size of the resulting vector.
+ * Allocates a new vector which needs to be cleared.
+ *
+ * @param v pointer to vector to initialize
+ * @returns the length of the new vector
+ */
slong read_hex_lines(fmpz** v);
#endif
diff --git a/prodtree.c b/prodtree.c
@@ -0,0 +1,69 @@
+#include <stdlib.h>
+#include <err.h>
+#include <fmpz.h>
+#include <fmpz_vec.h>
+#include <stdio.h>
+
+#include "prodtree.h"
+
+static inline slong
+upper_bound_2pow(const slong x)
+{
+ slong r = 1;
+
+ while (r < x) {
+ r <<= 1;
+
+ if (r == 0) {
+ err(EXIT_FAILURE, "upper bound 2pow failure");
+ }
+ }
+
+ return r;
+}
+
+slong
+prodtree_compute(fmpz **res, const fmpz *v, slong nv)
+{
+ slong ubound = upper_bound_2pow(nv);
+ slong tree_size = 2 * ubound - 1;
+ slong i, j;
+
+ *res = _fmpz_vec_init(tree_size);
+
+ // row 0, v and padded with ones
+ for (i = 0; i < nv; i++) {
+ fmpz_set(&(*res)[i], &v[i]);
+ }
+ for (i = nv; i < ubound; i++) {
+ fmpz_set_ui(&(*res)[i], 1);
+ }
+
+ // rest
+ j = 0;
+ for (i = ubound; i < tree_size; i++) {
+ fmpz_mul(&(*res)[i], &(*res)[j], &(*res)[j + 1]);
+ j += 2;
+ }
+
+ return tree_size;
+}
+
+void
+prodtree_pprint(const fmpz* v, const slong nv)
+{
+ slong i, j = 0, row_len = (nv + 1) >> 1;
+
+ for (i = 0; i < nv; i++) {
+ fmpz_print(&v[i]);
+ printf(" ");
+
+ j++;
+
+ if (j == row_len) {
+ printf("\n");
+ row_len >>= 1;
+ j = 0;
+ }
+ }
+}
diff --git a/prodtree.h b/prodtree.h
@@ -0,0 +1,31 @@
+#ifndef _PRODTREE_H_
+#define _PRODTREE_H_
+
+/**
+ * Compute a prodtree from a vector.
+ *
+ * Given a vector v of length bv we first pad a product tree is
+ * constructed by first padding the vector with ones to make it a vector
+ * of length a power of 2. This vector forms the leaves of the product
+ * tree, and the remaining (complete binary) tree is formed by takning
+ * the pairwise product of the children of a node.
+ *
+ * This function allocates a new vector for the tree, the function
+ * calling this has to free the tree.
+ *
+ * @param res pointer to the vector to initialize
+ * @param v vector to compute the product tree from
+ * @param nv size of the vector n
+ * @returns size of the product tree
+ */
+slong prodtree_compute(fmpz** res, const fmpz* v, slong nv);
+
+/**
+ * Pretty print a product tree.
+ *
+ * @param v the product tree to print (as a vector)
+ * @param nv the size (number of nodes) of the prouct tree
+ */
+void prodtree_pprint(const fmpz* v, const slong nv);
+
+#endif
diff --git a/tools/dbtool.c b/tools/dbtool.c
@@ -4,6 +4,7 @@
#include <err.h>
#include <fmpz.h>
+#include <fmpz_vec.h>
#include <sqlite3.h>
#include <stdio.h>
#include <stdlib.h>
@@ -11,6 +12,7 @@
#include <unistd.h>
#include "fmpzio.h"
+#include "prodtree.h"
enum command { INSERT, CREATE, NONE };
@@ -95,7 +97,15 @@ static void
insert(sqlite3 *db)
{
fmpz *v;
- read_hex_lines(&v);
+ slong nv = read_hex_lines(&v);
+
+ fmpz *tree;
+ slong ntree = prodtree_compute(&tree, v, nv);
+
+ prodtree_pprint(tree, ntree);
+
+ _fmpz_vec_clear(v, nv);
+ _fmpz_vec_clear(tree, ntree);
}
static enum command
@@ -115,12 +125,13 @@ main(int argc, char *argv[])
{
sqlite3 *db;
int rc;
+ enum command com;
if (argc < 3) {
usage(argv[0]);
}
- enum command com = get_command(argv[2]);
+ com = get_command(argv[2]);
if (com == NONE) {
fprintf(stderr, "Unknown command: %s\n\n", argv[2]);
usage(argv[0]);
