Binary Coffee

Operaciones matemáticas con comandos de bash

algorithms bash icpc math shell
Inspirado en soluciones a problemas del [Proyecto Euler](https://projecteuler.net/) 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](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](https://gist.github.com/frarteaga/16a6065f55397f6a3eb5d989ee708755#file-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.
Opiniones
noavatar