cangrepp

commit 6cba5c0e44be17c653cb2c41d847e18695f34dad
parent b12541b4b2578b2f0871c96b7ec4011fba252ba4
Author: olikru <olikru@tkruger.se>
Date:   Tue, 16 Jan 2024 11:07:57 +0100

added brents cycle finder

Diffstat:
M
Makefile
 | 
5
+++--
M
cyclefind.c
 | 
36
++++++++++++++++++++++++++++++++++++
M
cyclefind.h
 | 
19
+++++++++++++++++++
M
test_angrepp.c
 | 
10
++++++++++

4 files changed, 68 insertions(+), 2 deletions(-)
diff --git a/Makefile b/Makefile
@@ -32,7 +32,7 @@ BUILD_OBJS=$(OBJS:S/^/$(BUILD)\//g)
 TOOLS_DIR=tools
 PRECOMPUTERS_DIR=precomputers
 
-all: build $(OBJS) $(SHARED) $(TOOLS) $(PRECOMPUTERS) test
+all: build $(OBJS) $(SHARED) $(TOOLS) $(PRECOMPUTERS)
 
 build:
 	mkdir -p $(BUILD)
@@ -45,8 +45,9 @@ build:
 $(SHARED):
 	$(CC) -shared -fPIC $(BUILD_OBJS) -o $(BUILD)/$(SHARED) $(LDFLAGS)
 
-test: $(TEST_SOURCE)
+test: all $(TEST_SOURCE)
 	$(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD_OBJS) $(LDFLAGS)
+	$(BUILD)/test
 
 # -- tools
 
diff --git a/cyclefind.c b/cyclefind.c
@@ -27,3 +27,39 @@ uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0,
 
   return lam;
 }
+
+uint64_t cyclefind_brent(uint64_t *mu, uint64_t x0,
+    uint64_t (*f)(uint64_t)) {
+  size_t i;
+  uint64_t power = 1;
+  uint64_t lam = 1;
+  uint64_t t = x0;
+  uint64_t h = f(x0);
+
+  while (t != h) {
+    if (power == lam) {
+      t = h;
+      power <<= 1;
+      lam = 0;
+    }
+
+    h = f(h);
+    lam++;
+  }
+
+  h = x0;
+  t = h;
+
+  for(i = 0; i < lam; i++) {
+    h = f(h);
+  }
+
+  *mu = 0;
+  while (t != h) {
+    t = f(t);
+    h = f(h);
+    (*mu)++;
+  }
+
+  return lam;
+}
diff --git a/cyclefind.h b/cyclefind.h
@@ -22,4 +22,23 @@
 uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0,
     uint64_t(*f)(uint64_t));
 
+/**
+ * Cycle finding (Brent's algorithm)
+ *
+ * This function finds the least natural number mu, such that x[mu]
+ * occurs an infinite number of times in the sequence
+ *   x[0], x[1], ...,
+ * recursively defined by the relation x[i+1] = f(x[i]), for i >= 0, and
+ * the least positive integer lambda such that
+ *   x[mu + k*lambda] = x[mu],
+ * for all natural numbers k.
+ *
+ * @param mu pointer to where to write value of mu, defined above
+ * @param x0 the value of x[0] in the sequence
+ * @param f  function pointer for f
+ * @returns the value of lambda, as defined above
+ */
+uint64_t cyclefind_brent(uint64_t *mu, uint64_t x0,
+    uint64_t (*f)(uint64_t));
+
 #endif
diff --git a/test_angrepp.c b/test_angrepp.c
@@ -16,8 +16,18 @@ static void test_cyclefind_floyd() {
   assert(mu == 1);
 }
 
+static void test_cyclefind_brent() {
+  uint64_t lambda, mu;
+  lambda = cyclefind_brent(&mu, 4, &test_f);
+
+  assert(lambda == 2);
+  assert(mu == 1);
+}
+
+
 int main() {
   test_cyclefind_floyd();
+  test_cyclefind_brent();
 
   printf("test ok\n");
 }