Average loop length: Difference between revisions

20 5.2699 5.2936 ( 0.45%)</pre>

<br>

 

=={{header|Ada}}==

with Ada.Numerics.Generic_Elementary_Functions;

with Ada.Numerics.Discrete_Random;

Put(err, Fore=>3, Aft=>3, exp=>0); New_line;

end loop;

{{out}}

<pre>

 

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

MAX_N = 20

TIMES = 1000000

DEF FNfactorial(n)

{{out}}

<pre>

=={{header|C}}==

 

#include <stdlib.h>

#include <math.h>

}

return 0;

{{out}}

<pre>

19 5.1479 5.1522 -0.084%

20 5.2957 5.2936 0.040%

</pre>

 

=={{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];

}

return 0;

}

{{out}}

<pre>

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

 

</pre>

=={{header|Clojure}}==

{{trans|Python}}

(:gen-class))

 

diff (Math/abs (* 100 (- 1 (/ avg anal))))]]

(println (format "%3d\t%.4f\t%.4f\t%.2f%%" q avg anal diff)))

{{Output}}

<pre>

=={{header|D}}==

{{trans|Raku}}

 

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

n, average, an, errorS);

}

{{out}}

<pre> n average analytical (error)

39 7.51864 7.50959 ( 0.1204%)

40 7.60255 7.60911 ( 0.0863%)</pre>

 

=={{header|EchoLisp}}==

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

(define fa (f-anal N))

(printf "%3d %10d %10d %10.2d %%" N fc fa (// (abs (- fa fc)) fc 0.01))))

{{out}}

<pre>

{{trans|Ruby}}

{{works with|Elixir|1.1+}}

def factorial(0), do: 1

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

 

runs = 1_000_000

 

{{out}}

{{trans|Scala}}

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

 

let gamma z =

printfn "%2i %2.6f %2.6f %+2.3f%%" n avg theory ((avg / theory - 1.) * 100.))

0

{{out}}

<pre> N average analytical (error)

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 ;

 

 

" n\tavg\texp.\tdiff\n-------------------------------" print

{{out}}

<pre>

19 5.1519 5.1522 -0.005%

20 5.2927 5.2936 -0.017%

</pre>

 

=={{header|Go}}==

 

import (

}

return sum

{{out}}

<pre>

 

=={{header|Haskell}}==

import qualified Data.Set as S

import Text.Printf

range = [1..20] :: [Integer]

_ <- test samples range $ mkStdGen 0

<pre> N average analytical (error)

=== ========= ============ =========

 

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

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

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 0

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

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

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

ana"0]1 2 3 4 5 6

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

The simulation approach is noticeably slower than the analytic approach, while being less accurate.

 

Finally, we can generate our desired results:

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

|N |average|analytic|error |

|19| 5.1522|5.14785 |0.000843052|

|20|5.29358|5.28587 | 0.00145829|

Here, error is the difference between the two values divided by the analytic value.

 

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)

 

main(20)

 

{{out}}

=={{header|Kotlin}}==

{{trans|Go}}

const val TESTS = 1000000

val rand = java.util.Random()

println(String.format("%3d %6.4f %10.4f (%4.2f%%)", n, a, b, Math.abs(a - b) / b * 100.0))

}

Sample output:

{{out}}

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

{{trans|BBC BASIC}}

MAXN = 20

TIMES = 10000'00

IF n=1 OR n=0 THEN FNfactorial=1 ELSE FNfactorial= n * FNfactorial(n-1)

end function

 

{{out}}

20 5.2792 5.29358459 -0.2717%

</pre>

 

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

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

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

RandomInteger[{1, n}, n]] &] &, 10000]],

Sum[n! n^(n - k - 1)/(n - k)!, {k, n}]/n^(n - 1)}, 5], {n, 1,

{{Out}}

<pre>N average analytical error

=={{header|Nim}}==

{{trans|C}}

randomize()

inc result

bits = bits or x

echo " n\tavg\texp.\tdiff"

let theory = expected(n)

let diff = (avg / theory - 1) * 100

{{out}}

<pre> n avg exp. diff

 

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

MODULE AvgLoopLen;

(* Oxford Oberon-2 *)

END

END AvgLoopLen.

{{Out}}

<pre>

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

{{trans|C}}

test(n, times)={

my(ct);

my(cnt=test(n, TIMES),avg=cnt/TIMES,ex=expected(n),diff=(avg/ex-1)*100.);

print(n"\t"avg*1."\t"ex*1."\t"diff);

{{out}}

<pre>1 1.0000 1.0000 0.E-7

 

=={{header|Perl}}==

 

sub find_loop {

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

$n, $empiric, $theoric, 100 * ($empiric - $theoric) / $theoric;

{{out}}

<pre> N empiric theoric (error)

 

=={{header|Phix}}==

{{out}}

<pre>

20 5.2955 5.2936 (0.037%)

</pre>

 

=={{header|PicoLisp}}==

{{trans|Python}}

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

 

2 ) ) ) ) )

 

 

=={{header|PowerShell}}==

{{works with|PowerShell|2}}

function Get-AnalyticalLoopAverage ( [int]$N )

{

return $LoopAvereage

}

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 )

}

}

{{out}}

<pre>

=={{header|Python}}==

{{trans|C}}

from math import factorial

from random import randrange

theory = analytical(n)

diff = (avg / theory - 1) * 100

{{out}}

<pre> n avg exp. diff

19 5.1534 5.1522 0.024%

20 5.2927 5.2936 -0.017%</pre>

 

=={{header|R}}==

expected <- function(size) {

result <- 0

cat(sprintf("%3d%11.4f%14.4f ( %4.4f%%)\n", num, round(average,4), round(analytical,4), round(error,2)))

}

 

{{out}}

 

=={{header|Racket}}==

#lang racket

(require (only-in math factorial))

 

(test-table 20 10000)

 

{{out}}

=={{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",

}

{{out|Example}}

<pre> N empiric theoric (error)

 

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

/*──────────────────────────────────────────────────────────────────────────────────────*/

fmtD: parse arg y,d; d=word(d 4, 1); y=format(y, , d); parse var y w '.' f

{{out|output|text=&nbsp; when using the default inputs:}}

<pre style="height:90ex">

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(:*)

analytical = (1..n).inject(0){|sum, i| sum += (n.factorial / (n**i).to_f / (n-i).factorial)}

puts "%3d %8.4f %8.4f (%8.4f%%)" % [n, avg, analytical, (avg/analytical - 1)*100]

{{out}}

<pre>

=={{header|Rust}}==

{{libheader|rand}}

 

use rand::{ThreadRng, thread_rng};

 

 

{{out}}

Using default arguments:

=={{header|Scala}}==

 

import scala.util.Random

 

 

}

{{out}}

<pre>

=={{header|Scheme}}==

 

(import (scheme base)

(scheme write)

(newline)))

(iota 20 1))

 

{{out}}

 

=={{header|Seed7}}==

include "float.s7i";

 

analytical digits 4 lpad 7 <& err digits 3 lpad 7);

end for;

 

{{out}}

=={{header|Sidef}}==

{{trans|Perl}}

var seen = Hash()

loop {

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

n, empiric, theoric, 100*(empiric-theoric)/theoric)

{{out}}

<pre>

 

=={{header|Simula}}==

 

REAL PROCEDURE FACTORIAL(N); INTEGER N;

END FOR I;

END;

{{in}}

<pre>678</pre>

 

=={{header|Tcl}}==

proc range {a b} {

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

set e [Experimental $n 100000]

puts [format "%3d %9.4f %12.4f (%6.2f%%)" $n $e $a [expr {abs($e-$a)/$a*100.0}]]

{{out}}

<pre>

20 5.2992 5.2936 ( 0.11%)

</pre>

 

=={{header|Unicon}}==

{{trans|C}}

 

$define MAX_N 20

}

return 0

{{out}}

<pre> n avg exp. diff

=={{header|VBA}}==

{{trans|Phix}}

Const ITER = 1000000

Debug.Print Format(ex, "0.0000"); " ("; Format(Abs(1 - av / ex), "0.000%"); ")"

Next n

<pre> n avg. exp. (error%)

== ====== ====== ========

19 5,1530 5,1522 (0,016%)

20 5,2958 5,2936 (0,041%)</pre>

 

=={{header|zkl}}==

 

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

n=n.toFloat();

(1).reduce(n,'wrap(sum,i){ sum+fact(n)/n.pow(i)/fact(n-i) },0.0);

{{out}}

<pre>