cyclefind.h (1427B)
1 #ifndef CYCLEFIND_H 2 #define CYCLEFIND_H 3 4 #include <stdlib.h> 5 6 /** 7 * Cycle finding (Floyd's algorithm) 8 * 9 * This function finds the least natural number mu, such that x[mu] 10 * occurs an infinite number of times in the sequence 11 * x[0], x[1], ..., 12 * recursively defined by the relation x[i+1] = f(x[i]), for i >= 0, and 13 * the least positive integer lambda such that 14 * x[mu + k*lambda] = x[mu], 15 * for all natural numbers k. 16 * 17 * @param mu pointer to where to write value of mu, defined above 18 * @param x0 the value of x[0] in the sequence 19 * @param f function pointer for f 20 * @returns the value of lambda, as defined above 21 */ 22 uint64_t cyclefind_floyd(uint64_t *mu, uint64_t x0, 23 uint64_t (*f)(uint64_t)); 24 25 /** 26 * Cycle finding (Brent's algorithm) 27 * 28 * This function finds the least natural number mu, such that x[mu] 29 * occurs an infinite number of times in the sequence 30 * x[0], x[1], ..., 31 * recursively defined by the relation x[i+1] = f(x[i]), for i >= 0, and 32 * the least positive integer lambda such that 33 * x[mu + k*lambda] = x[mu], 34 * for all natural numbers k. 35 * 36 * @param mu pointer to where to write value of mu, defined above 37 * @param x0 the value of x[0] in the sequence 38 * @param f function pointer for f 39 * @returns the value of lambda, as defined above 40 */ 41 uint64_t cyclefind_brent(uint64_t *mu, uint64_t x0, 42 uint64_t (*f)(uint64_t)); 43 44 #endif