How to resolve the algorithm Average loop length step by step in the uBasic/4tH programming language

Published on 12 May 2024 09:40 PM
#Ubasic/4th

How to resolve the algorithm Average loop length step by step in the uBasic/4tH programming language

Table of Contents

Problem Statement

Let f be a uniformly-randomly chosen mapping from the numbers 1..N to the numbers 1..N (note: not necessarily a permutation of 1..N; the mapping could produce a number in more than one way or not at all). At some point, the sequence 1, f(1), f(f(1))... will contain a repetition, a number that occurring for the second time in the sequence.

Write a program or a script that estimates, for each N, the average length until the first such repetition. Also calculate this expected length using an analytical formula, and optionally compare the simulated result with the theoretical one.

This problem comes from the end of Donald Knuth's Christmas tree lecture 2011. Example of expected output:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Average loop length step by step in the uBasic/4tH programming language

Source code in the ubasic/4th programming language

M = 14
T = 100000

If Info("wordsize") < 64 Then Print "This program requires a 64-bit uBasic" : End

Print "N\tavg\tcalc\t%diff"

For n = 1 To M
  a = FUNC(_Test(n, T))
  h = FUNC(_Analytical(n))
  d = FUNC(_Fmul(FUNC(_Fdiv(a, h)) - FUNC(_Ntof(1)), FUNC(_Ntof(100))))

  Print n; "\t";
  Proc _Fprint (a) : Print "\t";
  Proc _Fprint (h) : Print "\t";
  Proc _Fprint (d) : Print "%"
Next
End

_Analytical
  Param (1)
  Local (3)

  c@ = 0
  For b@ = 1 To a@
    d@ = FUNC(_Fdiv(FUNC(_Factorial(a@)), a@^b@))
    c@ = c@ + FUNC(_Fdiv (d@, FUNC(_Ntof(FUNC(_Factorial(a@-b@))))))
  Next
Return (c@)

_Test
  Param (2)
  Local (4)

  e@ = 0
  For c@ = 1 To b@
    f@ = 1 : d@ = 0
    Do While AND(d@, f@) = 0
      e@ = e@ + 1
      d@ = OR(d@, f@)
      f@ = SHL(1, Rnd(a@))
    Loop
  Next
Return (FUNC(_Fdiv(e@, b@)))

_Factorial
  Param(1)

  If (a@ = 1) + (a@ = 0) Then Return (1)
Return (a@ * FUNC(_Factorial(a@-1)))

_Fmul Param (2) : Return ((a@*b@)/16384)
_Fdiv Param (2) : Return ((a@*16384)/b@)
_Ftoi Param (1) : Return ((10000*a@)/16384)
_Itof Param (1) : Return ((16384*a@)/10000)
_Ntof Param (1) : Return (16384*a@)
_Fprint Param (1) : a@ = FUNC(_Ftoi(a@)) : Print Using "+?.####";a@; : Return

You may also check:How to resolve the algorithm Mad Libs step by step in the Erlang programming language
You may also check:How to resolve the algorithm Create a two-dimensional array at runtime step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Jewels and stones step by step in the C programming language
You may also check:How to resolve the algorithm Averages/Arithmetic mean step by step in the Tcl programming language
You may also check:How to resolve the algorithm Inverted syntax step by step in the Sidef programming language