Anonymous user
Cycle detection: Difference between revisions
Scala contribution added.
(Scala contribution added.) |
|||
Line 2,170:
</pre>
=={{header|Scala}}==
{{Out}}Best seen in running your browser either by [https://scalafiddle.io/sf/6O7WjnO/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/kPCg0fxOQQCZPkOnmMR0Kg Scastie (remote JVM)].
<lang Scala>object CycleDetection extends App {
def brent(f: Int => Int, x0: Int): (Int, Int) = {
// main phase: search successive powers of two
// f(x0) is the element/node next to x0.
var (power, λ, μ, tortoise, hare) = (1, 1, 0, x0, f(x0))
while (tortoise != hare) {
if (power == λ) { // time to start a new power of two?
tortoise = hare
power *= 2
λ = 0
}
hare = f(hare)
λ += 1
}
// Find the position of the first repetition of length 'λ'
tortoise = x0
hare = x0
for (i <- 0 until λ) hare = f(hare)
// 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)
μ += 1
}
(λ, μ)
}
def cycle = loop.slice(μ, μ + λ)
def f = (x: Int) => (x * x + 1) % 255
// Generator for the first terms of the sequence starting from 3
def loop: LazyList[Int] = 3 #:: loop.map(f(_))
val (λ, μ) = brent(f, 3)
println(s"Cycle length = $λ")
println(s"Start index = $μ")
println(s"Cycle = ${cycle.force}")
}</lang>
=={{header|Sidef}}==
{{trans|Perl 6}}
Line 2,217 ⟶ 2,264:
say [seq[s .. (s + l - 1)]]</lang>
{{out}}
<pre>3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...▼
▲3, 10, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, 101, 2, 5, 26, 167, 95, ...
Cycle length 6.
Cycle start index 2.
[101, 2, 5, 26, 167, 95]</pre>
=={{header|Visual Basic .NET}}==
{{trans|C#}}
| |||