Code-challenge: How fast can you calculate 1000! with Powershell?-CodePudding

I have got a challenge to calculate 1000! with Powershell as fast as possible. Here the given rules for this code-challenge:

no predefined arrays or strings (except for initial 0!-value)
no use of external modules or embedded C# code
routine must be correct for any input from 0 till 1000
result-string must be created as part of the measurement

Based on this conditions I could create the below code-snippet as a first draft. Is there any idea to improve the speed? Inputs are more than welcome!

cls
Remove-Variable * -ea 0

$in = 1000

$runtime = measure-command {


    # define initial arr with 0! = 1:
    $arr = [System.Collections.Generic.List[uint64]]::new()
    $arr.Add(1)
    if ($in -gt 1) {

        # define block-dimension per array-entry:
        $posLen = 16
        $multiplier = [uint64][math]::Pow(10,$posLen)

        # calculate faculty:
        $start = 0
        foreach($i in 2..$in) {
            $div = 0
            if ($arr[$start] -eq 0){$start  }
            foreach($p in $start..($arr.Count-1)) {
                $mul = $i * $arr[$p]   $div
                $arr[$p] = $mul % $multiplier
                $div = [math]::Floor($mul/$multiplier)
            }
            if ($div -gt 0) {$arr.Add($div)}
        }
    }

    # convert array into string-result:
    $max = $arr.count-1
    $faculty = $arr[$max].ToString()
    if ($max -gt 1) {
        foreach($p in ($max-1)..0) {
            $faculty  = ($multiplier   $arr[$p]).ToString().Substring(1)
        }
    }
}

# check:
if ($in -eq 1000 -and !$faculty.StartsWith('402387260077') -or $faculty.length -ne 2568) {
    write-host 'result is not OK.' -f y 
}

# show result:
write-host 'runtime:' $runtime.TotalSeconds 'sec.'
write-host "`nfaculty of $in :`n$faculty"

CodePudding user response：

The fastest way is to rely on the existing multiplication capabilities of a data type designed specifically for large integers - like [bigint]:

$in = 1000

$runtime = Measure-Command {
  # handle 0!
  $n = [Math]::Max($in, 1)
  $b = [bigint]::Parse($n)

  while(--$n -ge 1){
    $b *= $n
  }
}

Clear-Host
Write-Host "Runtime: $($runtime.TotalSeconds)"
Write-Host "Factorial of $in is: `n$b"

This gives me a runtime of ~18ms, contrasting with ~300ms using your [uint64]-based carry approach :)

As Jeroen Mostert points out, you may be able to attain an additional improvement by side-stepping the *= operator and calling [BigInt]::Multiply directly:

# change this line
$b *= $n
# to this
$b = [bigint]::Multiply($b, $n)

I believe all the constraints are met as well:

no predefined arrays or strings (except for initial 0!-value)

Check!

no use of external modules or embedded C# code

Check! ([bigint] is part of the .NET base class library)

routine must be correct for any input from 0 till 1000

Check!

result-string must be created as part of the measurement

We're already tracking the result as an integer, thereby implicitly storing the string representation