#!/bin/env bash
################################################################################
# shellmath.sh
# Shell functions for floating-point arithmetic using only builtins
#
# Copyright (c) 2020 by Michael Wood. All rights reserved.
#
# Usage:
#
#    source  _thisPath_/_thisFileName_
#
#    # Conventional method: call the APIs by subshelling
#    mySum=$( _shellmath_add 202.895 6.00311 )
#    echo $mySum
#
#    # Optimized method: use hidden globals to simulate more flexible pass-and-return
#    _shellmath_isOptimized=1
#    _shellmath_add 44.2 -87
#    _shellmath_getReturnValue mySum
#    echo $mySum
# 
################################################################################


################################################################################
# Program constants
################################################################################
declare -A -r __shellmath_numericTypes=(
    [INTEGER]=0
    [DECIMAL]=1
)

declare -A -r __shellmath_returnCodes=(
    [SUCCESS]="0:Success"
    [FAIL]="1:General failure"
    [ILLEGAL_NUMBER]="2:Invalid argument; decimal number required: '%s'"
    [DIVIDE_BY_ZERO]="3:Divide by zero error"
)

declare -r -i __shellmath_true=1
declare -r -i __shellmath_false=0

declare __shellmath_SUCCESS  __shellmath_FAIL  __shellmath_ILLEGAL_NUMBER

################################################################################
# Program state
################################################################################
declare __shellmath_isOptimized=${__shellmath_false}
declare __shellmath_didPrecalc=${__shellmath_false}


################################################################################
# Error-handling utilities
################################################################################
function _shellmath_getReturnCode()
{
    local errorName=$1
    return "${__shellmath_returnCodes[$errorName]%%:*}"
}

function _shellmath_warn()
{
    # Generate an error message and return control to the caller
    _shellmath_handleError -r "$@"
    return $?
}

function _shellmath_exit()
{
    # Generate an error message and EXIT THE SCRIPT / interpreter
    _shellmath_handleError "$@"
}

function _shellmath_handleError()
{
    # Hidden option "-r" causes return instead of exit
    local returnDontExit=$__shellmath_false
    if [[ "$1" == "-r" ]]; then
        returnDontExit=${__shellmath_true}
        shift
    fi

    # Format of $1:  returnCode:msgTemplate
    [[ "$1" =~ ^([0-9]+):(.*) ]]
    returnCode=${BASH_REMATCH[1]}
    msgTemplate=${BASH_REMATCH[2]}
    shift
    
    # Display error msg, making parameter substitutions as needed
    msgParameters="$*"
    printf  "$msgTemplate" "${msgParameters[@]}"

    if ((returnDontExit)); then
        return "$returnCode"
    else
        exit "$returnCode"
    fi
}


################################################################################
# precalc()
#
# Pre-calculates certain global data and by setting the global variable
# "__shellmath_didPrecalc" records that this routine has been called. As an
# optimization, the caller should check that global to prevent needless
# invocations.
################################################################################
function _shellmath_precalc()
{
    # Set a few global constants
    _shellmath_getReturnCode SUCCESS; __shellmath_SUCCESS=$?
    _shellmath_getReturnCode FAIL; __shellmath_FAIL=$?
    _shellmath_getReturnCode ILLEGAL_NUMBER; __shellmath_ILLEGAL_NUMBER=$?

    # Determine the decimal precision to which we can accurately calculate.
    # To do this we probe for the threshold at which integers overflow and
    # take the integer floor of that number's base-10 logarithm.
    # We check the 64-bit, 32-bit and 16-bit thresholds only.
    if ((2**63 < 2**63-1)); then
        __shellmath_precision=18
        __shellmath_maxValue=$((2**63-1))
    elif ((2**31 < 2**31-1)); then
        __shellmath_precision=9
        __shellmath_maxValue=$((2**31-1))
    else     ## ((2**15 < 2**15-1))
        __shellmath_precision=4
        __shellmath_maxValue=$((2**15-1))
    fi

    __shellmath_didPrecalc=$__shellmath_true
}


################################################################################
# Simulate pass-and-return by reference using a secret global storage array
################################################################################

declare -a __shellmath_storage

function _shellmath_setReturnValues()
{
    local -i _i

    for ((_i=1; _i<=$#; _i++)); do
        __shellmath_storage[_i]="${!_i}"
    done

    __shellmath_storage[0]=$#
}

function _shellmath_getReturnValues()
{
    local -i _i
    local evalString

    for ((_i=1; _i<=$#; _i++)); do
        evalString+=${!_i}="${__shellmath_storage[_i]}"" "
    done

    eval "$evalString"
}

function _shellmath_setReturnValue() { __shellmath_storage=(1 "$1"); }
function _shellmath_getReturnValue() { eval "$1"=\"${__shellmath_storage[1]}\"; }
function _shellmath_getReturnValueCount() { eval "$1"=\"${__shellmath_storage[0]}\"; }

################################################################################
# validateAndParse(numericString)
# Return Code:      SUCCESS or ILLEGAL_NUMBER
# Return Signature: integerPart fractionalPart isNegative numericType isScientific
#
# Validate and parse arguments to the main arithmetic routines
################################################################################

function _shellmath_validateAndParse()
{
    local n="$1"
    local isNegative=${__shellmath_false}
    local isScientific=${__shellmath_false}
    local numericType returnCode

    ((returnCode = __shellmath_SUCCESS))
    
    # Accept decimals: leading digits (optional), decimal point, trailing digits
    if [[ "$n" =~ ^[-]?([0-9]*)\.([0-9]+)$ ]]; then
        local integerPart=${BASH_REMATCH[1]:-0}
        local fractionalPart=${BASH_REMATCH[2]}

        # Strip superfluous trailing zeros
        if [[ "$fractionalPart" =~ ^(.*[^0])0*$ ]]; then
            fractionalPart=${BASH_REMATCH[1]}
        fi

        numericType=${__shellmath_numericTypes[DECIMAL]}

        # Factor out the negative sign if it is present
        if [[ "$n" =~ ^- ]]; then
            isNegative=${__shellmath_true}
            n=${n:1}
        fi

        _shellmath_setReturnValues "$integerPart" "$fractionalPart" \
                    $isNegative "$numericType" $isScientific
        return "$returnCode"

    # Accept integers
    elif [[ "$n" =~ ^[-]?[0-9]+$ ]]; then
        numericType=${__shellmath_numericTypes[INTEGER]}

        # Factor out the negative sign if it is present
        if [[ "$n" =~ ^- ]]; then
            isNegative=${__shellmath_true}
            n=${n:1}
        fi

        _shellmath_setReturnValues "$n" 0 $isNegative "$numericType" $isScientific
        return "$returnCode"

    # Accept scientific notation: 1e5, 2.44E+10, etc.
    elif [[ "$n" =~ (.*)[Ee](.*) ]]; then
        local significand=${BASH_REMATCH[1]}
        local exponent=${BASH_REMATCH[2]}

        # Validate the significand: optional sign, integer part,
        # optional decimal point and fractional part
        if [[ "$significand" =~ ^[-]?([0-9]+)(\.([0-9]+))?$ ]]; then

            isScientific=${__shellmath_true}

            # Separate the integer and fractional parts
            local sigInteger=${BASH_REMATCH[1]}
            local sigIntLength=${#sigInteger}
            local sigFraction=${BASH_REMATCH[3]}

            # Strip superfluous trailing zeros
            if [[ "$sigFraction" =~ ^(.*[^0])0*$ ]]; then
                sigFraction=${BASH_REMATCH[1]}
            fi

            local sigFracLength=${#sigFraction}

            if [[ "$n" =~ ^- ]]; then
                isNegative=${__shellmath_true}
                n=${n:1}
            fi

            # Rewrite the scientifically-notated number in ordinary decimal notation.
            # IOW, realign the integer and fractional parts. Separate with a space
            # so they can be returned as two separate values
            if ((exponent > 0)); then
                local zeroCount integer fraction
                ((zeroCount = exponent - sigFracLength))
                if ((zeroCount > 0)); then
                    printf -v zeros "%0*d" "$zeroCount" 0
                    n=${sigInteger}${sigFraction}${zeros}" 0"
                    numericType=${__shellmath_numericTypes[INTEGER]}
                elif ((zeroCount < 0)); then
                    n=${sigInteger}${sigFraction:0:exponent}" "${sigFraction:exponent}
                    numericType=${__shellmath_numericTypes[DECIMAL]}
                else
                    n=${sigInteger}${sigFraction}" 0"
                    numericType=${__shellmath_numericTypes[INTEGER]}
                fi
                integer=${n% *}; fraction=${n#* }
                _shellmath_setReturnValues "$integer" "$fraction" $isNegative "$numericType" $isScientific
                return "$returnCode"

            elif ((exponent < 0)); then
                local zeroCount integer fraction
                ((zeroCount = -exponent - sigIntLength))
                if ((zeroCount > 0)); then
                    printf -v zeros "%0*d" "$zeroCount" 0
                    n="0 "${zeros}${sigInteger}${sigFraction}
                    numericType=${__shellmath_numericTypes[DECIMAL]}
                elif ((zeroCount < 0)); then
                    n=${sigInteger:0:-zeroCount}" "${sigInteger:(-zeroCount)}${sigFraction}
                    numericType=${__shellmath_numericTypes[DECIMAL]}
                else
                    n="0 "${sigInteger}${sigFraction}
                    numericType=${__shellmath_numericTypes[DECIMAL]}
                fi
                integer=${n% *}; fraction=${n#* }
                _shellmath_setReturnValues "$integer" "$fraction" $isNegative "$numericType" $isScientific
                return "$returnCode"

            else
                # exponent == 0 means the number is already aligned as desired
                numericType=${__shellmath_numericTypes[DECIMAL]}
                _shellmath_setReturnValues "$sigInteger" "$sigFraction" $isNegative "$numericType" $isScientific
                return "$returnCode"
            fi

        # Reject strings like xxx[Ee]yyy where xxx, yyy are not valid numbers
        else
            ((returnCode = __shellmath_ILLEGAL_NUMBER))
            _shellmath_setReturnValues ""
            return "$returnCode"
        fi

    # Reject everything else
    else
        ((returnCode = __shellmath_ILLEGAL_NUMBER))
        _shellmath_setReturnValues ""
        return "$returnCode"
    fi
}


################################################################################
# numToScientific (integerPart, fractionalPart)
#
# Format conversion utility function
################################################################################
function _shellmath_numToScientific()
{
    local integerPart=$1 fractionalPart=$2
    local exponent head tail scientific

    if ((integerPart > 0)); then
        ((exponent = ${#integerPart}-1))
        head=${integerPart:0:1}
        tail=${integerPart:1}${fractionalPart}
    elif ((integerPart < 0)); then
        ((exponent = ${#integerPart}-2))   # skip "-" and first digit
        head=${integerPart:0:2}
        tail=${integerPart:2}${fractionalPart}
    else
        [[ "$fractionalPart" =~ ^[-]?(0*)([^0])(.*)$ ]]
        exponent=$((-(${#BASH_REMATCH[1]} + 1)))
        head=${BASH_REMATCH[2]}
        tail=${BASH_REMATCH[3]}
    fi

    # Remove trailing zeros
    [[ $tail =~ ^.*[^0] ]]; tail=${BASH_REMATCH[0]:-0}

    printf -v scientific "%d.%de%d" "$head" "$tail" "$exponent"

    _shellmath_setReturnValue "$scientific"
}


################################################################################
# _shellmath_add (addend_1, addend_2)
################################################################################
function _shellmath_add()
{
    local n1="$1"
    local n2="$2"

    if ((! __shellmath_didPrecalc)); then
        _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true
    fi

    local isVerbose=$(( __shellmath_isOptimized == __shellmath_false ))

    # Is the caller itself an arithmetic function?
    local isSubcall=${__shellmath_false}
    local isMultiplication=${__shellmath_false}
    if [[ "${FUNCNAME[1]}" =~ shellmath_(add|subtract|multiply|divide)$ ]]; then
        isSubcall=${__shellmath_true}
        if [[ "${BASH_REMATCH[1]}" == multiply ]]; then
            isMultiplication=${__shellmath_true}
        fi
    fi

    # Handle corner cases where argument count is not 2
    local argCount=$#
    if ((argCount == 0)); then
        echo "Usage: ${FUNCNAME[0]}  addend_1  addend_2"
        return "$__shellmath_SUCCESS"
    elif ((argCount == 1)); then
        # Note the result as-is, print if running "normally", and return
        _shellmath_setReturnValue "$n1"
        (( isVerbose && ! isSubcall )) && echo "$n1"
        return "$__shellmath_SUCCESS"
    elif ((argCount > 2 && !isSubcall)); then
        local recursiveReturn

        # Use a binary recursion tree to add everything up
        # 1) left branch
        _shellmath_add "${@:1:$((argCount/2))}"; recursiveReturn=$?
        _shellmath_getReturnValue n1
        if (( recursiveReturn != __shellmath_SUCCESS )); then
            _shellmath_setReturnValue "$n1"
            return "$recursiveReturn"
        fi
        # 2) right branch
        _shellmath_add "${@:$((argCount/2+1))}"; recursiveReturn=$?
        _shellmath_getReturnValue n2
        if (( recursiveReturn != __shellmath_SUCCESS )); then
            _shellmath_setReturnValue "$n2"
            return "$recursiveReturn"
        fi
        # 3) head node
        local sum
        _shellmath_add "$n1" "$n2"; recursiveReturn=$?
        _shellmath_getReturnValue sum
        _shellmath_setReturnValue "$sum"
        if (( isVerbose && ! isSubcall )); then
            echo "$sum"
        fi
        return "$recursiveReturn"
    fi

    local integerPart1  fractionalPart1  integerPart2  fractionalPart2
    local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2
    local flags

    if ((isMultiplication)); then
        integerPart1="$1"
        fractionalPart1="$2"
        integerPart2="$3"
        fractionalPart2="$4"

        type1=${__shellmath_numericTypes[DECIMAL]}
        type2=${__shellmath_numericTypes[DECIMAL]}
        isNegative1=$__shellmath_false
        isNegative2=$__shellmath_false
        isScientific1=$__shellmath_false
        isScientific2=$__shellmath_false
    else
        # Check and parse the arguments
        _shellmath_validateAndParse "$n1";  flags=$?
        _shellmath_getReturnValues  integerPart1  fractionalPart1  isNegative1  type1  isScientific1
        if ((flags == __shellmath_ILLEGAL_NUMBER)); then
            _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n1"
            return $?
        fi
        _shellmath_validateAndParse "$n2";  flags=$?
        _shellmath_getReturnValues  integerPart2  fractionalPart2  isNegative2  type2  isScientific2
        if ((flags == __shellmath_ILLEGAL_NUMBER)); then
            _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n2"
            return $?
        fi
    fi

    # Quick add & return for integer adds
    if ((type1==type2 && type1==__shellmath_numericTypes[INTEGER])); then
        ((isNegative1)) && ((integerPart1*=-1))
        ((isNegative2)) && ((integerPart2*=-1))
        local sum=$((integerPart1 + integerPart2))
        if (( (!isSubcall) && (isScientific1 || isScientific2) )); then
            _shellmath_numToScientific $sum "" 
            _shellmath_getReturnValue sum
        fi
        _shellmath_setReturnValue $sum
        if (( isVerbose && ! isSubcall )); then
            echo "$sum"
        fi
        return "$__shellmath_SUCCESS"
    fi

    # Right-pad both fractional parts with zeros to the same length
    local fractionalLen1=${#fractionalPart1}
    local fractionalLen2=${#fractionalPart2}
    if ((fractionalLen1 > fractionalLen2)); then
        # Use printf to zero-pad. This avoids mathematical side effects.
        printf -v fractionalPart2 %-*s "$fractionalLen1" "$fractionalPart2"
        fractionalPart2=${fractionalPart2// /0}
    elif ((fractionalLen2 > fractionalLen1)); then
        printf -v fractionalPart1 %-*s "$fractionalLen2" "$fractionalPart1"
        fractionalPart1=${fractionalPart1// /0}
    fi
    local unsignedFracLength=${#fractionalPart1}

    # Implement a sign convention that will enable us to detect carries by
    # comparing string lengths of addends and sums: propagate the sign across
    # both numeric parts (whether unsigned or zero).
    if ((isNegative1)); then
        fractionalPart1="-"$fractionalPart1
        integerPart1="-"$integerPart1
    fi
    if ((isNegative2)); then
        fractionalPart2="-"$fractionalPart2
        integerPart2="-"$integerPart2
    fi

    local integerSum=0
    local fractionalSum=0

    ((integerSum = integerPart1+integerPart2))

    # Summing the fractional parts is tricky: We need to override the shell's
    # default interpretation of leading zeros, but the operator for doing this
    # (the "10#" operator) cannot work directly with negative numbers. So we
    # break it all down.
    if ((isNegative1)); then
        ((fractionalSum += (-1) * 10#${fractionalPart1:1}))
    else
        ((fractionalSum += 10#$fractionalPart1))
    fi
    if ((isNegative2)); then
        ((fractionalSum += (-1) * 10#${fractionalPart2:1}))
    else
        ((fractionalSum += 10#$fractionalPart2))
    fi

    unsignedFracSumLength=${#fractionalSum}
    if [[ "$fractionalSum" =~ ^[-] ]]; then
        ((unsignedFracSumLength--))
    fi

    # Restore any leading zeroes that were lost when adding
    if ((unsignedFracSumLength < unsignedFracLength)); then
        local lengthDiff=$((unsignedFracLength - unsignedFracSumLength))
        local zeroPrefix
        printf -v zeroPrefix "%0*d" "$lengthDiff" 0
        if ((fractionalSum < 0)); then
            fractionalSum="-"${zeroPrefix}${fractionalSum:1}
        else
            fractionalSum=${zeroPrefix}${fractionalSum}
        fi
    fi

    # Carry a digit from fraction to integer if required
    if ((10#$fractionalSum!=0 && unsignedFracSumLength > unsignedFracLength)); then
        local carryAmount
        ((carryAmount = isNegative1?-1:1))
        ((integerSum += carryAmount))
        # Remove the leading 1-digit whether the fraction is + or -
        fractionalSum=${fractionalSum/1/}
    fi

    # Transform the partial sums from additive to concatenative. Example: the
    # pair (-2,3) is not -2.3 but rather (-2)+(0.3), i.e. -1.7 so we want to
    # transform (-2,3) to (-1,7). This transformation is meaningful when
    # the two parts have opposite signs, so that's what we look for.
    if ((integerSum < 0 && 10#$fractionalSum > 0)); then
        ((integerSum += 1))
        ((fractionalSum = 10#$fractionalSum - 10**unsignedFracSumLength))
    elif ((integerSum > 0 && 10#$fractionalSum < 0)); then
        ((integerSum -= 1))
        ((fractionalSum = 10**unsignedFracSumLength + 10#$fractionalSum))
    fi
    # This last case needs to function either as an "else" for the above,
    # or as a coda to the "if" clause when integerSum is -1 initially.
    if ((integerSum == 0 && 10#$fractionalSum < 0)); then
        integerSum="-"$integerSum
        ((fractionalSum *= -1))
    fi

    # Touch up the numbers for display
    local sum
    ((10#$fractionalSum < 0)) && fractionalSum=${fractionalSum:1}
    if (( (!isSubcall) && (isScientific1 || isScientific2) )); then
        _shellmath_numToScientific "$integerSum" "$fractionalSum"
        _shellmath_getReturnValue sum
    elif ((10#$fractionalSum)); then
        printf -v sum "%s.%s" "$integerSum" "$fractionalSum"
    else
        sum=$integerSum
    fi

    # Note the result, print if running "normally", and return
    _shellmath_setReturnValue $sum
    if (( isVerbose && ! isSubcall )); then
        echo "$sum"
    fi

    return "$__shellmath_SUCCESS"
}


################################################################################
# subtract (subtrahend, minuend)
################################################################################
function _shellmath_subtract()
{
    local n1="$1"
    local n2="$2"
    local isVerbose=$(( __shellmath_isOptimized == __shellmath_false ))

    if ((! __shellmath_didPrecalc)); then
        _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true
    fi

    if (( $# == 0 || $# > 2 )); then
        echo "Usage: ${FUNCNAME[0]}  subtrahend  minuend"
        return "$__shellmath_SUCCESS"
    elif (( $# == 1 )); then
        # Note the value as-is and return
        _shellmath_setReturnValue "$n1"
        ((isVerbose)) && echo "$n1"
        return "$__shellmath_SUCCESS"
    fi

    # Symbolically negate the second argument
    if [[ "$n2" =~ ^- ]]; then
        n2=${n2:1}
    else
        n2="-"$n2
    fi

    # Calculate, note the result, print if running "normally", and return
    local difference
    _shellmath_add "$n1" "$n2"
    _shellmath_getReturnValue difference
    if ((isVerbose)); then
        echo "$difference"
    fi

    return $?
}


################################################################################
# reduceOuterPairs (two integer parts [, two fractional parts])
#
# Examines the magnitudes of two numbers in advance of a multiplication
# and either chops off their lowest-order digits or pushes them to the
# corresponding lower-order parts in order to prevent overflow in the product.
# The choice depends on whether 2 or 4 arguments are supplied.
################################################################################
function _shellmath_reduceOuterPairs()
{
    local value1="$1" value2="$2" subvalue1="$3" subvalue2="$4"

    local digitExcess value1Len=${#value1} value2Len=${#value2}
    ((digitExcess = value1Len + value2Len - __shellmath_precision))

    # Be very precise about detecting overflow. The "digit excess" underestimates
    # this: floor(log_10(longLongMax)). We don't want to needlessly lose precision
    # when a product barely squeezes under the exact threshold.
    if ((digitExcess>1 || (digitExcess==1 && value1 > __shellmath_maxValue/value2) )); then

        # Identify the digit-tails to be pruned off and either discarded or
        # pushed past the decimal point. In pruning the two values we want to
        # retain as much "significance" as possible, so we try to equalize the
        # lengths of the remaining digit sequences.
        local tail1 tail2
        local lengthDiff leftOver

        # Which digit string is longer, and by how much?
        ((lengthDiff = value1Len - value2Len))
        if ((lengthDiff > 0)); then
            if ((digitExcess <= lengthDiff)); then
                # Chop digits from the longer string only
                tail1=${value1:(-digitExcess)}
                tail2=""     # do not chop anything
            else
                # Chop more digits from the longer string so the two strings
                # end up as nearly-equal in length as possible
                ((leftOver = digitExcess - lengthDiff))
                tail1=${value1:(-(lengthDiff + leftOver/2))}
                tail2=${value2:(-((leftOver+1)/2))}
            fi
        else
            ((lengthDiff *= -1))
            # Mirror the above code block but swap 1 and 2
            if ((digitExcess <= lengthDiff)); then
                tail1=""
                tail2=${value2:(-digitExcess)}
            else
                ((leftOver = digitExcess - lengthDiff))
                tail1=${value1:(-((leftOver+1)/2))}
                tail2=${value2:(-(lengthDiff + leftOver/2))}
            fi
        fi

        # Discard the least-significant digits or move them past the decimal point
        value1=${value1%${tail1}}
        [[ -n "$subvalue1" ]] && subvalue1=${tail1}${subvalue1%0}  # remove placeholder zero
        value2=${value2%${tail2}}
        [[ -n "$subvalue2" ]] && subvalue2=${tail2}${subvalue2%0}
    else
        # Signal the caller that no rescaling was actually done
        ((digitExcess = 0))
    fi

    _shellmath_setReturnValues "$value1" "$value2" \
                         "$subvalue1" "$subvalue2" "$digitExcess"
}

################################################################################
# rescaleValue(value, rescaleFactor)
#
# Upscales a decimal value by "factor" orders of magnitude:  3.14159 --> 3141.59
################################################################################
function _shellmath_rescaleValue()
{
    local value="$1" rescalingFactor="$2"
    local head tail zeroCount zeroTail

    [[ "$value" =~ ^(.*)\.(.*)$ ]]
    head=${BASH_REMATCH[1]}
    tail=${BASH_REMATCH[2]}
    ((zeroCount = rescalingFactor - ${#tail}))
    if ((zeroCount > 0)); then
        printf -v zeroTail "%0*d" "$zeroCount" 0
        value=${head}${tail}${zeroTail}
    elif ((zeroCount < 0)); then
        value=${head}${tail:0:rescalingFactor}"."${tail:rescalingFactor}
    else
        value=${head}${tail}
    fi

    _shellmath_setReturnValue "$value"
}

################################################################################
# reduceCrossPairs (two integer parts, two fractional parts)
#
# Examines the precision of the inner products (of "multiplication by parts")
# and if necessary truncates the fractional part(s) to prevent overflow
################################################################################
function _shellmath_reduceCrossPairs()
{
    local value1="$1" value2="$2" subvalue1="$3" subvalue2="$4"

    local digitExcess value1Len=${#value1} value2Len=${#value2}
    local subvalue1Len=${#subvalue1} subvalue2Len=${#subvalue2}

    # Check BOTH cross-products
    ((digitExcess = value1Len + subvalue2Len - __shellmath_precision))
    if ((digitExcess > 1 || (digitExcess==1 && value1 > __shellmath_maxValue/subvalue2) )); then
        subvalue2=${subvalue2:0:(-digitExcess)}
    fi
    ((digitExcess = value2Len + subvalue1Len - __shellmath_precision))
    if ((digitExcess > 1 || (digitExcess==1 && value2 > __shellmath_maxValue/subvalue1) )); then
        subvalue1=${subvalue1:0:(-digitExcess)}
    fi

    _shellmath_setReturnValues "$subvalue1" "$subvalue2"
}


function _shellmath_round()
{
    local number="$1" digitCount="$2"
    local nextDigit=${number:digitCount:1}

    number=${number:0:digitCount}
    if ((nextDigit >= 5)); then
        printf -v number "%0*d" "$digitCount" $((10#$number + 1))
    fi

    _shellmath_setReturnValue "$number"
}

################################################################################
# multiply (multiplicand, multiplier)
################################################################################
function _shellmath_multiply()
{
    local n1="$1"
    local n2="$2"

    if ((! __shellmath_didPrecalc)); then
        _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true
    fi

    local isVerbose=$(( __shellmath_isOptimized == __shellmath_false ))

    # Is the caller itself an arithmetic function?
    local isSubcall=${__shellmath_false}
    if [[ "${FUNCNAME[1]}" =~ shellmath_(add|subtract|multiply|divide)$ ]]; then
        isSubcall=${__shellmath_true}
    fi

    # Handle corner cases where argument count is not 2
    local argCount=$#
    if ((argCount == 0)); then
        echo "Usage: ${FUNCNAME[0]}  factor_1  factor_2"
        return "$__shellmath_SUCCESS"
    elif ((argCount == 1)); then
        # Note the value as-is and return
        _shellmath_setReturnValue "$n1"
        (( isVerbose && ! isSubcall )) && echo "$n1"
        return "$__shellmath_SUCCESS"
    elif ((argCount > 2)); then
        local recursiveReturn

        # Use a binary recursion tree to multiply everything out
        # 1) left branch
        _shellmath_multiply "${@:1:$((argCount/2))}"; recursiveReturn=$?
        _shellmath_getReturnValue n1
        if (( recursiveReturn != __shellmath_SUCCESS )); then
            _shellmath_setReturnValue "$n1"
            return "$recursiveReturn"
        fi
        # 2) right branch
        _shellmath_multiply "${@:$((argCount/2+1))}"; recursiveReturn=$?
        _shellmath_getReturnValue n2
        if (( recursiveReturn != __shellmath_SUCCESS )); then
            _shellmath_setReturnValue "$n2"
            return "$recursiveReturn"
        fi
        # 3) head node
        local product
        _shellmath_multiply "$n1" "$n2"; recursiveReturn=$?
        _shellmath_getReturnValue product
        _shellmath_setReturnValue "$product"
        if (( isVerbose && ! isSubcall )); then
            echo "$product"
        fi
        return "$recursiveReturn"
    fi

    local integerPart1  fractionalPart1  integerPart2  fractionalPart2
    local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2
    local flags

    # Check and parse the arguments
    _shellmath_validateAndParse "$n1";  flags=$?
    _shellmath_getReturnValues  integerPart1  fractionalPart1  isNegative1  type1  isScientific1
    if ((flags == __shellmath_ILLEGAL_NUMBER)); then
        _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n1"
        return $?
    fi
    _shellmath_validateAndParse "$n2";  flags=$?
    _shellmath_getReturnValues  integerPart2  fractionalPart2  isNegative2  type2  isScientific2
    if ((flags == __shellmath_ILLEGAL_NUMBER)); then
        _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n2"
        return $?
    fi

    # Overflow / underflow detection and accommodation
    local rescalingFactor=0
    if ((${#integerPart1} + ${#integerPart2} + ${#fractionalPart1} + ${#fractionalPart2} >= ${__shellmath_precision})); then
        _shellmath_reduceOuterPairs "$integerPart1" "$integerPart2" "$fractionalPart1" "$fractionalPart2"
        _shellmath_getReturnValues integerPart1 integerPart2 fractionalPart1 fractionalPart2 rescalingFactor
        if ((10#$fractionalPart1)); then type1=${__shellmath_numericTypes[DECIMAL]}; fi
        if ((10#$fractionalPart2)); then type2=${__shellmath_numericTypes[DECIMAL]}; fi

        _shellmath_reduceCrossPairs "$integerPart1" "$integerPart2" "$fractionalPart1" "$fractionalPart2"
        _shellmath_getReturnValues fractionalPart1 fractionalPart2

        _shellmath_reduceOuterPairs "$fractionalPart1" "$fractionalPart2"
        _shellmath_getReturnValues fractionalPart1 fractionalPart2
    fi

    # Quick multiply & return for integer multiplies
    if ((type1==type2 && type1==__shellmath_numericTypes[INTEGER])); then
        ((isNegative1)) && ((integerPart1*=-1))
        ((isNegative2)) && ((integerPart2*=-1))
        local product=$((integerPart1 * integerPart2))
        if ((rescalingFactor > 0)); then
            _shellmath_rescaleValue "$product" "$rescalingFactor"
            _shellmath_getReturnValue product
        fi
        if (( (!isSubcall) && (isScientific1 || isScientific2) )); then
            _shellmath_numToScientific $product "" 
            _shellmath_getReturnValue product
        fi
        _shellmath_setReturnValue $product
        if (( isVerbose && ! isSubcall )); then
            echo "$product"
        fi
        return "$__shellmath_SUCCESS"
    fi

    # The product has four components per the distributive law
    local intProduct floatProduct innerProduct1 innerProduct2
    # Widths of the decimal parts
    local floatWidth fractionalWidth1 fractionalWidth2

    # Compute the integer and floating-point components
    ((intProduct = integerPart1 * integerPart2))

    fractionalWidth1=${#fractionalPart1}
    fractionalWidth2=${#fractionalPart2}
    ((floatWidth = fractionalWidth1 + fractionalWidth2))
    ((floatProduct = 10#$fractionalPart1 * 10#$fractionalPart2))
    if ((${#floatProduct} < floatWidth)); then
        printf -v floatProduct "%0*d" "$floatWidth" "$floatProduct"
    fi

    # Compute the inner products: First integer-multiply, then rescale
    ((innerProduct1 = integerPart1 * 10#$fractionalPart2))
    ((innerProduct2 = integerPart2 * 10#$fractionalPart1))

    # Rescale the inner products back to decimals so we can shellmath_add() them
    if ((fractionalWidth2 <= ${#innerProduct1})); then
        local innerInt1=${innerProduct1:0:(-$fractionalWidth2)}
        local innerFloat1=${innerProduct1:(-$fractionalWidth2)}
        integerPart1=${innerInt1}
        fractionalPart1=${innerFloat1}
    else
        integerPart1=0
        printf -v fractionalPart1 "%0*d" "$fractionalWidth2" "$innerProduct1"
    fi
    if ((fractionalWidth1 <= ${#innerProduct2})); then
        local innerInt2=${innerProduct2:0:(-$fractionalWidth1)}
        local innerFloat2=${innerProduct2:(-$fractionalWidth1)}
        integerPart2=${innerInt2}
        fractionalPart2=${innerFloat2}
    else
        integerPart2=0
        printf -v fractionalPart2 "%0*d" "$fractionalWidth1" "$innerProduct2"
    fi

    # Combine the distributed parts
    local innerSum product
    # Add the inner products to get the inner sum
    _shellmath_add  "$integerPart1" "$fractionalPart1" "$integerPart2" "$fractionalPart2"
    _shellmath_getReturnValue innerSum
    [[ "$innerSum" =~ (.*)\.(.*) ]]
    integerPart1=${BASH_REMATCH[1]}
    fractionalPart1=${BASH_REMATCH[2]}
    # Add inner sum + outer sum
    _shellmath_add "$integerPart1" "$fractionalPart1" "$intProduct" "$floatProduct"
    _shellmath_getReturnValue product

    # Determine the sign of the product
    if ((isNegative1 != isNegative2)); then
        product="-"$product
    fi

    # When we pre-detect overflow in the integer part of the computation,
    # we compensate by shrinking the inputs by some order of magnitude.
    # Having now finished the computation, we revert to the original magnitude.
    if ((rescalingFactor > 0)); then
        _shellmath_rescaleValue "$product" "$rescalingFactor"
        _shellmath_getReturnValue product
    fi

    # Convert to scientific notation if appropriate
    if (( (!isSubcall) && (isScientific1 || isScientific2) )); then
        _shellmath_numToScientific "${product%.*}" "${product#*.}"
        _shellmath_getReturnValue product
    fi

    # Note the result, print if running "normally", and return
    _shellmath_setReturnValue $product
    if (( isVerbose && ! isSubcall )); then
        echo "$product"
    fi

    return "$__shellmath_SUCCESS"
}


################################################################################
# divide (dividend, divisor)
################################################################################
function _shellmath_divide()
{
    local n1="$1"
    local n2="$2"
    local integerPart1  fractionalPart1  integerPart2  fractionalPart2
    local isNegative1 type1 isScientific1 isNegative2 type2 isScientific2

    if ((! __shellmath_didPrecalc)); then
        _shellmath_precalc; __shellmath_didPrecalc=$__shellmath_true
    fi

    local isVerbose=$(( __shellmath_isOptimized == __shellmath_false ))

    local isTesting=${__shellmath_false}
    if [[ "${FUNCNAME[1]}" == "_shellmath_assert_functionReturn" ]]; then
        isTesting=${__shellmath_true}
    fi

    if [[ $# -eq 0 || $# -gt 2 ]]; then
        echo "Usage: ${FUNCNAME[0]}  dividend  divisor"
        return "$__shellmath_SUCCESS"
    elif [[ $# -eq 1 ]]; then
        # Note the value as-is and return
        _shellmath_setReturnValue "$n1"
        ((isVerbose)) && echo "$n1"
        return "$__shellmath_SUCCESS"
    fi

    # Check and parse the arguments
    local flags
    _shellmath_validateAndParse "$n1";  flags=$?
    _shellmath_getReturnValues  integerPart1  fractionalPart1  isNegative1  type1  isScientific1
    if ((flags == __shellmath_ILLEGAL_NUMBER)); then
        _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n1"
        return $?
    fi
    _shellmath_validateAndParse "$n2";  flags=$?
    _shellmath_getReturnValues  integerPart2  fractionalPart2  isNegative2  type2  isScientific2
    if ((flags == __shellmath_ILLEGAL_NUMBER)); then
        _shellmath_warn  "${__shellmath_returnCodes[ILLEGAL_NUMBER]}"  "$n2"
        return $?
    fi

    # Throw error on divide by zero
    if ((integerPart2 == 0 && 10#$fractionalPart2 == 0)); then
        _shellmath_warn  "${__shellmath_returnCodes[DIVIDE_BY_ZERO]}"  "$n2"
        return $?
    fi

    # Convert the division problem to an *integer* division problem by rescaling
    # both inputs so as to lose their decimal points. To obtain maximal precision,
    # we scale up the numerator further, padding with as many zeros as it can hold
    local numerator denominator quotient
    local rescaleFactor zeroCount zeroTail

    if ((integerPart1 == 0)); then
        integerPart1=""
    fi
    ((zeroCount = __shellmath_precision - ${#integerPart1} - ${#fractionalPart1}))
    ((rescaleFactor = __shellmath_precision - ${#integerPart1} - ${#fractionalPart2}))
    if ((zeroCount > 0)); then
        printf -v zeroTail "%0*d" "$zeroCount" 0
    fi

    # Rescale and rewrite the fraction to be computed, and compute it
    numerator=${integerPart1}${fractionalPart1}${zeroTail}
    denominator=${integerPart2}${fractionalPart2}
    ((quotient = 10#$numerator / 10#$denominator))

    # For greater precision, re-divide by the remainder to get the next digits of the quotient
    local remainder quotient_2
    ((remainder = 10#$numerator % 10#$denominator))   # cannot exceed numerator or thus, maxValue
    ((zeroCount = __shellmath_precision - ${#remainder}))
    if ((zeroCount > 0)); then
        printf -v zeroTail "%0*d" "$zeroCount" 0
    else
        zeroTail=""
    fi
    # Derive the new numerator from the remainder. Do not change the denominator.
    numerator=${remainder}${zeroTail}
    ((quotient_2 = 10#$numerator / 10#$denominator))
    quotient=${quotient}${quotient_2}
    ((rescaleFactor += ${#quotient_2}))

    # Rescale back. For aesthetic reasons we also round off at the "precision"th decimal place
    ((zeroCount = rescaleFactor - ${#quotient}))
    if ((zeroCount >= 0)); then
        local zeroPrefix="" fractionalPart
        if ((zeroCount > 0)); then
            printf -v zeroPrefix "%0*d" "$((rescaleFactor - ${#quotient}))" 0
        fi
        fractionalPart=${zeroPrefix}${quotient}
        _shellmath_round "$fractionalPart" $__shellmath_precision
        _shellmath_getReturnValue fractionalPart
        quotient="0."${fractionalPart}
    else
        fractionalPart=${quotient:(-$rescaleFactor)}
        _shellmath_round "$fractionalPart" $__shellmath_precision
        _shellmath_getReturnValue fractionalPart
        quotient=${quotient:0:(-$rescaleFactor)}"."${fractionalPart}
    fi

    # Determine the sign of the quotient
    if ((isNegative1 != isNegative2)); then
        quotient="-"$quotient
    fi

    if ((isTesting)); then
        # Trim zeros. (Requires decimal point and zero tail.)
        if [[ "$quotient" =~ [\.].*0$ ]]; then
            # If the decimal point IMMEDIATELY precedes the 0s, remove that too
            [[ $quotient =~ [\.]?0+$ ]]
            quotient=${quotient%${BASH_REMATCH[0]}}
        fi
    fi

    # Convert to scientific notation if appropriate
    if ((isScientific1 || isScientific2)); then
        _shellmath_numToScientific "${quotient%.*}" "${quotient#*.}"
        _shellmath_getReturnValue quotient
    fi

    # Note the result, print if running "normally", and return
    _shellmath_setReturnValue "$quotient"
    if ((isVerbose)); then
        echo "$quotient"
    fi

    return "$__shellmath_SUCCESS"
}