Challenges for Linux Users Group on fb

001_factorial.sh

#!/bin/sh
# https://www.facebook.com/groups/LinuxUsersGroupOfficial/posts/4186776714756296/

error(){
    >&2 echo "$@"
}

validate_and_calc(){
    # https://stackoverflow.com/a/808740
    if [ "$1" -eq "$1" ] 2>/dev/null
    then
        the_factorial "$1"
    else
        error "$1 is not an integer"
    fi
}

the_factorial(){
    N="$1"
    F="1"
    if [ "$N" -lt "0" ];
    then
        error "Thou shall not try and calculate factorials for negative integers."
        error ""
        error "You might have some luck with non-integer negatives,"
        error "see https://en.wikipedia.org/wiki/Gamma_function"
    elif [ "$N" -le "20" ]; # 21 factorial needs floating point math 
    then
        while [ "$N" -gt "1" ]; do
            F=$(( F * N ))
            N=$(( N - 1 ))
        done
        echo "$F"
    else
        # A proper implementation borrowing from bc's own manpage
        if [ "$N" -le "1000" ]; then # if N > 1000, parallelize
            bc_code(){
                echo "
  define f(x){
    if (x <= 1) return (1);
    return (f(x-1) * x);
  }
  f(${1})"
            }
 
            F=$(bc_code "$N" | bc)
        else
            # this is not really parallelized but it's 4x faster
            # when using tranches of 1000 (probably because of bc idiosincrasies)
            T=1000
            bc_code(){
                echo "
  define f(x){
    r=1
    i=0
    while (i<${2} && x> 0){
      r *= x
      i += 1
      x -= 1
    }
    return r
  }
  f(${1})"
            }
            while [ "$N" -ge "1" ]; do
                C=$(bc_code "$N" "$T" | bc)
                F=$(echo "$F * $C" | bc)
                N=$(echo "$N - $T" | bc)
            done
        fi # 1000-over
            
        echo "$F"
    fi # 0-20-else
}

if [ -n "$1" ];
then
    # if something is passed as an argument, use that.
    while [ -n "$1" ]; do 
        validate_and_calc "$1"
        shift
    done
else
    # otherwise, wait on the standard input.
    while read -r line; do
        validate_and_calc "$line"
    done
fi