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
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
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.