Floyd's Cycle Finding Algorithm

[CrackaLackaZe]

This might turn out to be a rather naive math question, please bear with me...

I have a question regarding Floyd's Cycle Finding Algorithm, specifically the choice of the value at which to increment the hare pointer by.

For those unfamiliar with the algorithm, you can find an explanation here: link

Now, I know that for some variations of this algorithm, you can opt to dynamically increase the hare pointer speed in exponential increments (by powers of 2, specifically) as the turtle continues to move by 1.

My question is the following:

In a cyclic sequence of numbers: 1->2->3->4->5->6->1->2->3->4->5->6->1..., where the value of the turtle starts at 2, and the value of the hare starts at 3.

When the speed of the hare increases to 3 and remains 3 (hare = hare[i+3], or hare = hare->next->next->next), why does does it fail to detect the cycle?

Sample code attached.

Thanks.

EDIT: Tried to attach the code, but it's stripping my hard returns
EDIT v2: I'll try including it in the body.


#include <stdio.h>

struct item
{
int value;
struct item *next;
};

void printList(struct item *head);
void appendNodeToList(struct item *node, struct item *new_node);
void appendValueToList(struct item *node, int value);
void appendValuesToList(struct item *node, int max);
int hasCycle(struct item *node);

int main(void)
{

struct item head;

head.value = 1;

appendValuesToList(&head, 5);
appendNodeToList(&head, &head);

printList(&head);

printf("hasCycle: %d\n", hasCycle(&head));

return 0;
}

void appendNodeToList(struct item *node, struct item *new_node)
{

while (node != NULL) {
if (node->next == NULL) {
node->next = malloc(sizeof(struct item));
node->next = new_node;
break;
}
node = node->next;
}
}

void appendValuesToList(struct item *node, int max)
{
int i;

for (i = 0; i < max; i++) {
node->next = malloc(sizeof(struct item));
(node->next)->value = node->value+1;
node = node->next;
}
}


void appendValueToList(struct item *node, int value)
{
struct item new_node;
new_node.value = value;
new_node.next = NULL;

while (node != NULL) {
if (node->next == NULL) {
node->next = malloc(sizeof(struct item));
*node->next = new_node;
break;
}
node = node->next;
}
}

int hasCycle(struct item *node)
{
int ret = 0;

if (node->next == NULL || node->next->next == NULL)
return ret;

int count = 0;
struct item *turtle = node->next;
struct item *hare = turtle->next;

while (turtle->next != NULL) {
count++;
printf("[count:%d] turtle = %d, hare = %d\n", count, turtle->value, hare->value);
if (turtle->value == hare->value) {
ret = 1;
break;
}
turtle = turtle->next;
//works fine
hare = hare->next->next;
//unexpected results -- does not detect cycle: hare = hare->next->next->next;
}

return ret;
}

 

[degibson]

Three divides the number of nodes evenly, so the hare's pointer only sees two nodes. Since the turtle advances only by one:

Steps: (I only show the mod 6 as needed for clarity -- it is assumed on every operation )
Turtle = i-1 Hare = i
Turtle = i Hare = i+3
Turtle = i+1 Hare = (i+3+3) % 6 = i
Turtle = i+2 Hare = i + 3
Turtle = i+3 Hare = (i + 3 + 3) % 6 = i
Turtle = i+4 Hare = i + 3
Turtle = i+5 Hare = (i + 3 + 3) % 6 = i
Turtle = (i+6)%6 = i Hare = i + 3

 

[CrackaLackaZe]

Sorry, I should have been more clear...I guess I'm looking for more or less a mathematical proof or explanation as to why this occurs. I can observe what happens to the hare pointer, but it's not clear to me the reason behind this situation.

For example, in the case that I mentioned, the hare pointer just happens to flip flop between 6 and 3, and it just so happens to never match up with the turtle pointer. I understand that the hare pointer only sees 2 nodes, but the reason for the fact that they never collide is what I'm curious about.

Thanks.

 

[degibson]

I don't know the generalization -- perhaps something to do with a relationship between the hare's jump size and the length of the cycle.