代码挑战：你能多快计算 1000！用Powershell？

Question

我遇到了计算 1000 的挑战！尽可能快地使用 Powershell。这里是这个代码挑战的给定规则：

没有预定义的数组或字符串（初始 0!-value 除外）
不使用外部模块或嵌入式 C# 代码
对于从 0 到 1000 的任何输入，例程必须正确
结果字符串必须作为测量的一部分创建

基于此条件，我可以创建以下代码片段作为初稿。有什么想法可以提高速度吗？非常欢迎输入！

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"

Answer 1

最快的方法是依靠专为大整数设计的数据类型的现有乘法功能 - 如 [bigint]:

$in = 1000

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

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

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

这给了我大约 18 毫秒的运行时间，与使用基于 [uint64] 的进位方法的大约 300 毫秒形成对比:)

正如 Jeroen Mostert 指出的那样，您可以通过 side-stepping *= 运算符并直接调用 [BigInt]::Multiply 来获得额外的改进：

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

我相信所有的限制条件都满足了：

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

检查！

no use of external modules or embedded C# code

检查！（[bigint] 是 .NET 基础 class 库的一部分）

routine must be correct for any input from 0 till 1000

检查！

result-string must be created as part of the measurement

我们已经将结果作为整数进行跟踪，从而隐式存储字符串表示形式

代码挑战：你能多快计算 1000！用Powershell？

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

powershell