:::: MENU ::::

Llevemos el factorial al extremo

En este post vamos a utilizar como lenguaje C# y Scala, no obstante sería posible hacerlo con otros lenguajes con sus correspondientes librerías de BigInteger.

Si habéis hecho cualquier curso, universitario, por internet, etc; para practicar recursividad, siempre se suele plantea el siguiente ejercicio:

Haga un método recursivo para calcular n! (n factorial).

Cuando se nos plantea el ejercicio, siempre hacemos algo así:

public static UInt32 Fact(UInt32 n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Tenemos un UInt32 llamado n, es decir, un int pero sin signo, de forma que no puede ser negativo, como argumento.
Si n es menor que 2, sabemos que 1! y 0! son 1, así que devolvemos 1 directamente.
De lo contrario, devolvemos n * (n-1)!.

«Bien, ya le he enseñado a hacer el ejercicio a mi alumna de repaso», pensé.
Pero luego empecé a darle vueltas a la cabeza; sé cuanto es el máximo para enteros de 32 bits, también el de 64 bits…
Sabía que los factoriales, al ser exponenciales, se dispararían en cuanto a dígitos se refiere, así que busqué en Google: «factorial de 1.000», «factorial de 2.000», «factorial de 3.000″… Así hasta llegar a 10.000, numero posterior al cual no encontré resultados…

En ese momento yo y mi curiosidad, y aprovechando que mi alumna utilizaba C#, me propuse calcular todos los factoriales de 0! a 1.000.000! (simplemente por curiosidad) con la librería BigInteger.

public static BigInteger Fact(BigInteger n)
{
    if (n < 2)
        return 1;
    return n * Fact(n - 1);
}

Sí, era fácil adaptarlo… El problema fue que al ponerlo en práctica descubrí que haciéndolo recursivamente llegaba a un límite muy por debajo de lo esperado, en concreto alrededor de 7.000!, ya que depende del tamaño de la pila de llamadas del sistema, y esta no es muy grande (en mi caso), por lo que hacerlo de esta forma no era la solución.

StackOverflowException

Si bien es cierto que se puede cambiar el límite de la pila (en Unix suele ser mayor por defecto) y algunos compiladores podrían hacerlo con saltos, no es el caso, así que optaremos por un clásico bucle for.

A la función que nos devuelve el Factorial sin recursividad, la llamaremos NRFact(n).

public static BigInteger NRFact(UInt32 n)
{
    BigInteger r = 1;
    for (; n > 1; n--)
        r *= n;
    return r;
}

Si nos fijamos, es un simple for que va decrementando n y multiplicándolo por r en cada iteración, siendo este inicialmente 1.
El bucle for no tiene inicializador ya que n per se es el valor inicial.

Con esto ya podemos calcular factoriales enormes. Necesita cierto tiempo para calcular valores grandes, ya que tiene que iterar muchas veces y el proceso de multiplicación es más costoso de forma exponencial conforme aumentemos n.

No obstante, yo no quería quedarme ahí, así que decidí hacer un programa que calculase los factoriales de 0 a 1.000.000 y, de esa forma, poder mostrarlos luego en una página web, o de la forma deseada, pues calcularlos es costoso y podemos necesitarlos de forma más rápida, así que decidí guardarlos como documentos de texto plano cuyo nombre era el valor a factorializar.

Aquí entraba en cuestión el que las memorias secundarias (como es el caso de un SSD) no son comparables de ninguna forma en cuanto a velocidad con las primarias (como puede ser la RAM), por lo que se crea un gran cuello de botella, y tarda muchísimo más en guardar el resultado en disco que calcularlo en sí.

O eso pensé yo al obtener tiempos de más de 6 segundos… Hasta que pasé mi código de C# a Scala, es decir, ejecutado en la Java Virtual Machine y utilizando el IO de Java, y pasó de 6 segundos a escasos 100 milisegundos por archivo escrito.
Diréis que en C# hay diferentes alternativas y así es, probé muchísimas alternativas para escribir los archivos, incluso intenté hacerlo asíncrono o crear 8 threads escribiendo un archivo por vez… Pero no mejoró en absoluto.

Diferencia Milisegundos/archivo guardado.
Menor es mejor.

Es importante recalcar que ambos tardan 0 milisegundos en calcular cada factorial (al menos en los números que se manejan ahora), la diferencia es puramente en sus librerías de I/O y/o rendimiento.

Por ello, os dejo el código completo para ir generando los Factoriales y guardarlos en .txt en Scala:

package main

import java.math.BigInteger
import java.io._

object Factorial {
  def main(args: Array[String]): Unit = {
    var r = new BigInteger("1")
    for(i <- 1 to 1000000) {    // Aquí ponemos el valor límite a calcular
      val startTime = System.currentTimeMillis
      r = r multiply new BigInteger(i.toString)

      val fileName = "C:\\Factorial\\" + i + ".txt";  // Aquí la ruta
      val file = new File(fileName)
      if(!file.exists) {
        file.createNewFile
        val writer = new BufferedWriter(new FileWriter(fileName))
        writer.write(r.toString)
        writer.close
      }

      println(i + " - " + (System.currentTimeMillis - startTime) + "ms")
    }
  }
}

Con el fin de poder visualizar los factoriales ya calculados por mi programa (cuyo objetivo es llegar a 1.000.000! gradualmente), podéis acceder al siguiente enlace.


Calcular PI con lanzamientos

¿Nunca has escuchado que se puede calcular PI de forma aproximada con granos de arroz?

Pues muchas de esas formas de calcular PI de forma aproximada se pueden realizar programáticamente, ya que al fin y al cabo se basan en el azar y en la colocación en un plano de elementos.

Para esto, nosotros vamos a utilizar «agujas» (o cualquier elemento que tenga dicha forma, ya sean palillos u otro que queramos imaginar).

¿Por qué agujas? La fórmula que utilizamos es derivada de La aguja de Buffon, acerca de la cual os dejo un artículo interesante:
http://www.estadisticaparatodos.es/taller/buffon/buffon.html

¡Vamos a ello!
Se nos dice que, si tenemos un plano dividido en filas del mismo alto que el tamaño de unas simples agujas, siendo esas divisiones marcadas con lápiz, y lanzamos una cantidad N de agujas sobre ese plano, con la cantidad de colisiones entre las agujas y las líneas marcadas N’ y una simple fórmula obtendremos aproximadamente PI.

A todo esto y aplicando la lógica, no hace falta decir que a mayor número de intentos, mayor «precisión» obtendremos, siempre sabiendo que es imposible obtener el número exacto, y más sabiendo que tiene infinitos decimales.

La fórmula que nos proporcina La aguja de Buffon es la siguiente:

 π = 2N/N'
Siendo
N los lanzamientos totales
N' la cantidad de colisionens

Por tanto, teniendo dicha fórmula, nos ponemos manos a la obra y obtenemos dicho código (PHP):

<?php
// Config
$times = 1000000; // Lanzamientos de aguja
$size = 30; // Tamaño de aguja
$lines = 40; // Cantidad de líneas
$separation = $size; // Separación entre líneas (tiene que ser igual al tamaño)

$gridsize = $lines * $separation;

$count = 0;

for($i = 0; $i < $times; $i++)
{
	// Generamos aguja
	$position = rand(0, $gridsize);
	$angle = rand(0, 90);
	
	// Detectamos las líneas de arriba y abajo (nos ahorramos generar un tablero y recorrerlo en busca de colisiones)
	$upper = floor($position / $separation) * $separation;
	$bottom = ceil($position / $separation) * $separation;
	
	// Borde arriba y abajo de la aguja
	$up = $position - sin(deg2rad($angle)) * $size/2;
	$down = $position + sin(deg2rad($angle)) * $size/2;
	
	if($up <= $upper || $down >= $bottom)	// Si tocan o pasan por encima...
		$count++;							// Sumamos 1 al contador
	
	// Para debuggear:
	// echo 'Pos: ', $position, ' | a: ', $angle, ' | Upper: ', $upper, ' | Bottom: ', $bottom, ' | Up: ', $up, ' | Down: ', $down, "\n";
}

echo 'Colisiones: ', $count, '/', $times, "\n";

// Calculemos PI
echo 'PI = ', 2*$times/$count; // Aplicamos la fórmula

while(true){} // Mantengamos la consola abierta para ver el Output

Como siempre, aquí os dejo el enlace a paste.bin:
https://pastebin.com/KtFpbYVa

Y con simplemente con este trocito de código, habremos aproximado PI de forma casera. Cuanto más aumentemos $times, más cerca de 3,14 estará el resultado.

Os recomiendo también ir probando con otros tamaños de agujas o cantidad de líneas, puede ser que varíe el resultado, pese a que la teoría indique que no.

Aquí podemos ver 2 resultados de prueba:
633840/1000000 colisiones // PI = 3.1553704404897
632918/1000000 colisiones // PI = 3.1599670099444
No son lo más preciso del mundo, pero nos puede valer :)

Y con esto, ¡me despido y os deseo una feliz semana!


Ensaïmada numérica, el bot que las resuelve

Pues sí queridos amigos,
Un año y medio después he vuelto y os traigo el post que tanto prometí.
En este caso se trata de un pequeño proyecto de PHP que resuelve las ensaïmadas numéricas (sí, con diéresis, que por algo estamos en Mallorca).
Una ensaïmada numérica es un circuito Hamiltoniano, matemáticamente hablando. En este caso es una tabla de 10×10 en cuyas celdas encontramos todos los valores del 1 al 100 ordenados de una forma específica.
Para empezar, colocamos el valor ‘1’ en cualquiera de las celdas que tiene la tabla, sin importar ningún factor, puro azar. A posteriori, tenemos que proseguir rellenando la tabla incrementando de uno en uno el valor que tenemos, y podemos ir distribuyéndolo de forma diagonal, horizontal y vertical, es decir, podemos ir rellenando hacia arriba, abajo, los lados y diagonal, pero siempre dejando un espacio en diagonal y dos en horizontal o vertical, de forma que sería: 1xx2 (siendo x espacios libres), o en diagonal solo uno. No vale «rebotar» o «atravesar» las paredes, y si deja de haber posiciones libres, no se puede continuar, simplemente hay que empzar con una tabla nueva (o volver atrás en la actual).

Para resolver este problema he optado por fuerza bruta y puro azar en vez de recursividad por pura pereza, pero es posible hacerlo con recursividad, y de hecho no sería demasiado difícil (así que… probablemente tendréis el proyecto modificado en un futuro).

Este programa ha sido realizado en PHP, y se recomienda abrir tantas instancias de este como núcleos/hilos tenga el procesador, para acelerar el proceso. En un futuro os lo traeré en C# y/o Java y con multithreading, de forma que podréis ahorraros el trabajo de abrir múltiples instancias.

Para que funcione, debéis crear una carpeta llamada ‘soluciones’ en la raíz del programa y dentro crear un archivo llamado ‘ultima.txt’. En dicha carpeta se guardarán las soluciones en formato HTML con tablas.

Aquí tenéis un ejemplo de ensaïmada numérica generada por el programa:

Resultado al azar del programa

Resultado al azar del programa

He aquí el código (pastebin también disponible): 

<?php
/* Hecho por Martín Durán - www.maduranma.com */

echo "Buscando soluciones...\n";
$tries = 0;
while(true)
{
// Todos los números a 0 (para tener algo, si no ya se borrará)
for($d = 1; $d <= 100; $d++)
	$r[$d] = 0;
 
// ¿Dónde ponemos el 1?
$tries++;
$rs = rand(1,100);
$r[$rs] = 1;
$l = $rs; // Definimos que la última posición es dónde está el uno, hasta un futuro muy cercano
 
$can_move = true; // Para que el while continue

while($can_move)
{
	// Obtenemos el número de posición horizontal
	if(strlen($l) > 1)
		$h = (substr($l, -1) == 0) ? 10 : substr($l, -1);
	else
		$h = $l;
       
	// Obtenemos el número según el vertical
	if(strlen($l) > 1)
		if($l == 100)
			$v = 10;
		else
			$v = ($h == 10) ? substr($l, 0, 1) : substr($l, 0, 1) + 1;
	else
		$v = 1;
       
	// Ponemos que todos los valores del array $m sean true, para comprobarlos luego
	for($c = 1; $c <= 8; $c++)
		$m[$c] = 1;
       
	// --- Movimientos horizontales ---
	if($h == 8 || $h == 9 || $h == 10 || (($l + 3 > 100) ? true : ($r[$l + 3] != 0)))
		$m[1] = 0;
       
	if($h == 1 || $h == 2 || $h == 3 || (($l - 3 < 1) ? true : ($r[$l - 3] != 0)))
		$m[5] = 0;
       
	// --- Movimientos verticales ---
	if($v == 8 || $v == 9 || $v == 10 || (($l + 30 > 100) ? true : ($r[$l + 30] != 0)))
		$m[3] = 0;
	       
	if($v == 1 || $v == 2 || $v == 3 || (($l - 30 < 1) ? true : ($r[$l - 30] != 0)))
		$m[7] = 0;
	       
	// --- Movimiento arriba derecha ---
	if($h == 9 || $h == 10 || $v == 1 || $v == 2 || (($l - 18 < 1) ? true : ($r[$l - 18] != 0)))
		$m[8] = 0;
	       
	// --- Movimiento arriba izquierda ---
	if($h == 1 || $h == 2 || $v == 1 || $v == 2 || (($l - 22 < 1) ? true : ($r[$l - 22] != 0)))
		$m[6] = 0;
       
	// --- Movimiento abajo derecha ---
	if($h == 9 || $h == 10 || $v == 9 || $v == 10 || (($l + 22 > 100) ? true : ($r[$l + 22] != 0)))
		$m[2] = 0;
       
	// --- Movimiento abajo izquierda ---
	if($h == 1 || $h == 2 || $v == 9 || $v == 10 || (($l + 18 > 100) ? true : ($r[$l + 18] != 0)))
		$m[4] = 0;
       
	$cm = null;
	$cm = array();
	foreach($m as $ia => $ib)
		if($ib == 1)
			$cm = array_merge($cm, array($ia));
       
	// Comprobamos que han salido movimientos
	if(($cm != null) ? count($cm) >= 1 : false)
		$fm = array_rand($cm); // Movimiento elegido
	else
		$can_move = false; // Aquí paramos
       
	if($can_move)
		foreach($cm as $ba => $bb)
			if($ba == $fm)
				$fm = $bb;
       
	// Nos movemos (si podemos)
	if($can_move)
		switch($fm)
		{
			case 1:
				$nl = ($l) + 3;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 2:
				$nl = ($l) + 22;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 3:
				$nl = ($l) + 30;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 4:
				$nl = ($l) + 18;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 5:
				$nl = ($l) - 3;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 6:
				$nl = ($l) - 22;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 7:
				$nl = ($l) - 30;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
			       
			case 8:
				$nl = ($l) - 18;
				$r[$nl] = $r[$l] + 1;
				$l = $nl;
				break;
 
			default:
				echo 'Error';
				$can_move = false;
				break;
		}
	}
 
	if($r[$l]  == 100)
	{
		$file_name = 'soluciones/last.txt';
		$file = fopen($file_name, 'r+');
		$last = fread($file, 11);
        ftruncate($file, 0);
        rewind($file);
		$last = $last + 1;
		fwrite($file, $last);
		fclose($file);
	       
		$content = '<!DOCTYPE html>
	<head>
		<title>Soluci&oacute;n ' . $last . ' del circuito Hamiltoniano - Ensaimada num&eacute;rica</title>
	</head>
	<body style="margin:3 0;">
			<table border="1" style="font-size: 57pt;text-align: center; border: 2px solid black;" cellpadding="2" cellspacing="0">';
		for($a = 1; $a <= 10; $a++)
		{
			$content .= "\n\t\t\t\t<tr>";
			for($b = 1; $b <= 10; $b++)
			{
				$content .= "\n\t\t\t\t\t<td width=\"90\" height=\"75\" style=\"height: 89px; text-align: center; border: 2px solid black;\" >";
				$content .= ($r[(($a-1)*10)+$b] == 0) ? "\n\t\t\t\t\t\t&nbsp;" : ("\n\t\t\t\t\t\t" . $r[(($a-1)*10)+$b]);
				$content .= "\n\t\t\t\t\t</td>";
			}
			$content .= "\n\t\t\t\t</tr>";
		}
		$content .= "\n\t\t\t</table></body></html>";
		echo 'Sol. $contenido encontrada y guardada. Intentos:',  $tries;
				$tries = 0;
		echo "\nBuscando soluciones...\n";
		$file = fopen('soluciones/' . $last . '.html', 'w');
		fwrite($file, $content);
		fclose($file);
	}
}

maduranma’s Stresser – Generador de estrés para el procesador

Hola lectores,
Estaba en clase y me plateé qué haría falta para petar la CPU del ordenador que teníamos, así que básicamente hice un programa en C# que calculaba los cosenos de 69 (por la naturaleza del número…) infinitamente (con un bucle while), y abriendo uno por núcleo de dicho procesador conseguías ponerlo al 100% (que además con la de años que tienen y contando que en su vida se han limpiado, se han puesto a 90-100 grados los jodios…).

Código del programa absurdo

Código del programa de clase (absurdamente fácil)

Después he decicido hacer algo útil, y puesto que ya he visto programas que hacen esto, de hecho hice un tutorial en mi canal de como hacer un test de estrés (que básicamente sirve para ver la temperatura cuando le estás metiendo caña al procesador), pero el programa que usé lo encontré por internet, y tenías que abrir un programa por núcleo, y eso nos lo podríamos ahorrar si simplemente lo hubieran hecho con varios threads en C# mismamente, así que, he decidido hacerlo yo en media horita o así y me ha quedado algo bastante cuqui, por ello he decidido publicar el resultado en este blog, por supuesto será Open Source, y si veo que tiene «éxito» supongo que lo actualizaré y una posible mejora en un futuro sería añadir abajo la temperatura de todos los cores (más o menos como SpeedFan, que es un buen complemento a usar con mi programa actualmente).

Speed Fan, para ver la temperatura de la CPU

Speed Fan, para ver la temperatura de la CPU

Aún teniendo propuestas las mejoras mencionadas anteriormente, el programa cumple perfectamente con su función, y solo requiere .NET Framework 3.5 (que viene instalado por defecto desde Windows 7, y sigue siendo compatible con Windows Vista con una simple actualización). Cabe mencionar que con cualquier versión posterior también sirve.

Mi programa (maduranma's Stresser)

Mi programa (maduranma’s Stresser)

Descargar_ICONODescargas

 Descargar versión 1.0.1Directa | Mediafire | Mega.co.nz