A tatuagem do programador

Se fosse obrigatório fazer tatuagem, ao invés de tatuar aquelas asneiras de jogador de futebol, todo programador deveria tatuar seu algoritmo preferido.

tattoo

Este seria o meu, tal é a beleza e simplicidade do algoritmo concebido por Euclides para achar o máximo divisor comum entre os números inteiros x e y.

O mestre Donald Knuth diz no volume 2 da bíblia:

“[The Euclidean algorithm] is the granddaddy of all algorithms, because it is the oldest nontrivial algorithm that has survived to the present day.”

E qual o algoritmo que você tatuaria?

Números primos e algoritmos – Parte III (final)

Hoje mostraremos algoritmos que são rápidos e determinísticos (ou seja, sempre indicam correto se o número é primo ou não), alguns destes foram desenvolvidos no ano de 1983, no entanto em 2002 foi mostrado pela primeira vez um algoritmo, chamado AKS, para encontrar números primos que reunia as seguintes características:

  • Geral: para qualquer tipo de número primo e não apenas para alguns subconjuntos de primos.
  • Tempo Polinomial: com relação ao número de dígitos.
  • Determinístico
  • Incondícional: Ou seja, foi provado que o algoritmo não depende de nenhuma conjectura.

O teorema sobre o qual o algoritmo AKS se sustenta é uma generalização do pequeno teorema de Fermat que mostramos na semana passada.

pow ((x-a),n) % pow(x,n)-a = n

Onde n é o número primo e a é um primo em comum com n.

Abaixo vai uma das possíveis implementações dele:

#include <iostream>
using namespace std;
#include <math.h>
 
#ifdef _M_IX86
 
#define umulrem(z, x, y, m)	\
__asm	mov		eax, x	\
__asm	mul		y	\
__asm	div		m	\
__asm	mov		z, edx
 
#define umuladdrem(z, x, y, a, m)	\
__asm	mov		eax, x	\
__asm	mul		y	\
__asm	add		eax, a	\
__asm	adc		edx, 0	\
__asm	div		m	\
__asm	mov		z, edx
 
#else
 
#ifdef _MSC_VER
typedef unsigned __int64	Tu64;
#else
typedef unsigned long long	Tu64;
#endif
 
#define umulrem(z, x, y, m)	\
	{	\
	z = (unsigned int)(x * (Tu64)y % m);	\
	}
 
#define umuladdrem(z, x, y, a, m)	\
	{	\
	z = (unsigned int)((x * (Tu64)y + a) % m);	\
	}
 
#endif
 
static bool IsPrime(unsigned int n)
{
	if (n < 2) return false;
	if (n < 4) return true;
	if (n % 2 == 0) return false;
 
	const unsigned int iMax = (int)sqrt(n) + 1;
	unsigned int i;
	for (i = 3; i <= iMax; i += 2)
		if (n % i == 0)
			return false;
 
	return true;
}
 
static unsigned int LargestPrimeFactor(unsigned int n)
{
	if (n < 2) return 1;
 
	unsigned int r = n, p;
	if (r % 2 == 0)
	{
		p = 2;
		do { r /= 2; } while (r % 2 == 0);
	}
	unsigned int i;
	for (i = 3; i <= r; i += 2)
	{
		if (r % i == 0)
		{
			p = i;
			do { r /= i; } while (r % i == 0);
		}
	}
	return p;
}
 
static unsigned int Powm(unsigned int n, unsigned int e, unsigned int m)
{
	unsigned int r = 1;
	unsigned int t = n % m;
	unsigned int i;
	for (i = e; i != 0; i /= 2)
	{
		if (i % 2 != 0)
		{
			umulrem(r, r, t, m);
		}
		umulrem(t, t, t, m);
	}
	return r;
}
 
static unsigned int Inv(unsigned int n, unsigned int m)
{
	unsigned int a = n, b = m;
	int u = 1, v = 0;
	do
	{
		const unsigned int q = a / b;
 
		const unsigned int t1 = a - q*b;
		a = b;
		b = t1;
 
		const int t2 = u - (int)q*v;
		u = v;
		v = t2;
	} while (b != 0);
	if (a != 1) u = 0;
	if (u < 0) u += m;
	return u;
}
 
class CPolyMod
{
protected:
	// (mod x^r - 1, n)
	const unsigned int m_r;
	const unsigned int m_n;
	unsigned int m_deg;
	unsigned int * mp_a;
 
private:
	CPolyMod():m_r(0), m_n(0) { mp_a = NULL; };
 
public:
	// default value is x
	CPolyMod(unsigned int r, unsigned int n)
		: m_r(r), m_n(n)
	{
		m_deg = 1;
		mp_a = new unsigned int [2];
		mp_a[0] = 0; mp_a[1] = 1;
	}
 
	CPolyMod(const CPolyMod & p)
		: m_r(p.m_r), m_n(p.m_n)
	{
		m_deg = p.m_deg;
		mp_a = new unsigned int [p.m_deg + 1];
		unsigned int i;
		for (i = 0; i <= p.m_deg; ++i)
			mp_a[i] = p.mp_a[i];
	}
 
	virtual ~CPolyMod()
	{
		if (mp_a != NULL)
			delete [] mp_a;
	}
 
private:
	void _polySquare()
	{
		const unsigned int deg = m_deg;
		const unsigned int n = m_n;
		const unsigned int * const p_a = mp_a;
 
		const unsigned int degr = deg + deg;
		unsigned int * const p_ar = new unsigned int [degr + 1];
		unsigned int k;
		for (k = 0; k <= degr; ++k)
			p_ar[k] = 0;
 
		unsigned int j;
		for (j = 1; j <= deg; ++j)
		{
			const unsigned int x = p_a[j];
			if (x != 0)
			{
				unsigned int i;
				for (i = 0; i < j; ++i)
				{
					const unsigned int y = 2 * p_a[i];
					unsigned int t = p_ar[j + i];
					umuladdrem(t, x, y, t, n);
					p_ar[j + i] = t;
				}
			}
		}
		unsigned int i;
		for (i = 0; i <= deg; ++i)
		{
			const unsigned int x = p_a[i];
			unsigned int t = p_ar[2 * i];
			umuladdrem(t, x, x, t, n);
			p_ar[2 * i] = t;
		}
 
		m_deg = degr;
		delete [] mp_a;
		mp_a = p_ar;
	}
 
	void _polyMul(const CPolyMod & p)
	{
		const unsigned int deg = m_deg;
		const unsigned int n = m_n;
		const unsigned int * const p_a = mp_a;
 
		const unsigned int degr = deg + p.m_deg;
		unsigned int * const p_ar = new unsigned int [degr + 1];
		unsigned int k;
		for (k = 0; k <= degr; ++k)
			p_ar[k] = 0;
 
		unsigned int j;
		for (j = 0; j <= p.m_deg; ++j)
		{
			const unsigned int x = p.mp_a[j];
			if (x != 0)
			{
				unsigned int i;
				for (i = 0; i <= deg; ++i)
				{
					const unsigned int y = p_a[i];
					unsigned int t = p_ar[j + i];
					umuladdrem(t, x, y, t, n);
					p_ar[j + i] = t;
				}
			}
		}
 
		m_deg = degr;
		delete [] mp_a;
		mp_a = p_ar;
	}
 
	void _Mod()
	{
		unsigned int deg = m_deg;
		unsigned int * const p_a = mp_a;
		while (deg >= m_r)
		{
			p_a[deg - m_r] += p_a[deg];
			if (p_a[deg - m_r] >= m_n) p_a[deg - m_r] -= m_n;
			--deg;
 
			while (p_a[deg] == 0) --deg;
		}
		m_deg = deg;
	}
 
	void _Norm()
	{
		const unsigned int deg = m_deg;
		const unsigned int n = m_n;
		unsigned int * const p_a = mp_a;
		if (p_a[deg] != 1)
		{
			const unsigned int y = Inv(p_a[deg], m_n);
			unsigned int i;
			for (i = 0; i <= deg; ++i)
			{
				unsigned int t = p_a[i];
				umulrem(t, t, y, n);
				p_a[i] = t;
			}
		}
	}
 
public:
	CPolyMod & operator = (const CPolyMod & p)
	{
		if (&p == this) return *this;
		m_deg = p.m_deg;
		delete [] mp_a;
		mp_a = new unsigned int [p.m_deg + 1];
		unsigned int i;
		for (i = 0; i <= p.m_deg; ++i)
			mp_a[i] = p.mp_a[i];
		return *this;
	}
 
	int operator != (const CPolyMod & p) const
	{
		if (m_deg != p.m_deg)
			return true;
		unsigned int i;
		for (i = 0; i <= m_deg; ++i)
			if (mp_a[i] != p.mp_a[i])
				return true;
		return false;
	}
 
	CPolyMod & operator += (unsigned int i)
	{
		const unsigned int t = i % m_n;
		mp_a[0] += t;
		if (mp_a[0] >= m_n) mp_a[0] -= m_n;
		return *this;
	}
 
	CPolyMod & operator -= (unsigned int i)
	{
		const unsigned int t = m_n - i % m_n;
		mp_a[0] += t;
		if (mp_a[0] >= m_n) mp_a[0] -= m_n;
		return *this;
	}
 
	CPolyMod Pow(unsigned int e) const
	{
		unsigned int er = 1;
		unsigned int j;
		for (j = e; j != 1; j /= 2)
		{
			er = 2 * er + (j % 2);
		}
 
		CPolyMod t(*this);
		unsigned int i;
		for (i = er; i != 1; i /= 2)
		{
			t._polySquare();
			t._Mod();
			if (i % 2 != 0)
			{
				t._polyMul(*this);
				t._Mod();
			}
		}
		t._Norm();
		return t;
	}
};

Com isto encerramos nossa série de introdução aos números primos. Se você quiser ler mais sobre o assunto eu recomendo este artigo avançado:
http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf
e este artigo em termos mais leigos:
http://www.flonnet.com/fl1917/19171290.htm

Gerador de Números Aleatórios Humanos

A exploração de fenômenos aleatórios ou” aleatorizadores” ocorre desde a Antiguidade. Achados arqueológicos na região da antiga Mesopotâmia revelaram os dados (de 6 faces, como o que você usa para jogar WAR) mais antigos conhecidos, feitos de barro cozido cerca de 2750 a.C. Ilustrações de jogos como par ou ímpar de cerca de 2000 a.C. também foram encontrados no Egito, em túmulos atribuídos a Beni Hassan.

Além da utilidade para jogos, algumas civilizações como os gregos (vide a Ilíada) também utilizavam os aleatorizadores como uma forma de revelação da vontade divina. É interessante notar que mesmo em nossa cultura, ainda temos uma herança desta concepção, presente nos búzios ou tarô. Mesmo quando algum felizardo ganha o prêmio máximo na loteria, as pessoas pensam “era para ser assim” ou “é porque Deus quis”.

Podemos não perceber, mas cada um de nós convive diariamente com o fenômeno da aleatoriedade. Seja porque o universo possui uma aleatoriedade intrínseca (como afirma a mecânica quântica) ou porque nós humanos não temos acesso a toda informação disponível (e portanto não podemos fazer previsões perfeitas sobre tudo). É bem sabido que computadores não são capazes de gerar números aleatórios. Na realidade, eles geram números pseudo-aleatórios, baseados em regras, ou seja, fórmulas matemáticas. Sabendo a regra, a previsão de todos os números a serem gerados é realizada sem erros. Esta é uma das principais fontes de vulnerabilidade da criptografia (quem quiser ler algo legal que pode levá-lo ao Geek Level 8 compre o livro Silence on the Wire)

Para muitos, os melhores aleatorizadores são baseados em medições de decaimento radioativo ou outros fenômenos físicos.

No entanto, uma pergunta interessante é levantada: e os seres humanos? São aleatórios? De fato, sempre há um fator de imprevisibilidade em qualquer ser humano. Logo, a pergunta mais lógica seria: “Quão aleatórios/previsíveis são os seres humanos?”. Diversos estudos de psicologia cognitiva e até mesmo medicina, mostraram que a geração de sequências aleatórias por seres humanos envolvem funções executivas como memória e atenção. Estudos de neuroimagem funcional chegaram a mostrar o envolvimento dos lobos frontais na execução desta tarefa e outros estudos clínicos mostraram uma menor aleatoriedade (no sentido de maior previsibilidade) das sequência de números geradas por indivíduos com doença de Huntington, Parkinson, Alzheimer ou autismo. Mesmo indivíduos com comprometimento de funções executivas, como um alcoolizado, geram sequências de números mais previsíveis.

Atualmente, há um jogo online, que tem como objetivo quantificar quão aleatórios são os seres humanos, e quais são os principais fatores que influenciam nesta imprevisibilidade.

Contribua com este estudo, participe em:

http://randomicogame.appspot.com