Symbol Newtona w PowerShell

Chciałem poćwiczyć z symbolem Newtona, więc postanowiłem napisać skrypt w PS, aby porównać te sposoby uzyskiwania współczynnika dwumianowego.
Oczywiście do symbolu Newtona będziemy potrzebowali funkcję zwracającą wartość silni.

function Get-Factorial([int]$n)
{
    if($n -lt 1) {
        return 1
    }
    $facttorialRec = Get-Factorial($n -1)
    return ($n * $facttorialRec )
}

Jak na razie funkcja oblicza silnie rekurencyjnie (ale mam w planach dodać jeszcze silnie obliczoną w sposób iteracyjnie).

Mamy też funkcję obliczającą symbol Newtona za pomocą rekurencji:

function Get-BinomialCoefficientRec([int]$n, [int]$k)
{
    if($k -lt 0 -OR $k -gt $n)
        {return 0}

    if($k -eq 0 -OR $k -eq $n -OR $n -lt 1)
        {return 1} 

    $diff = $n - $k
    if($k -gt $diff)
    {
        $k = $diff
    }
    
    $binomial1 = Get-BinomialCoefficientRec -n ($n-1) -k $k
    $binomial2 = Get-BinomialCoefficientRec -n ($n-1) -k ($k-1)
    return $binomial1 + $binomial2
}

Oraz funkcję korzystającą z tożsamości algebraicznej:

function Get-BinomialCoefficientIteratively([int]$n, [int]$k)
{
    if ($k -lt 0 -or  $k -gt $n)
    {return 0}
 
    if($k -eq  0 -or  $k -eq  $n)
    { return 1}

    $diff = $n - $k
    if ($k -gt $diff)
    {  $k = $diff }
    
    $prod = 1
    for($i=1; $i -le $k; $i++)
    {
        $prod = $prod * (  ($n - $i + 1) / $i  )    
    }

    return $prod
}

Możemy wyliczyć symbol Newtona na ze wzoru Sterlinga. Wzór ten stosuje się dla bardzo dużych liczb, gdyż błędy względne są małe.

function Get-StirlingApproximation([int]$n)
{

    $numDivE = $n / [math]::E
    $const = [math]::Sqrt(2.0 * $n * [math]::PI)
    $result = $const * ([math]::Pow(($numDivE) ,$n))   
    if($result -eq 0)
        {return 1}
    return $result
}

Główna funkcja, która agreguje funkcje zliczające współczynnik dwumianowy jest przedstawiona poniżej:

function Get-BinomialCoefficient
{
    param(
    [ValidateSet('factorial','recursive', 'multiplicative', 'stirling'  )]
    [string]$arg='factorial',

    [Parameter(Mandatory=$true, Position=0)]  
    [int]$n,

    [Parameter(Mandatory=$true, Position=1)]  
    [int]$k
    )

    if($arg -eq 'factorial')
    {
         $upperFractal = Get-Factorial($n) 
         $lowerFractalK = Get-Factorial ($k) 
         $lowerFractalNK=  Get-Factorial($n- $k)
         return $upperFractal  / ($lowerFractalK * $lowerFractalNK)
    }
    elseif($arg -eq 'stirling')
    {
        $aproxN = Get-StirlingApproximation($n)
        $aproxK = Get-StirlingApproximation ($k)
        $aproxNK = Get-StirlingApproximation($n- $k)
        return  $aproxN/ ( $aproxK  *$aproxNK )
    }
    elseif($arg -eq 'recursive')
    {
        return Get-BinomialCoefficientRec -n $n -k $k
    }
    elseif($arg -eq 'multiplicative')
    {
        return Get-BinomialCoefficientIteratively -n $n -k $k
    }

    throw 'Wrong argument in parameter $arg'
}

A funkcja do pomiaru wygląda następująco:

function Measure-BinomialCoefficient([int]$to)
{
    $Nenum = 1..$to
    $Nenum | %{
        $n = $_
        $Kenum = 1..$n 
        $Kenum | %{
           $k = $_
           $factorialMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       })

           $multiplicativeMeasure =    
(Invoke-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  })

           $recursiveMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       })

           $stirlingMeasure =          
(Invoke-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        })


            return new-object PSObject | 
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  n  -Value $n |
               
Add-Member -PassThru -MemberType NoteProperty 
-Name  k  -Value $k |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  factorial  -Value $factorialMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  multiplicative  -Value $multiplicativeMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  recursive  -Value $recursiveMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  stirling  -Value $stirlingMeasure
        }
    }
}

Wyniki tych wywołań są przedstawione poniżej. Co prawda wzór Stirling nie daje dokładnej wartości, ale jestem pod wrażeniem przybliżenia wartości symbolu Newtona.

Aby uzyskać czasy działania algorytmów to wystarczy zamienić słowa Invoke na Measure oraz dodać TotalMilliseconds - pomiary są w milisekundach.

           $factorialMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       }).TotalMilliseconds

           $multiplicativeMeasure =    
(Measure-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  }).TotalMilliseconds

           $recursiveMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       }).TotalMilliseconds

           $stirlingMeasure =          
(Measure-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        }).TotalMilliseconds

A poniżej wykres przedstawiający czasy działania algorytmów (dla różnych n i k):

Gdybyśmy ograniczyli ilość danych poprzez wprowadzenie parametru k jako połowa parametru n oraz przedstawili dane na wykresie w skali logarytmicznej to mamy taki wykres:

Co dla mnie jest dziwne, to czasy obliczeń symbolu Newtona za pomocą wzoru Sterlinga oraz dla iteracyjnego sposób wyliczenia się zmniejszają :)
Takie rzeczy to tylko w PS.