Operaciones matemáticas con comandos de bash

Inspirado en soluciones a problemas del Proyecto Euler y la experiencia en concursos de programación competitiva les mostraré como usando solo comandos de la consola de linux es posible obtener varios resultados matemáticos como los números primos.

Primero, un sumario de los comandos que vamos a usar:

$ whatis factor seq shuf bc python time matho-primes grep cut head
 
    factor (1)         - factor numbers
    seq (1)            - print a sequence of numbers
    shuf               - generate random permutations
    bc (1)             - An arbitrary precision calculator language
    python (1)         - an interpreted, interactive, object-oriented pro...
    time (1)           - run programs and summarize system resource usage
    matho-primes (1)   - generate consecutive prime numbers
    grep (1)           - print lines matching a pattern
    cut (1)            - remove sections from each line of files 
    head (1)           - output the first part of files

Todos, excepto matho-primes, los podemos encontrar por defecto en la mayoría de las distros. Para obtener matho-primes puedes instalar el paquete mathomatic desde un repositorio: apt-get install mathomatic para Debian y similares, u obtener la última versión y código en http://mathomatic.org.

Veamos algunos ejemplos para empaparnos con los modos de invocación:

$ factor 15
    15: 3 5
$ seq 1 4
    1
    2
    3
    4
$ seq 5 2 10
    6
    8
    10
$ seq 3 2 11 | factor
    3: 3
    5: 5
    7: 7
    9: 3 3
    11: 11
$ seq 1 3 | shuf
    2
    1
    3
$ seq 2 4 | factor | cut -d: -f2
     2
     3
     2 2

Para entrar en materia concentrémonos en dos problemas a continuación.

Problema 1: Encontrar un número primo aleatorio de seis dígitos.

Determinar si un número es primo es un subproblema a resolver, lo cual será resuelto combinando los comandos factor, cut y grep por tuberías de la siguiente manera:

factor | cut -d: -f2 | cut -b2- | grep -v ' '

Este comando lee de la entrada estándar números e imprime solo aquellos que son primos. Después de esto es fácil obtener todos los números primos entre 100000 y 999999, desordenarlos con shuf e imprimir el primero:

seq 100001 2 999999 | \
factor | cut -d: -f2 | cut -b2- | grep -v ' ' | \
shuf | head -1

Veamos otra solución más eficiente y simple con matho-primes:

matho-primes 100001 999999 | shuf | head -1

Esta última es más eficiente gracias a que este software usa una criba en lugar de factorizar.

Probemos y midamos tiempos con time:

$ time seq 100001 2 999999 | \
   factor | cut -d: -f2 | cut -b2- | grep -v ' ' | \
   shuf | head -1
578077        
 
real    0m0.524s
user    0m0.503s
sys     0m0.020s

$ time matho-primes 100001 999999 | shuf | head -1
182089

real    0m0.204s
user    0m0.191s
sys     0m0.013s

Problema 2: Calcular el factorial 1000.

Es evidente que deberemos usar bc o python como calculadora en algún momento. Pero antes debemos ser capaces de formar la expresión del factorial usando el comando seq con el parámetro -s, --separator=STRING use STRING to separate numbers (default: \n):

$ seq -s\* 2 1000
2*3*4*5*.....  

Luego esta expresión sería la entrada de la calculadora que decidamos usar.

$ seq -s\* 2 1000 | bc
402387260077093773543......

$ echo "print `seq -s\* 2 1000`" | python
402387260077093773543......

Según he observado a la que usa bc es ligeramente más eficiente para números menores que 1500, y para números superiores la que usa python es considerablemente más rápida:

          100        3000        6000         12000        15000
bc      ~0.005s      ~0.26s      ~1.07s       ~4.5s        ~7.6s
python  ~0.035s      ~0.16s      ~0.44s       ~1.6s        ~2.7s

Si deseamos tener un comando similar a factor en cuanto a stdin y stdout, pero que calcule factoriales podemos poner en el archivo de alias de bash una función como esta factorial.sh.

function factorial()
{
    if test $# -eq "0"; then
        # Si no hay paraametros en la linea de comandos
        # leemos de la entrada estandar.
        while read num; do
            echo $num: $(echo `seq -s\* $num` | bc)
        done
    else
        for num in $@; do
            echo $num: $(seq -s\* $num | bc)
        done
    fi
}

Conclusiones

Como hemos visto bash tiene varios comandos que combinados pueden servirnos para realizar no solo operaciones de búsqueda, ordenamiento y filtrado de texto, sino también operaciones matemáticas para generar secuencias, encontrar números primos, computar factoriales y medición del tiempo consumido por la CPU.