bash 计算多项式系数的脚本溢出

Question

我正在使用 bash 来计算多项式系数。代码如下：

#!/bin/bash

function factorial {
  declare n=
    (( n < 2 )) && echo 1 && return
      echo $(( n * $(factorial $((n-1))) ))
}

function binomial {
  declare n=
  declare k=
  echo $(( $(factorial $((n))) / ( $(factorial $((k))) * $(factorial $((n-k)))  ) ))
}

function multinomial {
  arr=("$@")
  declare mcoeff=1
  declare n=0
  for k in "${arr[@]}";
  do
    ((n=$n+$k))
    ((mcoeff=$mcoeff*$(binomial "$n" "$k")))
  done
  echo "$mcoeff"
}

multinomial $@

我好像在某些情况下溢出了。

$ ./multinomial.sh 4 5 6
630630
$ ./multinomial.sh 4 5 6 7
-119189070

知道如何解决这个问题吗？

Answer 1

A shell 是一种环境，可以从中调用工具，并使用一种语言对这些调用进行排序。它既不是功能齐全的编程语言，也不是用于复杂的计算。试试这个，我只是将您的 shell 代码翻译成等效的 awk:

$ cat multinomial.sh
#!/usr/bin/env bash

awk -v nums="$*" '
function factorial(n) {
    if ( n < 2 ) {
        return 1
    }
    return n * factorial(n-1)
}

function binomial(n,k) {
    return factorial(n) / ( factorial(k) * factorial(n-k) )
}

function multinomial(str,   arr, mcoeff, n, k) {
    split(str,arr)
    mcoeff = 1
    n = 0
    for (j=1; j in arr; j++) {
        k = arr[j]
        n = n + k
        mcoeff = mcoeff * binomial(n,k)
    }
    return mcoeff
}

BEGIN { print multinomial(nums) }
'

.

$ ./multinomial.sh 4 5 6
630630

$ ./multinomial.sh 4 5 6 7
107550162720

$ ./multinomial.sh 4 5 6 7 8
629483036137955968

bash 计算多项式系数的脚本溢出

getting overflow in bash script to compute the multinomial coeffcients

bash

overflow

multinomial