cangrepp

commit 66858f5dd8dcdd32d0df66d1f2a8c46f832b4a3f
parent 71e31251ae8b7c8c9316867e88245184455529d9
Author: olikru <olikru@tkruger.se>
Date:   Tue, 16 Jan 2024 08:11:13 +0100

doc floyd's

Diffstat:
M
cyclefind.c
 | 
3
++-
M
cyclefind.h
 | 
19
++++++++++++++++++-

2 files changed, 20 insertions(+), 2 deletions(-)
diff --git a/cyclefind.c b/cyclefind.c
@@ -1,6 +1,7 @@
 #include "cyclefind.h"
 
-uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t)) {
+uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0,
+    uint64_t (*f)(uint64_t)) {
   uint64_t t = f(x0);
   uint64_t h = f(t);
   uint64_t lam = 1;
diff --git a/cyclefind.h b/cyclefind.h
@@ -3,6 +3,23 @@
 
 #include <stdlib.h>
 
-uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0, uint64_t (*f)(uint64_t));
+/**
+ * Cycle finding (Floyd'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_floyd(uint64_t *mu, uint64_t x0,
+    uint64_t(*f)(uint64_t));
 
 #endif