Java Program to Implement Brent Cycle Algorithm

This is a Java Program to Implement Brent Cycle Algorithm. Cycle detection is the algorithmic problem of finding a cycle in a sequence of iterated function values. Brent Cycle Algorithm is an alternative cycle detection algorithm that, like the tortoise and hare algorithm, requires only two pointers into the sequence.

Here is the source code of the Java Program to Implement Brent Cycle Algorithm . The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. /**
  2.  ** Java Program to Implement Brent Cycle Algorithm 
  3.  **/
  4.  
  5. import java.util.Scanner;
  6. import java.util.List;
  7. import java.util.ArrayList;
  8.  
  9. /** Class BrentCycle **/
  10. public class BrentCycle
  11. {
  12.     private List<Integer> func;
  13.     private int lam, mu; 
  14.     /** Constructor **/
  15.     public BrentCycle(List<Integer> list, int x0)
  16.     {
  17.         func = list;
  18.         /** print sequence **/
  19.         printSequence(x0);
  20.         /** find cycle **/
  21.         findCycle(x0);
  22.         /** display results **/
  23.         display();
  24.     }
  25.     /** function to find cycle **/
  26.     private void findCycle(int x0)
  27.     {
  28.         int power, lam;
  29.         power = lam = 1;
  30.         int tortoise = x0;
  31.         int hare = f(x0);
  32.  
  33.         while (tortoise != hare)
  34.         {
  35.             if (power == lam)
  36.             {
  37.                 tortoise = hare;
  38.                  power *= 2;
  39.                   lam = 0;
  40.             }
  41.             hare = f(hare);
  42.             lam += 1;
  43.         }
  44.         mu = 0;
  45.         tortoise = hare = x0;
  46.         for (int i = 0; i < lam; i++)
  47.         {
  48.             hare = f(hare);
  49.         }
  50.         while (tortoise != hare)
  51.         {
  52.             tortoise = f(tortoise);
  53.               hare = f(hare);
  54.             mu += 1;
  55.         }
  56.         this.lam = lam;
  57.         this.mu = mu;
  58.     }
  59.     /** function to return value of function f(x) **/
  60.     private int f(int p)
  61.     {
  62.         return func.get(p);
  63.     }
  64.     /** function to print first n sequence **/
  65.     public void printSequence(int x0)
  66.     {
  67.         int n = func.size();
  68.         int tempx = x0;
  69.         System.out.print("\nFirst "+ n +" elements in sequence : \n"+ tempx);
  70.         for (int i = 0; i < n; i++)
  71.         {
  72.             tempx = f(tempx);
  73.             System.out.print(" "+ tempx);
  74.         }
  75.         System.out.println();        
  76.     }
  77.     /** function to display results **/
  78.     public void display()
  79.     {
  80.         System.out.println("\nLength of cycle : "+ lam);
  81.         System.out.println("Position : "+ (mu + 1));
  82.     }
  83.     /** Main function **/
  84.     public static void main(String[] args)
  85.     {
  86.         Scanner scan = new Scanner(System.in);
  87.         System.out.println("Brent Cycle Algorithm Test\n");
  88.         System.out.println("Enter size of list");
  89.         int n = scan.nextInt();
  90.         List<Integer> list = new ArrayList<Integer>();
  91.         System.out.println("\nEnter f(x)");
  92.         for (int i = 0; i < n; i++)
  93.             list.add(scan.nextInt());
  94.         System.out.println("\nEnter x0");
  95.         int x0 = scan.nextInt();
  96.         BrentCycle bc = new BrentCycle(list, x0);
  97.     }
  98. }

Brent Cycle Algorithm Test
 
Enter size of list
9
 
Enter f(x)
6 6 0 1 4 3 3 4 2
 
Enter x0
8
 
First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6
 
Length of cycle : 3
Position : 4

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.