“Floating Point” Math

Tuesday, 6th December 2022

I’ve always been interested in what is the most ridiculous way I could build a 3D engine. For example, the first one I built was based off of the work done here except that I implemented it in TI-BASIC instead of Z80 Assembly (unfortunately that calculator – and by extension the code – has been lost to time). It ran at roughly a frame per 5 seconds but you could walk around a very simple level and even play a deathmatch against a friend with the link cable. However, now that I write code for a living and have graduated somewhat from my TI-BASIC days, I figured I would choose a more “appropriate” language to write an engine in. So, naturally, I turned to Bash.

As a side note, the name of the project “Bash and Tear” is a play on the phrase from the new Doom games (Doom (2016) and Doom Eternal) “Rip and Tear”

The first challenge I ran into was the lack of floating point arithmetic in Bash. There are ways around this with external tools (for example bc) but I decided to roll my own solution since that’s more fun.

To do this, we have to have some ability to parse a string representation of a decimal number and convert it to an integer format which Bash can then handle. To this end, I wrote this function:

function float.parse {
    local num
    local parts
    local int
    local frac
    local output
    local sign

    num="$1"

    # check to see if it's a negative number, remove the negative sign if so
    if [[ "${num:0:1}" == "-" ]]; then
        sign="-"
        num="${num:1}"
    fi

    # get integer and fractional parts
    parts=(${num//./ })
    int="${parts[0]}"
    frac="${parts[1]}"

    # expand the fraction out to our desired precision
    while [[ "${#frac}" < "${FLOAT_PRECISION}" ]]; do
        frac="${frac}0"
    done

    output="${int}${frac}"

    # trim leading "0"s from the output
    while [[ "${output:0:1}" == "0" ]]; do
        output="${output:1}"
    done

    # if it was all "0"s, then we should return "0" with no sign
    if [[ "${output}" == "" ]]; then
        output="0"
        sign=""
    fi
    
    # return the output with the sign we saved from earlier
    echo "${sign}${output}"
}

With the FLOAT_PRECISION variable set to 8, we can use this function like so:

$ float.parse "-10.0"
  -1000000000

Great, so now we have the ability to take a float written out and convert it to an integer representation. What about if we want to print the number, however? Or have it stored as its float representation instead of passing ints around everywhere? For that, we’ll need a format function:

function float.format {
    local num
    local int
    local frac
    local length
    local int_length
    local sign

    num="$1"
    sign=""

    # check to see if it's a negative number and store the sign, removing it from the number
    if [[ "${num:0:1}" == "-" ]]; then
        sign="-"
        num="${num:1}"
    fi

    # how many characters is the integer
    length="${#num}"

    if (( length <= FLOAT_PRECISION )); then
        # if we're less than our precision value then it's entirely the mantissa
        int="0"
        frac="${num}"
        # pad with "0"s to get to the right length
        while [[ "${#frac}" < "${FLOAT_PRECISION}" ]]; do
            frac="0${frac}"
        done
    else
        # if we're greater than our precision value then we have an integer part
        int_length=$((length - FLOAT_PRECISION))
        int="${num:0:$int_length}"
        frac="${num:int_length}"
    fi

    # format all the parts and return it
    echo "${sign}${int}.${frac}"
}

This can be used like:

$ float.format "-1000000000"
  -10.00000000

Cool. We’re well on our way with the ability to standardize the representation of floats. Now we just need basic mathematical operations. To this end, we’ll look at addition and subtraction together.

function float.add {
    local a
    local b
    local total

    a="$(float.parse "$1")"
    b="$(float.parse "$2")"

    total=$((a + b))

    echo "$(float.format "${total}")"
}

function float.subtract {
    local a
    local b
    local total

    a="$(float.parse "$1")"
    b="$(float.parse "$2")"

    total=$((a - b))

    echo "$(float.format "${total}")"
}

For both of these functions we take the approach of “take in arguments, convert them from float representation to ints, perform operation on ints, convert back to float representation”.

Multiplication follows the same principal, however we also have to remove the last 8 digits to keep the number within the precision we’re looking for. So as a result, the multiplication function looks like:

function float.multiply {
    local a
    local b
    local total
    local precision

    precision=0
    total=0

    a="$(float.parse "$1")"
    b="$(float.parse "$2")"

    total=$((a * b))
    
    # remove extra precision that comes from having to use integers for the operation
    local length
    length="${#total}"
    length=$((length - FLOAT_PRECISION))
    total="${total:0:length}"

    echo "$(float.format "${total}")"
}

We’re able to now use the functions as shown below:

$ float.add "10.0" "2.5"
  12.50000000
$ float.subtract "10.0" "2.5"
  7.50000000
$ float.multiply "10.0" "2.5"
  25.00000000

Division is where it gets tough. If we want to use our integer representations we have three options:

1. Perform the integer division as normal, which will result in a truncated output that we then have to multiply by our precision scaling factor.
2. Divide one integer by the other scaled down by the float precision. This gives us a value with the correct fractional precision but it’s not as accurate as we might like
3. Roll our own division function to get the correct answer

(1) has problems in that we’ll need slopes less than 1 when drawing lines, so it’s not a viable candidate. (2) and (3) are both viable, but for correctness I decided to go with (3) in this case, though I may revert that in the future for performance gains.

The division function works like this:

1. Initialize output to 0
2. While a > b, increment output by 1, subtract b from a
3. Multiply a and output by 10 (effectively we’re shifting our division one digit to the right)
4. Repeat (2) -> (3) as many times as precision is desired

This results in a division function that looks like this:

function float.divide {
    local a
    local b
    local total
    local precision
    local sign

    precision=0
    total=0

    a="$(float.parse "$1")"
    b="$(float.parse "$2")"

    # figure out what sign the result should have, strip signs from the numbers being used
    if [[ "${a:0:1}" == "-" ]]; then
        sign="-"
        a="${a:1}"
    fi
    if [[ "${b:0:1}" == "-" ]]; then
        if [[ "${sign}" == "-" ]]; then
            sign=""
        else
            sign="-"
        fi
        b="${b:1}"
    fi

    # division loop
    while (( precision < FLOAT_PRECISION )); do
        while (( a >= b )); do
            total=$((total + 1))
            a=$((a - b))
        done
        b=$((b / 10))
        total=$((total * 10))
        precision=$((precision + 1))
    done

    echo "${sign}$(float.format "${total}")"
}

which can then be used as follows:

$ float.divide "10.0" "2.5"
  4.00000000

Now that the operations are in place we can start using our float system. I did end up implementing some other functions that came in handy which I won’t go into detail about, but if you’re curious they are:

• float.eq
  • Check if floats are equal
• float.gt
  • Check if a is greater than b
• float.lt
  • Check if a is less than b
• float.gte
  • Check if a is greater than or equal to b
• float.lte
  • Check if a is less than or equal to b
• float.truncate
  • Truncate a float
• float.mantissa
  • Return just the mantissa of a float
• float.round
  • Round a float
• float.int
  • Return a truncated float without the decimal precision, e.g. 10.00000000 -> 10