Bash for Project Euler - really???
Tags: bash, math, projecteuler, tutorial
Published: 2020-01-18 09:11:58

Whatever language and stack you prefer, **learn bash also!** - that wisdom come to me through years. I was doing electronics and POS-terminals in C++, backend in Java, web with PHP and JS, machine learning in BigData with Python, Scala and many horrible names...

And always there were chores to be done with linux/unix shell scripting!

Let's plan "miniseries" on bash, but let's start with math exercise. To see how bash rocks and know when it sucks :)

For example I pick [Project Euler #7 - "10001-st Prime"](https://projecteuler.net/problem=7). There would be 3 versions of code and they all are [in this git repo](https://github.com/RodionGork/projecteuler-7-bash/tree/master) for reference.

### Let's Rock!

For generating primes we usually need array to collect them. I usually start by initializing first few elements manually (this helps avoiding spare stop condition inside the loop).

```bash
#!/usr/bin/env bash

primes=(2 3 5 7)
```

As clever people warn, we add "shebang" header which allows script to properly start if it is executable.

Array is created by enclosing space-separated sequence in parentheses. (non-posix feature, though we can do without them)

Now we create main loop! Just make 20 first primes for test, not thousands...

```bash
next=9  # next number to try

while [[ ${#primes[@]} -lt 20 ]] ; do
    #here we put more code
    next=$((next+2))
done

```

we understand `while` and `do` and `done`, but what is this whimsical expression? Well, logical expressions are tested in square brackets, `-lt` is "numerical" comparison for "less than" and `${#primes[@]}` is curious expression of the length of array. Bash has funny syntax sometimes.

Now the code inside.

At every iteration we are going to test if `next` is divisible by anything in array `primes`, starting from beginning.

```bash
    i=0
    while true ; do
        p=${primes[i]}
        if [[ $((next % p)) -eq 0 ]] ; then
            # next is divisible by p, not prime, halt
            break
        fi

        # some end condition we add at next step...

        i=$((i+1))
    done
```

Here we see new features - `if - fi` block (it supports `else` too), `-eq` operator for numeric equality and forms `$((...))` for evaluating numeric expressions. Shell heavily deals with text so usually variables are treated as strings, not numbers.

Now how we decide new prime is found? We don't need to go till end of `primes`, it's enough to stop when `p` is greater than `sqrt(next)` - let's add it to the loop:

```bash
        if [[ $((p * p)) -gt $next ]] ; then
            primes+=($next)
            break
        fi
```

Looks good! Let's print out `primes` after main loop ended to check:

```bash
        # various code before...
    next=$((next+2))
done

echo ${primes[@]}

```

Curiously, syntax for "whole array" is quite close to syntax of taking length... Now I save this into file `pe-7.sh`, set executable flag and run:

```
$ chmod a+x pe-7.sh
$ ./pe-7.sh
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
```

Wonderful! Now we need two small changes:

- replace `20` with `10001` in the main loop condition
- don't print whole array, but only its last element with `${primes[-1]}`

Feel free to check [the whole code in github](https://github.com/RodionGork/projecteuler-7-bash/blob/master/pe-7.sh) - it's brief.

Run the program with `time` program to see how long it takes :)

```
$ time ./pe-7.sh 
104743

real	0m12.896s
user	0m12.881s
sys	0m0.004s

```

Result is correct. **But wow, 13 seconds** - definitely bash is not intended to be the fastest. However there are faster shell versions (e.g. `dash`) and on other hand I'll show you how to make it much slower :)

---

### Refactor it

Bash supports functions. Let's extract inner loop into function. It can be checked that running time doesn't increase seriously.

```bash
tryprime() {
    local try=$1   # $1 is the 1-st parameter
    i=0
    while true ; do
        p=${primes[i]}
        if [[ $((try % p)) -eq 0 ]] ; then
            break
        fi
        if [[ $((p * p)) -gt $try ]] ; then
            primes+=($try)
            break
        fi
        i=$((i+1))
    done
}
```

The function takes single parameter and puts it into local variable. Curiously, parameters are not passed in the parentheses :)

We don't return value, rather just add it to `primes` global array. I'll explain this bit later.

Now call the function in main loop:

```bash
next=9
while [[ ${#primes[@]} -lt 10001 ]] ; do
    tryprime $next
    next=$((next+2))
done

```

Hey, that's neat! [Full code in GH](https://github.com/RodionGork/projecteuler-7-bash/blob/master/pe-7-function.sh). And it still works - took 14 seconds...

---

### Performance Pitfall

Now just small change to **make it sloooooow**!

Let's return value from function. This is not done by `return` (which serves for other purpose). We rather print value in the function and capture it from output on call:

```bash

    # change this inside function
    # primes+=($try)
    # to this
    echo $try

#and main loop will be:
while [[ ${#primes[@]} -lt 10001 ]] ; do
    found=$(tryprime $next)
    primes+=($found)
    next=$((next+2))
done

```

The complete code [is here](https://github.com/RodionGork/projecteuler-7-bash/blob/master/pe-7-slooow.sh). Run it to get... 76 seconds!!!

Well, bash is shell version designed for reach user-friendly features, not for speed. But it is important to know such pitfalls :)

**Thanks for reading that far!** Let's meet next time to make some web-related work with bash :)