viernes, 11 de mayo de 2018

Ejemplo de aplicación del algoritmo de multiplicación egipcio

A modo de ejemplo, vamos a calcular el producto $45\cdot 98$, para ello confeccionaremos una tabla con dos columnas; en la primera escribiremos las sucesivas potencias de $2$ ( empezando por $2^0=1$) y en la segunda la sucesión geométrica de razón $2$ cuyo primer término sea el segundo factor:

1  |   98
 2  |  196
 4  |  392
 8  |  784
16  | 1568
32  | 3136
.   |   .
.   |   .
.   |   .


A continuación, expresaremos el primer factor como suma de potencias de base $2$ ( los números de la primera columna ) y seleccionaremos las filas en las que se encuentran. Sumando, finalmente, los números de la segunda columna que estén en esas mismas filas, llegando así al resultado de la multiplicación pedida.

Para saber qué números de la primera columna intervienen como sumandos del número $45$ ( siendo éstos potencias de base $2$ ) escribiremos $45$ en la base de numeración $2$ ( binaria ), dividiendo sucesivamente por $2$ el número y los cocientes que se van obteniendo hasta llegar a una división con resto $0$; los números así obtenidos, incluyendo el cociente de la última división, y dispuestos en orden, comenzando con el cociente de la última división y acabando con el resto de la primera, son los coeficientes del desarrollo en serie de $45$ en suma de términos de potencias de base $2$, esto es,
$45_{(10)}=101101_{(2)}$, luego
$45=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+1\cdot 2^3+0\cdot 2^4+1\cdot 2^5$
            $=1+4+8+32$

Así pues, seleccionando los números de la segunda columna con los que se emparejan:
 1  |   98 | x
 2  |  196 |
 4  |  392 | x
 8  |  784 | x
16  | 1568 |
32  | 3136 | x
obtenemos, como resultado de la multiplicación pedida el siguiente resultado: $$98+392+784+3136 = 4410$$
$\square$

jueves, 10 de mayo de 2018

Expresando un número entero no negativo como suma de potencias de base 2

ENUNCIADO. Expresar el número $493$ como una suma de potencias de base $2$

SOLUCIÓN. $496_{(10)}=11101101_{(2)}$, luego
$493=1\cdot 2^0+0\cdot 2^1+1\cdot 2^2+1\cdot 2^3+0\cdot 2^4+1\cdot 2^5+1\cdot 2^6+1\cdot 2^7+1\cdot 2^8$
            $=1+0+4+8+0+32+64+128+256$

$\square$

Algoritmo de la multiplicación rusa. Un ejemplo

Realícese la multiplicación $45\cdot 98$ empleando el algoritmo 'ruso'

procedimiento multiplicación_rusa(a,b)
inicio
{
 i:=1;
 a_i:=a;
 b_i:=b;
 p:=0;
 mientras a_i!=1 hacer
  {
   i:=i+1;
   a_i:=entero_por_defecto(a_i/2);
   b_i:=2·b_i
   si resto(a_i div 2 ) != 0, p:=p+b_i
  }
 escribir('a·b=',p);
}
fin

Ejemplo de implementación:

% multiplicación_rusa(45,98)
salida:
->  45·98=4410

Proceso paso a paso:
------------------------------------------------------------------
  i  |  a_i    | ¿ a_i es impar ?   |   b_i   |  si a_i es impar
     |         |                    |         |   acumula suma de
     |         |                    |         |   b_i  
------------------------------------------------------------------
  1  |  45     |      sí            |    98   |       98
------------------------------------------------------------------
  2  |  22     |      no            |   196   |       98
------------------------------------------------------------------
  3  |  11     |      sí            |   392   |   98+392=490
------------------------------------------------------------------
  4  |   5     |      sí            |   784   |  490+784=1274
------------------------------------------------------------------
  5  |   2     |      no            |  1568   |      1274
------------------------------------------------------------------
  6  |   1     |      sí            |  3136   | 1274+3136=4410
------------------------------------------------------------------

$\square$

lunes, 2 de abril de 2018

Un ejemplo de código de detección de error: la letra del NIF

Habréis reparado en el último símbolo del NIF, que, a excepción de los ocho números a su izquierda, es una letra. Ésta responde a una asociación del resto de dividir el número de ocho cifras entre $23$ y sirve para comprobar que no se ha producido ningún error al facilitar el documento en una operación administrativa; si la letra facilitada junto con las ocho cifras no coincidiese con la que debe ser según la que le corresponde de acuerdo al resto ( por haber dado mal una de las cifras), sin duda se pondria de manifiesto el error, al obtener una letra distinta a la consignada. Las letras asociadas a los distintos restos son las siguientes:
-----------
Resto|Letra
-----------
  0  |  T 
  1  |  R
  2  |  W
  3  |  A 
  4  |  G 
  5  |  M 
  6  |  Y
  7  |  F 
  8  |  P 
  9  |  D 
 10  |  X 
 11  |  B 
 12  |  N
 13  |  J 
 14  |  Z
 15  |  S
 16  |  Q
 17  |  V
 18  |  H
 19  |  L
 20  |  C
 21  |  K
 22  |  E 
Así por ejemplo el NIF 789 260 31 J es correcto, pues el resto de la división $789 260 31 \div 23$ es $13$ y, según la tabla, la letra asociada es, efectivamente, la J; sin embargo, el 671 943 11 Q sería incorrecto ya que $671 943 11 \div 23$ es $18$, luego, de acuerdo con la tabla, no le corresponde la letra Q sino la H.
$\square$

martes, 13 de marzo de 2018

Demostración china del teorema de Pitágoras

La demostración que vamos a ver parece ser que proviene de China, y es anterior a la demostración que aparece en los Elementos de Euclides. En su versión original se trataria de recomponer en cuadrado en cuatro triángulos rectángulos iguales y un cuadrado más pequeño, a la usanza del clásico juego del Tangram. Sea un triángulo rectángulo, como el de la figura 3. Vamos a justificar que la longitud de la hipotenusa elevada al cuadrado es igual a la suma de los cuadrados de las longitudes de los catetos, esto es, y tal como se han designado los lados del triángulo rectángulo, se tiene que $$a^2=b^2+c^2 \quad \quad (1)$$

Veamos la razón de ésto. Fijémonos en la figura 1. El lado del cuadrado mayor, tiene una longitud igual a $b+c$, luego su área es igual a $(b+c)^2$; ahora bien, como este cuadrado se descompone en un cuadrado cuyo lado tiene longitud $a$ y cuatro triángulos rectángulos iguales de catetos, de longitudes respectivas $b$ y $c$, podemos escribir que $$(b+c)^2=a^2+4\cdot \dfrac{b\,c}{2}$$

Fijémonos ahora en la figura 2. Se trata del mismo cuadrado cuyo lado tiene longitud $b+c$; sin embargo, vemos ahora otra descomposición del mismo en dos cuadrados y dos rectángulos iguales, así pues $$(b+c)^2=b^2+c^2+2\, b\,c$$ que es el primer miembro de (1), luego se desprende de ellos que $$b^2+c^2+2\, b\,c= a^2+4\cdot \dfrac{b\,c}{2}$$ esto es $$b^2+c^2+2\, b\,c= a^2+2\,b\,c$$ y simplificando, llegamos a $$b^2+c^2=a^2$$, como queríamos demostrar. Ésta es la relación que liga los dos catetos con la hipotenusa de la figura 3.


Ejemplo de aplicación del teorema de Pitágoras.
ENUNCIADO. Sea un triángulo rectángulo cuyos catetos miden $6$ y $8$ decímetros, respectivamente. ¿ Calcúlese la longitud de la hipotenusa ?
SOLUCIÓN. Llamemos $x$ a la longitud de la hipotenusa, que queremos calcular. Según lo que acabamos de justificar, podemos escribir que $x^2=6^2+8^2$, esto es $x^2=36+64$, y por tanto $x^2=100$. Y como $100=10\cdot 10$, se desprende de ello que $x=10$ decímetros.

Observación 1. Toda terna de números enteros positivos no nulos $(a,b,c)$, con la que se cumpla el teorema de Pitágoras, se dice que es una terna pitagórica. Otra terna pitagóricas es $(3,4,5)$, ¿ te animas a buscar más ? ¿ cuántas habrá ?.

Observación 2. Los antiguos egipcios utilizaban cuerdas con nudos consecutivos equidistantes para escuadrar dos rectas en las parcelaciones y construcciones; para ello, les bastaba con seleccionar una terna pitagórica con los números de espacios entre nudos consecutivos de la cuerda, por ejemplo escogiendo un conjunto de $3$, $4$ y $5$ espacios entre nudos ( consecutivos y equidistantes ).

$\square$