{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Geração de números aleatórios\n",
    "\n",
    "Donald Knuth é uma das maiores autoridades vivas da área de Computação e uma das pessoas que mais contribuiram para o sucesso da área. Para você ter uma ideia, foi ele quem criou o sistema Tex, que mais tarde virou o Latex, que todos usamos. Uma outra grande contribuição dele foi uma série de sete volumes \"The Art of Computer Programming\", que ainda não está acabada (para saber mais, veja, por exemplo, aqui: https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming, ou aqui: https://www-cs-faculty.stanford.edu/~knuth/taocp.html). Pois bem, no segundo volume da série, \"Seminumerical Algorithms\", ele usa quase um terço do livro para tratar da geração de números aleatórios ou, em verdade, geração de números \"pseudo\" aleatórios. \n",
    "\n",
    "Neste pequeno notebook, você verá porque essa é uma das tarefas difíceis e importantes da computação. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pequeno histórico\n",
    "\n",
    "Números aleatórios são de aplicação prática tão importante que a busca por formas de conseguí-los é muito antiga, alguns casos mais importantes são:\n",
    "\n",
    "1- L. H. C. Tippett publicou em 1927 uma tabela de 40000 dígitos \"aleatórios\" de registros do censo americano (https://en.wikipedia.org/wiki/L._H._C._Tippett);\n",
    "\n",
    "2- Um pouco mais tarde, em 1939, M.G. Kendall e B. Babinghton Smith, no artigo: \"Randomness and Random Sampling Numbers\" (https://www.jstor.org/stable/pdf/2980655.pdf?seq=1) publicaram uma tabela de 100000 números gerados por uma máquina auxiliada por um operador humano;\n",
    "\n",
    "3- Em 1949, a RAND Corporation (https://en.wikipedia.org/wiki/RAND_Corporation) publicou um estudo sobre a geração de números aleatórios a partir, também, de um processo físico que imitava uma roleta eletrônica de 32 posições (https://www.rand.org/content/dam/rand/pubs/papers/2008/P113.pdf);\n",
    "\n",
    "4- Em 1951, os projetistas do computador Ferranti Mark I incluiram em seu conjunto de instruções uma instrução para feral um número aleatório de 20 bits usando um gerador de ruído resistivo (https://en.wikipedia.org/wiki/Ferranti_Mark_1);\n",
    "\n",
    "5- Em 1957, a Inglaterra queria que seus cidadãos poupassem dinheiro e, por isso, criou uma loteria eletrônica e um computador especialmente para gerar números aleatórios, o \"Electronic Random Number Indicator Equipment\", ou ERNIE (https://www.i-programmer.info/history/machines/6317-ernie-a-random-number-generator.html);\n",
    "\n",
    "Essa história é muito rica, importante e não para nesses poucos ítens, mas é possível ter uma ideia do esforço gasto para esse problema. Muitos artigos foram escritos, inclusive, questionando a validade estatística, ou a aleatoriedade dos números gerados dessa forma e logo começou-se a pensar em outras formas de geração de números aleatórios."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Números pseudo-aleatórios\n",
    "\n",
    "A geração de números aleatórios usando hardware não foi a única iniciativa nesse sentido. Em 1946, por exemplo, John Von Neumann, um outro \"gigante\" da área da computação, propôs um método aritmético simples para a geração de números aleatórios. Iniciando com um número p grande de dígitos, digamos dez dígitos, eleva-se o número ao quadrado e tomam-se os p dígitos centrais, que é usado novamente para a geração do próximo número.\n",
    "\n",
    "Usando esse método, G. E. Forsythe conseguiu gerar 750000 números de 38 bits antes da aleatoriedade degenerar. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "33317792380594909201\n",
      "333177923805949\n",
      "333170000000000\n",
      "7923805949\n"
     ]
    }
   ],
   "source": [
    "# As linhas abaixo geram um segundo número a partir do número 5772156649\n",
    "\n",
    "s = 5772156649\n",
    "s2 = s*s\n",
    "print(s2)\n",
    "ns1 = int(s2/100000)\n",
    "print(ns1)\n",
    "ns2 = 10000000000 * int(ns1/10000000000)\n",
    "print(ns2)\n",
    "ns = ns1-ns2\n",
    "print(ns)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercício: Dado n e s, faça um programa que imprima os n primeiros \n",
    "# números aleatórios de acordo com o algoritmo proposto por Neumann"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Método de congruência linear\n",
    "\n",
    "Métodos heurísticos tendem a ser ruins para a geração de números aleatórios e em  1949, D. H. Lehmer, propôs o método da congruência linear. Esse método precisa de quatro números \"mágicos\":\n",
    "- $m$ - módulo, um número inteiro positivo, $m>0$\n",
    "- $a$ - multiplicador, um número inteiro positivo, $0\\le a < m$\n",
    "- $c$ - incremento, um número inteiro positivo, $0\\le c < m$\n",
    "- $X_0$ - a semente inicial do gerador, $0\\le X_0 < m$\n",
    "\n",
    "Os números são então gerados segundo uma fórmula de recorrência:\n",
    "\n",
    "$X_{n+1} = (aX_n + c)$ mod $\\ m, n\\ge 0$\n",
    "\n",
    "Por exemplo: sejam $m=10$ e $X_0 = a = c = 7$; os números então serão:\n",
    "\n",
    "$X_0 = 7$, $X_1 = 6$, $X_2 = 9$, $X_3 = 0$, $X_4 = 7$, $X_5 = 6$, $X_6 = 9$, $X_7 = 0$\n",
    "\n",
    "Métodos de congruência sempre levam a um ciclo, que depende do valor de $m$. Aliás, $m$ é o maior ciclo de um método congruência. \n",
    "\n",
    "Teorema: O método de congruência linear definido por $m, a, c$ e $X_0$ tem período $m$ se e somente se:\n",
    "\n",
    "i) $c$ é primo relativo a $m$;\n",
    "\n",
    "ii) $b=a-1$ é múltiplo de $p$ para todo primo $p$ que divide $m$;\n",
    "\n",
    "iii) $b$ é um múltiplo de 4 se $m$ é um múltiplo de 4.\n",
    "\n",
    "Na prática, usualmente $m$ é o maior inteiro representável no computador, menos um, isto é: $m=2^{31} - 1 = 2147483647$, $c$ é normalmente igual a zero e $a$ na libc, é igual a 16807. Em outras palavras, ou equações: \n",
    "\n",
    "\n",
    "$X_{n+1} = (16807*X_n)$ mod $2147483647$\n",
    "\n",
    "$m-1$ é, assim, o maior valor que o gerador aleatório vai assumir. Na libc, que tem a função rand para gerar números aleatórios, ele é chamado RAND_MAX. O valor $X_0$, na libc pode ser inicializado pela função srand. Para saber mais, veja https://www.gnu.org/software/libc/manual/html_node/ISO-Random.html#ISO-Random\n",
    "\n",
    "Há vários problemas a serem enfrentados para a implementação desta fórmula e algumas dicas podem ser encontradas no livro Numerical Recipes in C (o livro está online, mas depende de Flash; assim, se você quiser saber mais, olhe aqui: https://www.unf.edu/~cwinton/html/cop4300/s09/class.notes/LCGinfo.pdf). Na glibc, essa implementação é um pouco mais elaborada.\n",
    "\n",
    "Um último comentário a respeito da fórmula é que o valor de $X_i$ não é independente dos valores de $X_j$ para $0 \\le j < i$. Em outras palavras, um experimento para o qual seja necessário independência, deve-se descorrelacionar as amostras. Donald Knuth apresenta duas estratégias para fazer isso no livro Seminumerical Algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercício: Experimente implementar o algoritmo da congruência linear em Python e, \n",
    "# usando a mesma semente do exercício anterior, gere e armazene n números aleatórios \n",
    "# e compare com os números gerados anteriormente. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Como gerar números aleatórios dentro de um intervalo\n",
    "\n",
    "Ingenuamente, mas matematicamente correto, pode-se pensar que a forma de gerar números dentro de um intervalo, digamos $[0,L]$ é multiplicar o valor da função rand por $\\frac{L+1}{RAND\\_MAX}$. Porém, como explicado no livro Numerical Recipies in C, essa forma não é boa. Caso você tenha interesse em saber mais, leia o capítulo Random Numbers desse livro.\n",
    "\n",
    "Em Python é mais fácil pois já existe a função randint(a, b) da biblioteca random (https://docs.python.org/3/library/random.html). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teste estatístico do Chi-quadrado\n",
    "\n",
    "O teste do Chi-quadrado é um teste simples e muito conhecido para verificar o quanto uma distribuição que está sendo estudada difere de uma distribuição conhecida. \n",
    "\n",
    "Não vamos entrar em muito detalhes de como é este teste, já que ele deve ter sido apresentado na disciplina de estatística do semestre anterior (por favor, avisem-nos caso não tenha sido o caso). Apenas relembrando rapidamente, vamos assumir que haja $k$ categorias às quais uma variável aleatória possa ser associada e que tenhamos $n$ observações independentes. Assim, a estatística do Chi-quadrado ($\\chi^2$) é dada pela fórmula:\n",
    "\n",
    "$\\chi^2 = \\sum\\limits_{s=1}^n \\frac{(Y_s - np_s)^2}{np_s}$\n",
    "\n",
    "Onde $Y_s$ é a quantidade observada de valores na categoria $k=s$ e $p_s$ é a probabilidade conhecida de um valor da categoria $s$. Como bem observado por Knuth, essa fórmula pode ser simplificada para:\n",
    "\n",
    "$\\chi^2 = \\frac{1}{n} \\sum\\limits_{s=1}^n \\frac{Y_s^2}{p_s} - n$\n",
    "\n",
    "A biblioteca stats do Python possui a função chi-quadrado implementada (https://docs.scipy.org/doc/scipy/reference/generated/scipy.stats.chisquare.html). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Exercício: Pense em uma forma de aplicar o teste acima para saber \n",
    "# se a distribuição randint do Python é uma boa implementação."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}