Κυριακή 20 Οκτωβρίου 2024

Cycle Detection

https://rosettacode.org/wiki/Cycle_detection#M2000_Interpreter

This is the output of the program:

 Brent's algorithm
 Cycle starts at position: 2 (starting position = 0)
 The length of the Cycle = 6

 Cycle: 101, 2, 5, 26, 167, 95

This is the FREEBASIC program:

' version 11-01-2017
' compile with: fbc -s console

' define the function f(x)=(x*x +1) mod 255
Function f(x As Integer) As Integer
    Return (x * x +1) Mod 255
End Function

Sub brent(x0 As Integer, ByRef lam As Integer, ByRef mu As Integer)

    Dim As Integer i, power = 1
    lam = 1

    ' main phase: search successive powers of two
    Dim As Integer tortoise = f(x0)   ' f(x0) is the element/node next to x0.
    Dim As Integer hare = f(f(x0))

    While tortoise <> hare
        If power = lam Then
            tortoise = hare
            power *= 2
            lam = 0
        End If
        hare = f(hare)
        lam += 1
    Wend

    ' Find the position of the first repetition of length ?
    mu = 0
    tortoise = x0
    hare = x0
    For i = 0 To lam -1
        ' range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    Next
    ' The distance between the hare and tortoise is now ?.

    ' Next, the hare and tortoise move at same speed until they agree
    While tortoise <> hare
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
    Wend

End Sub

' ------=< MAIN >=------

Dim As Integer  i, j, lam, mu, x0 = 3

brent(x0, lam, mu)
Print " Brent's algorithm"
Print " Cycle starts at position: "; mu; " (starting position = 0)"
Print " The length of the Cycle = "; lam
Print

j = f(x0)
Print " Cycle: ";
For i = 1 To lam + mu -1
    If i >= mu Then
        Print j;
        If i <> (lam + mu -1) Then Print ", "; Else Print ""
    End If
    j = f(j)
Next
Print

' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End


So I made some corretcions to translate to M2000 code, as less work as possible. Finally I put the code on a module. A module ins't a SUB. A module has own name space, a sub use the module's name space, so the simple function f() which we call using @f(). See the Local statements to make integers as local variables to Sub.

// https://rosettacode.org/wiki/Cycle_detection#
module Brent`s_Algorithm {
' Translated from FreeBasic
' Integer is 16bit integer
' Change to Long or Long Long for bigger numbers
Integer i, j, lam, mu, x0 = 3

brent(x0, &lam, &mu)
Print " Brent's algorithm"
Print " Cycle starts at position: "; mu; " (starting position = 0)"
Print " The length of the Cycle = "; lam
Print

j = @f(x0)
Print " Cycle: ";
For i = 1 To lam + mu -1
    If i >= mu Then
        Print j;
        If i <> (lam + mu -1) Then Print ", "; Else Print ""
    End If
    j = @f(j)
Next
Print


Function f(x As Integer)
    =(x * x +1) Mod 255
End Function

Sub brent(x0 As Integer, &lam As Integer, &mu As Integer)

    Local Integer i, power = 1
    lam = 1
	
    ' main phase: search successive powers of two
    Local Integer tortoise = @f(x0) ' f(x0) is the element/node next to x0.
    Local Integer hare = @f(@f(x0))

    While tortoise <> hare
        If power = lam Then
            tortoise = hare
            power *= 2
            lam = 0
        End If
        hare = @f(hare)
        lam += 1
    End While
    ' Find the position of the first repetition of length ?
    mu = 0
    tortoise = x0
    hare = x0
    if lam>0 then
        For i = 0 To lam -1
            ' range(lam) produces a list with the values 0, 1, ... , lam-1
            hare = @f(hare)
        Next
    end if
    ' The distance between the hare and tortoise is now ?.

    ' Next, the hare and tortoise move at same speed until they agree
    While tortoise <> hare
        tortoise = @f(tortoise)
        hare = @f(hare)
        mu += 1
    End While
End Sub
}
Brent`s_Algorithm


Δεν υπάρχουν σχόλια:

Δημοσίευση σχολίου

You can feel free to write any suggestion, or idea on the subject.