Tricky shell arithmetic

[MochiMoppel]

Inspired by amigo's IQ4sh project but unable to dissect its code I decided to try my luck and roll my own script from scratch, limited to multiplication.

Goal: Floating point multiplication for factors of arbitrary length, coded with nothing but POSIX compatible shell built-ins and constructs.
Obstacles: shell arithmetic, e.g $((2*5)), allows only integers and is restricted to values <=9223372036854775807
Purpose: Well...hmmmm. Let's say curiosity. It's like performing heart surgery with nothing but a Swiss army knife. Fun for the doctor, no advantage for the patient.

I figured that by simulating paper-and-pencil multiplication, which is simple and knows no value restrictions, I could eventually achieve my goal. Floats would have to be stripped of their fraction points to make them digestible for the shell and finally the point would have to be reinserted into what technically is a text string.

The following code was my first shot, still very bare bone and still restricted, but functional and - I hope - easy to understand (consecutive versions would eliminate the restrictions but are more complex and may blur the basic concept). It's written for busybox ash, making it decently fast.

Restrictions:
- One of the 2 factors may be of any length, the other should not exceed 17 digits. That's already sufficient for most real life calculations
- Multiple factors not supported
- No syntax checking
- No scaling to a user defined precision
- No rounding

Usage: <scriptname> num1 num2

Examples (assuming that the script was named "m" - can't think of a shorter name ):

Code: Select all

# m 2 3                                                                   
6
# m 2 0.03
0.06
# m 9.22337203685477580792233720368547758079223372036854775807  0.92233720368547758
8.5070591730234615791340362699272532179134036269927253217828333035262490706

Script:

Code: Select all

#!/bin/ash

# Bare bone floating point multiplication, using only POSIX compatible shell builtins and constructs
# Usage from command line: <scriptname> num1 num2
# Restrictions: Only 2 arguments allowed; one may be of any length, the other should be <= 17 digits

mmul() {
    a=$1    #1st argument
    b=$2    #2nd argument

    ## Determine sign of end result
    case $a$b in
        *-*-*)sign=  ;;
          *-*)sign=- ;;
    esac

    ## Strip any signs
    a=${a#[+-]}
    b=${b#[+-]}

    ## If 1st argument contains fractions ...
    case $a in *.* )
        frca=${a#*.}                #extract fraction portion
        fcnt=${#frca}               #count fraction digits
        a=${a%.*}$frca ;;           #remove '.'
    esac

    ## If 2nd argument contains fractions ...
    case $b in *.* )
        frcb=${b#*.}
        fcnt=$((fcnt+${#frcb}))     #add to fcnt of $a
        b=${b%.*}$frcb ;;
    esac

    ## Remove any leading zeros (avoids octal interpretation)
    a=${a#${a%%[!0]*}}
    b=${b#${b%%[!0]*}}

    ## Let the longest factor be $a
    [ ${#b} -gt ${#a} ] && c=$a a=$b b=$c

    ## Perform digit-wise multiplication 
    while [ $a ] ;do                #while loop will chop off digit after digit from $a until $a is empty
        m=$((${a#${a%?}}*b+cov))    #multiply last digit of $a with factor $b and add any remainder carried over from previous multiplication
        res=$((m%10))$res           #prepend last digit of m to accumulated result
        cov=$((m/10))               #carry-over for next loop: all digits of m except last. Returns '0' for single digit result.
        a=${a%?}                    #cut last digit of $a
    done
    res=${cov#0}$res                #prepend any remaining carry-over value if not 0

    ## If both input arguments were integers, it's done!
    [ -z $fcnt ] && echo ${sign}${res} && return

    ## If at least one of the input arguments was floating point number ...
    while [ $fcnt -gt ${#res} ];do  #pad with leading zeros if result has not enough digits to return fraction part (happens if argument 0.0<whatever> e.g. 2*0.002  (fcnt=3) => res 4 => must be padded to 004
        res=0$res                        
    done

    ## Split the result $res (still a pure integer) into digits before and after fraction point
    int=$res
    c=0
    while [ $c -lt $fcnt ];do       #chop off characters from right (fraction part) until only integer part remains
        int=${int%?}
        c=$((c+1))
    done
    frac=${res#$int}                #fraction part
    echo ${sign}${int:-0}.${frac}   #return result
}
mmul $@

[stemsee]

Examples (assuming that the script was named "m" - can't think of a shorter name ):

/eh/ is shorter than /ehm/ also when pronounced. /i/ , the first sound of 'in' is even shorter!

[MochiMoppel]

For the record here the pizza with everything. All previously mentioned restrictions removed.
The script contains 3 functions and a trailing command that calls the main function mmul. Removing the command allows the functions to be sourced in other scripts.

Display format is similar to bc, syntax is similar to iq.
The -s option cuts the result to a specific scale (like bc or iq), the -S options rounds the result.

Usage examples:

Code: Select all

#  m 2.3 -3.9 0.02                          #multiple arguments
-0.1794

# m      2.3  -3.99999999999999999999999999 #unscaled result
-9.199999999999999999999999977

#  m -s3 2.3  -3.99999999999999999999999999 #result cut to 3 digits
-9.199

#  m -S3 2.3  -3.99999999999999999999999999 #result rounded to 3 digits
-9.200

#  m 2.388888888888888888888888888  -3.99999999999999999999999999 #argument of arbitrary length
-9.55555555555555555555555552811111111111111111111111112

Script:

Code: Select all

#!/bin/ash
add_int() { #expects 2 positive integers of arbitrary length
    a=$1 b=$2 res= rrr=  cov=
    qmrks=??????????????????

    ## Let the longest argument be $a
    [ ${#b} -gt ${#a} ] && c=$a a=$b b=$c
    ## Make $b same length as $a
    while [ ${#b} -lt ${#a}  ];do
        b=0$b
    done
    ## Add max 18 digit chunks of a and b and aggregate results (rrr) into end result (res) 
    while [ $a ] ;do
        if [ ${#a} -gt 18  ];then
            rrr=$(( 1${a#${a%$qmrks}} + 1${b#${b%$qmrks}} + cov  )) #prepend '1' to avoid octal trap 
            cov=$(( ${rrr%$qmrks} - 2 ))
            res=${rrr#${rrr%$qmrks}}$res
            a=${a%$qmrks}
            b=${b%$qmrks}
        else                                    #after looping through chunks code may jump here to finish any remaining <=18 portion
            rrr=$(( 1$a + 1$b + cov ))
            cov=$(( ${rrr%%${rrr#?}} - 2 ))     #deduct 2 from first digit of rrr
            res=${cov#0}${rrr#?}$res            #prepend carry-over if not 0
            break
        fi
    done
    echo $res
}
test_validity() {
    while [ $1 ] ;do
        case $1 in
          *.*.*) echo "Invalid argument in function mmul: \"$1\" (multiple points)" ; return 1 ;;
        *?[+-]*) echo "Invalid argument in function mmul: \"$1\" (sign not preceding number or multiple signs)" ; return 1 ;;
           [+-]) echo "Invalid argument in function mmul: \"$1\" (missing number after sign)" ; return 1 ;;
    *[!0-9.+-]*) echo "Invalid argument in function mmul: \"$1\" (only digits, +/- sign and period allowed)" ; return 1 ;;
        esac
        shift
    done
}
mmul() {
    a= aa= b= bb= abcnt= c= fcnt= frac= int= res= mayround= roundme= scale= sign= tmp=

    ## Read scale value (if any)
    case $1 in
        -s?*) scale=${1#-s} ; shift;;
        -S?*) scale=${1#-S} mayround=y; shift;;
    esac

    ## Test input for syntax errors
    case $scale in *[!0-9]*) echo "Invalid scale in mmul: -s$scale" ; return 1 ;; esac
    [ -z $2 ] && echo "Usage: ${0##*/} [Options]  [+|-]num1 [+|-]num2 [[+|-]num3 ..]
Options:
-s<num> scale result to <num> fractional digits
-S<num> same as -s but round up as needed" && return 1
    test_validity $@ ||  return 1   #abort mmul if input check fails

    ## Process pair of 2 arguments 
    while [ $2 ];do
        res=$sign$res   #$sign$res is empty on startup; if more than 2 args passed it contains result of arg1*arg2, with arg3 now beeing $2
        a=${res:-$1}
        b=$2
        res=            #res must be emptied after assigning (aggregated) result to $a
        cov= zeros= frac= fcnt=0

        ## Determine sign of end result
        case $a$b in
            *-*-*)sign=  ;;
              *-*)sign=- ;;
        esac

        ## Strip all signs
        a=${a#[+-]}
        b=${b#[+-]}

        ## If input values contain fractions ...
        case $a in *.* )
            a=${a%${a##*[!0]}}          #trim trailing zeros
            frca=${a#*.}                #fraction portion
            fcnt=${#frca}               #count fraction digits
            a=${a%.*}$frca ;;           #remove '.'
        esac
        case $b in *.* )
            b=${b%${b##*[!0]}}
            frcb=${b#*.}
            fcnt=$((fcnt+${#frcb}))     #add to fcnt of $a
            b=${b%.*}$frcb ;;
        esac
        ## Remove any leading zeros (avoids octal interpretation)
        a=${a#${a%%[!0]*}}
        b=${b#${b%%[!0]*}}

        ## Prepare multiplication
        abcnt=$(( ${#a} + ${#b} ))          #number of digits in $a$b
        [ $abcnt -gt 18 ] && [ ${#b} -gt ${#a} ] && c=$a a=$b b=$c  # let the longest factor be $a

        ## CASE A: combined length of factors <=18 digits: Simple shell multiplication
        if [ $abcnt -le 18 ] ;then res=$((a*b))

        ## CASE B: 1st factor any length , 2nd factor <= 17 digits : Digit-wise multiplication
        elif [ ${#b} -le 17 ];then
            while [ $a ] ;do
                m=$((${a#${a%?}}*b+cov))    #multiply last digit of $a with factor $b and add any remainder to be carried over from previous multiplication
                res=$((m%10))$res           #last digit of m prepended to accumulated result
                cov=$((m/10))               #carry-over for next loop: all digits of m except last. Returns '0' for single digit result.
                a=${a%?}                    #cut last digit
            done
            res=${cov#0}$res                #prepend any remaining carry-over value if not 0

        ## CASE C: each factor > 17 digits: requires 'add_int'
        else
            while [ $b ] ;do                    #chop off 17digit chunks from $b until empty.
                bb=${b#${b%?????????????????}}  #last 17 digits of $b
                bb=${bb:-$b}                    #on final loop remaining $b may be < 17 digits, resulting in empty $bb when evaluatng 'bb=${b#${b%?????????????????}}'. Still the remaining part of $b has to be processed, hence assigning bb to b
                b=${b%$bb}                      #on final loop $b becomes empty 
                bb=${bb#${bb%%[!0]*}}           #trim leading zeros
                aa=$a cov=0 rrr=                #initialize 'while' loop
                while [ $aa ] ;do               #multiply each digit of $aa with $b until $aa empty
                    m=$((${aa#${aa%?}}*bb+cov)) #multiply last digit of $aa with factor $bb (any leading zeros removed to avoid octal interpretation) and add any remainder to be carried over from previous multiplication; Adding cov could push 18digit chunk over the edge to 19 hence chunk limit 17 
                    rrr=$((m%10))$rrr           #last digit of m prepended to accumulated result
                    cov=$((m/10))               #all digits of m except last. Returns '0' for single digit result.
                    aa=${aa%?}                  #cut last digit
                done
                rrr=${cov#0}${rrr}$zeros        #prepend any remaining carry-over value if not 0
                zeros=${zeros}00000000000000000 #increase zeros with each run
                if [ $res ] ;then               #$res exists only after 2nd loop, i.e. after 1st loop it would make no sense to run slow 'add 0 $rrr'
                    res=$(add_int $rrr $res)    #add current result to total result
                else
                    res=$rrr                    #assign $rrr to $res after 1st loop
                fi
            done
        fi

        #Final result will be integer
        [ $fcnt -eq 0 ] && int=$res && shift && continue

        #Final (unscaled) result will have fraction
        while [ $fcnt -gt ${#res} ];do      #pad with leading zeros if res has not enough digits to return fraction part (happens if argument 0.0<whatever> e.g. 0.002*2  (fcnt=3) => res 4 => must be padded to 004
        res=0$res
        done

        int=$res
        c=0
        while [ $c -lt $fcnt ];do           #chop off characters from right (fraction part) until only integer part remains
        int=${int%?}
         c=$((c+1))
        done
        frac=${res#$int}                    #fraction part
        res=$int.$frac                      #$res only needed for next loop (if any)
        shift                               #next argument. If none then while loop ends
    done                                    #while [ "$2" ]

    #########################################################
    # Loop ended. Now format $int and $frac into final result
    #########################################################
        
    #𝗡𝗼 𝘀𝗰𝗮𝗹𝗶𝗻𝗴
    [ -z $scale ] && echo ${sign}${int:-0}${frac:+.}${frac} && return

    #𝗡𝗲𝗲𝗱𝘀 𝘀𝗰𝗮𝗹𝗶𝗻𝗴
    while [ ${#frac} -gt $((scale)) ]; do   # scale down
        [ ${#frac} -eq $((scale+1)) ] && [ ${frac#${frac%?}} -ge 5 ] && roundme=${mayround:+y} #if ${#frac} reached scale+1 :  Examine last digit. Will determine if  result has to be rounded up
        frac=${frac%?}
    done
    while [ ${#frac} -lt $((scale)) ]; do   #scale up by padding with trailing zeros
        frac=${frac}0
    done

    #𝗡𝗼 𝗿𝗼𝘂𝗻𝗱𝗶𝗻𝗴
    [ -z $roundme ] && echo ${sign}${int:-0}${frac:+.}${frac} && return

    #𝗡𝗲𝗲𝗱𝘀 𝗿𝗼𝘂𝗻𝗱𝗶𝗻𝗴
    res=$(add_int $int$frac 1)   #round up by adding 1
    int=$res
    c=0
    while [ $c -lt ${#frac} ];do    #(re)determine int (may have changed due to rounding)
        int=${int%?}
        c=$((c+1))
    done
    frac=${res#$int}
    echo ${sign}${int:-0}${frac:+.}${frac}
}
mmul $@

[geo_c]

IPurpose: Well...hmmmm. Let's say curiosity. It's like performing heart surgery with nothing but a Swiss army knife. Fun for the doctor, no advantage for the patient.

It's why I do a lot of things, just because I think I can, and I want to test that hypothesis. The floating point math idea I see mentioned in regards to audio algorithms. I don't know what languages are used to actually design the binaries, but I kind of doubt it's scripting language. That's all beyond my current grasp.

Not to go off topic too much, but I was wondering if you know anything about Fractal equations. I've often tried to apply 'fractal thinking' to music composition, and I've gotten some really good results. But my intervalic, or rhythmic fractal formulas, are somewhat arbitrarily conceived, and not truly fractal in the mathematical sense.

So I was thinking, being that a fractal equation can be plotted on an a x-y coordinate, as best I understand, how on earth does one arrive at an equation that branches 'fractally?' I'm completely lost on it. But of course, I ditched math after Trigonometry. So I never even looked at calculus.