Average loop length: Difference between revisions

{{trans|Python}}

 

V result = 1.0

L(i) 2..n

 

=={{header|Ada}}==

with Ada.Numerics.Generic_Elementary_Functions;

with Ada.Numerics.Discrete_Random;

 

=={{header|BBC BASIC}}==

MAX_N = 20

TIMES = 1000000

=={{header|C}}==

 

#include <stdlib.h>

#include <math.h>

=={{header|C sharp|C#}}==

{{trans|Java}}

private static int N = 100000;

=={{header|C++}}==

Partial translation of C using stl and std.

#include <vector>

#include <iostream>

int randint(int n) {

int r, rmax = RAND_MAX / n * n;

r = dis(gen);

return r / (RAND_MAX / n);

}

 

//Factorial using dynamic programming to memoize the values.

for (;factorials.size() <= n;)

return factorials[n];

}

{{out}}

<pre>

-------------------------------

 

</pre>

=={{header|Clojure}}==

{{trans|Python}}

(:gen-class))

 

=={{header|D}}==

{{trans|Raku}}

 

real analytical(in int n) pure nothrow @safe /*@nogc*/ {

{{libheader| System.Math}}

{{Trans|C}}

program Average_loop_length;

 

20 5,2960 5,2936 0,046%

</pre>

=={{header|EchoLisp}}==

(lib 'math) ;; Σ aka (sigma f(n) nfrom nto)

{{trans|Ruby}}

{{works with|Elixir|1.1+}}

def factorial(0), do: 1

def factorial(n), do: Enum.reduce(1..n, 1, &(&1 * &2))

{{trans|Scala}}

<p>But uses the Gamma function instead of factorials.</p>

 

let gamma z =

The <code>loop-length</code> word is more or less a translation of the inner loop of C's <code>test</code> function.

{{works with|Factor|0.99 2020-01-23}}

math.functions math.ranges random sequences ;

 

 

=={{header|FreeBASIC}}==

 

Function Factorial(Byval N As Integer) As Double

 

=={{header|FutureBasic}}==

_nmax = 20

_times = 1000000

 

=={{header|Go}}==

 

import (

 

=={{header|Haskell}}==

import qualified Data.Set as S

import Text.Printf

 

We can implement f as {&LIST where LIST is an arbitrary list of N numbers, each picked independently from the range 0..(N-1). We can incrementally build the described sequence using (, f@{:) - here we extend the sequence by applying f to the last element of the sequence. Since we are only concerned with the sequence up to the point of the first repeat, we can select the unique values giving us (~.@, f@{:). This routine stops changing when we reach the desired length, so we can repeatedly apply it forever. For example:

0

(~.@, {&0 0@{:)^:_] 1

1 0</syntaxhighlight>

Once we have the sequence, we can count how many elements are in it.

2</syntaxhighlight>

Meanwhile, we can also generate all possible values of 1..N by counting out N^N values and breaking out the result as a base N list of digits.

0 0

0 1

1 1</syntaxhighlight>

All that's left is to count the lengths of all possible sequences for all possible distinct instances of f and average the results:

1

(+/ % #)@,@((#.inv i.@^~) ([: # (] ~.@, {:@] { [)^:_)"1 0/ i.)2

2.77469</syntaxhighlight>

Meanwhile the analytic solution (derived by reading the Ada implementation) looks like this:

ana"0]1 2 3 4 5 6

1 1.5 1.88889 2.21875 2.5104 2.77469</syntaxhighlight>

To get our simulation, we can take the exact approach and replace the part that generates all possible values for f with a random mechanism. Since the task does not specify how long to run the simulation, and to make this change easy, we'll use N*1e4 tests.

sim"0]1 2 3 4 5 6

1 1.5034 1.8825 2.22447 2.51298 2.76898</syntaxhighlight>

 

Finally, we can generate our desired results:

+--+-------+--------+-----------+

|N |average|analytic|error |

This uses a 0-based index (0, 1, ..., n-1) as opposed to the 1-based index (1, 2, ..., n) specified in the question, because it fits better with the native structure of Java.

 

import java.util.Random;

import java.util.Set;

=={{header|Julia}}==

{{trans|Python}}

 

analytical(n::Integer) = sum(factorial(n) / big(n) ^ i / factorial(n - i) for i = 1:n)

=={{header|Kotlin}}==

{{trans|Go}}

const val TESTS = 1000000

val rand = java.util.Random()

=={{header|Liberty BASIC}}==

{{trans|BBC BASIC}}

MAXN = 20

TIMES = 10000'00

 

=={{header|Lua}}==

local count = 0

for r = 1, reps do

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Table[{n, #[[1]], #[[2]],

Row[{Round[10000 Abs[#[[1]] - #[[2]]]/#[[2]]]/100., "%"}]} &@

=={{header|Nim}}==

{{trans|C}}

randomize()

 

=={{header|Oberon-2}}==

MODULE AvgLoopLen;

(* Oxford Oberon-2 *)

=={{header|PARI/GP}}==

{{trans|C}}

test(n, times)={

my(ct);

 

=={{header|Perl}}==

 

sub find_loop {

 

=={{header|Phix}}==

<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">,</span>

<span style="color: #000000;">ITER</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1000000</span>

=={{header|Phixmonti}}==

{{trans|Phix}}

 

20 var MAX

=={{header|PicoLisp}}==

{{trans|Python}}

(seed (in "/dev/urandom" (rd 8)))

 

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-AnalyticalLoopAverage ( [int]$N )

{

</syntaxhighlight>

Note: The use of the [pscustomobject] type accelerator to simplify making the test result table look pretty requires PowerShell 3.0.

# Display results for N = 1 through 20

ForEach ( $N in 1..20 )

=={{header|Python}}==

{{trans|C}}

from math import factorial

from random import randrange

19 5.1534 5.1522 0.024%

20 5.2927 5.2936 -0.017%</pre>

 

=={{header|R}}==

expected <- function(size) {

result <- 0

 

=={{header|Racket}}==

#lang racket

(require (only-in math factorial))

=={{header|Raku}}==

(formerly Perl 6)

constant TRIALS = 100;

for 1 .. MAX_N -> $N {

my $theoric = [+]

FIRST say " N empiric theoric (error)";

printf "%3d %9.4f %12.4f (%4.2f%%)\n",

}

sub find-loop { 0, | %^mapping{*} ...^ { (%){$_}++ } }</syntaxhighlight>

{{out|Example}}

 

Also note that the &nbsp; <big>'''!'''</big> &nbsp; (factorial function) &nbsp; uses memoization for optimization.

parse arg runs tests seed . /*obtain optional arguments from the CL*/

if runs =='' | runs =="," then runs = 40 /*Not specified? Then use the default.*/

40 7.6151 7.6091 0.0789

═══ ═════════ ═════════ ═════════

</pre>

 

=={{header|Ruby}}==

Ruby does not have a factorial method, not even in it's math library.

def factorial

self == 0 ? 1 : (1..self).inject(:*)

=={{header|Rust}}==

{{libheader|rand}}

 

use rand::{ThreadRng, thread_rng};

=={{header|Scala}}==

 

import scala.util.Random

 

=={{header|Scheme}}==

 

(import (scheme base)

(scheme write)

 

=={{header|Seed7}}==

include "float.s7i";

 

=={{header|Sidef}}==

{{trans|Perl}}

var seen = Hash()

loop {

 

=={{header|Simula}}==

 

REAL PROCEDURE FACTORIAL(N); INTEGER N;

 

=={{header|Tcl}}==

proc range {a b} {

for {set result {}} {$a <= $b} {incr a} {lappend result $a}

20 5.2992 5.2936 ( 0.11%)

</pre>

 

=={{header|Unicon}}==

{{trans|C}}

 

$define MAX_N 20

=={{header|VBA}}==

{{trans|Phix}}

Const ITER = 1000000

=={{header|VBScript}}==

Ported from the VBA version. I added some precalculations to speed it up

Const MAX = 20

Const ITER = 100000

</pre>

 

{{trans|Go}}

import math

 

{{trans|Go}}

{{libheader|Wren-fmt}}

 

var nmax = 20

var a = avg.call(n)

var b = ana.call(n)

var e = (a - b).abs/ b * 100

}</syntaxhighlight>

 

 

=={{header|zkl}}==

 

(" N average analytical (error)").println();