Le dan una máquina de 16 bits y le dicen que implemente la multiplicación de enteros de tamaño arbitrario. Sus registros solo pueden contener números de 16 bits, y la instrucción de multiplicación más grande toma dos entradas de 8 bits y genera un resultado de 16 bits.

Su programa debe tomar como entrada dos números positivos de tamaño arbitrario y generar su producto. Cada número de entrada se codifica en su propia línea como una matriz de bytes little endian donde cada byte es un número hexadecimal de 2 dígitos. La salida debe tener un formato similar. Quizás mejor explicado con un ejemplo:

entrada

1f 4a 07
63 a3

salida

fd 66 03 a7 04

que codifica la multiplicación 477727 * 41827 = 19981887229.

Puede suponer que el último byte (el más significativo) de cada número de entrada es distinto de cero, y el último fragmento del número que genera debe ser distinto de cero. Ambos números de entrada tendrán como máximo 100 bytes de longitud.

El código más pequeño gana.

Recuerde, la multiplicación más grande que puede usar es 1 byte * 1 byte, ¡y no hay tipos enteros de más de 2 bytes!

Perl, 137 caracteres

($x,$y)=<>;while($x=~s/.. *//s){$e=hex$&;$i=0;$s=$r[$i]+=$e*hex,$r[$i]&=255,$r[++$i]+=$s>>8 for$y=~/.. */gs;$y="00$y"}printf'%02x 'x@r,@r

Advertencias

• A veces imprime un 00byte adicional al final del resultado. Por supuesto, el resultado sigue siendo correcto incluso con ese byte adicional.
• Imprime un espacio extra después del último byte hexadecimal en el resultado.

Explicación

La explicación va a ser un poco larga, pero creo que la mayoría de la gente aquí la encontrará interesante.

En primer lugar, cuando tenía 10 años, me enseñaron el siguiente truco. Puedes multiplicar dos números positivos con esto. Describiré esto usando el ejemplo de 13 × 47. Comienzas escribiendo el primer número, 13, y dividiéndolo entre 2 (redondeando hacia abajo cada vez) hasta llegar a 1:

13
 6
 3
 1

Ahora, al lado del 13, escribe el otro número, 47, y sigue multiplicándolo por 2 la misma cantidad de veces:

13     47
 6     94
 3    188
 1    376

Ahora tachas todas las líneas donde el número de la izquierda es par . En este caso, esto es solo el 6. (No puedo hacer tachado en el código, así que lo eliminaré). Finalmente, agrega todos los números restantes a la derecha:

13     47
 3    188
 1    376
     ----
      611

Y esta es la respuesta correcta. 13 × 47 = 611.

Ahora, como todos ustedes son geeks de la computadora, se habrán dado cuenta de que lo que realmente estamos haciendo en las columnas izquierda y derecha es x >> 1y y << 1, respectivamente. Además, agregamos el yúnico si x & 1 == 1. Esto se traduce directamente en un algoritmo, que escribiré aquí en pseudocódigo:

input x, y
result = 0
while x > 0:
    if x & 1 == 1:
        result = result + y
    x = x >> 1
    y = y << 1
print result

Podemos volver a escribir el ifpara usar una multiplicación, y luego podemos cambiar esto fácilmente para que funcione byte a byte en lugar de bit a bit:

input x, y
result = 0
while x > 0:
    result = result + (y * (x & 255))
    x = x >> 8
    y = y << 8
print result

Esto todavía contiene una multiplicación con y, que es de tamaño arbitrario, por lo que también debemos cambiar eso en un ciclo. Lo haremos en Perl.

Ahora traduzca todo a Perl:

• $xy $yson las entradas en formato hexadecimal, por lo que primero tienen el byte menos significativo .

• Por lo tanto, en lugar de lo x >> 8que hago $x =~ s/.. *//s. Necesito el espacio + estrella porque el último byte podría no tener espacio (también podría usar espacio + ?). Esto coloca automáticamente el byte eliminado ( x & 255) en $&.

• y << 8es simplemente $y = "00$y".

• La resultrealidad es una matriz numérica, @r. Al final, cada elemento @rcontiene un byte de la respuesta, pero a la mitad del cálculo puede contener más de un byte. Te demostraré a continuación que cada valor nunca tiene más de dos bytes (16 bits) y que el resultado es siempre un byte al final.

Así que aquí está el código Perl descifrado y comentado:

# Input x and y
($x, $y) = <>;

# Do the equivalent of $& = x & 255, x = x >> 8
while ($x =~ s/.. *//s)
{
    # Let e = x & 255
    $e = hex $&;

    # For every byte in y... (notice this sets $_ to each byte)
    $i = 0;
    for ($y =~ /.. */gs)
    {
        # Do the multiplication of two single-byte values.
        $s = $r[$i] += $e*hex,
        # Truncate the value in $r[$i] to one byte. The rest of it is still in $s
        $r[$i] &= 255,
        # Move to the next array item and add the carry there.
        $r[++$i] += $s >> 8
    }

    # Do the equivalent of y = y << 8
    $y = "00$y"
}

# Output the result in hex format.
printf '%02x ' x @r, @r

Ahora para la prueba de que esto siempre genera bytes , y que el cálculo nunca genera valores superiores a dos bytes. Lo probaré por inducción sobre el whilebucle:

• El vacío @ral principio claramente no tiene valores mayores que 0xFF (porque no tiene valores en absoluto). Esto concluye el caso base.

• Ahora, dado que @rcontiene solo bytes individuales al comienzo de cada whileiteración:

  • El forbucle explícitamente &=muestra todos los valores en la matriz de resultados con 255 excepto el último , por lo que solo tenemos que mirar ese último.

  • Sabemos que siempre eliminamos solo un byte $xy $y:

    • Por lo tanto, $e*hexes una multiplicación de dos valores de un solo byte, lo que significa que está en el rango 0 — 0xFE01.

    • Por la hipótesis inductiva, $r[$i]es un byte; por lo tanto, $s = $r[$i] += $e*hexestá en el rango 0 — 0xFF00.

    • Por lo tanto, $s >> 8siempre es un byte.

  • $ycrece un extra 00en cada iteración del whilebucle:

    • Por lo tanto, en cada iteración del whileciclo, el forciclo interno se ejecuta por una iteración más que en la whileiteración anterior .

    • Por lo tanto, $r[++$i] += $s >> 8en la última iteración del forbucle siempre se agrega $s >> 8a 0, y ya establecimos que $s >> 8siempre es un byte.

  • Por lo tanto, el último valor almacenado @ral final del forciclo también es un solo byte.

Esto concluye un desafío maravilloso y emocionante. ¡Muchas gracias por publicarlo!

Solución C

Esta solución no valida la entrada. También es solo ligeramente probado. La velocidad no era realmente una consideración. La memoria de Malloc, y no es particularmente inteligente sobre cuánto agarra. Garantizado para ser suficiente y más de lo necesario.

m () acepta una cadena, espera dos nuevas líneas en la cadena, una después de cada número. Solo espera números, caracteres en minúscula, espacios y líneas nuevas. Espera que los dígitos hexadecimales sean siempre un par.

No se utiliza ninguna operación de multiplicación (a sabiendas). El cambio se realiza en variables de 8 bits. Se realiza una adición de 16 bits. No hay tipos de datos de 32 bits.

Encogido a mano, y solo levemente. editar: más ofuscación, menos caracteres: D Compila con advertencias con gcc.

Caracteres: 675

typedef unsigned char u8;
#define x calloc
#define f for
#define l p++
#define E *p>57?*p-87:*p-48
#define g(a) --i;--a;continue
void m(u8*d){short n=0,m=0,a,b,i,k,s;u8*t,*q,*r,*p=d,o;f(;*p!=10;n++,l){}l;f(;*p
!=10;m++,l){}t=x(n,1);q=x(m,1);r=x(n,1);p=d;a=n;i=0;f(;*p!=10;i++,l){if(*p==32){
g(a);}t[i]=E;t[i]<<=4;l;t[i]|=E;}a/=2;b=m;i=0;l;f(;*p!=10;i++,l){if(*p==32){g(b)
;}q[i]=E;q[i]<<=4;l;q[i]|=E;}b/=2;f(k=0;k<8*b;k++){if(q[0]&1){o=0;f(i=0;i<n;i++)
{s=o+t[i]+r[i];o=s>>8;r[i]=s&255;}}f(i=n;i;i--){o=t[i-1]>>7&1;t[i-1]*=2;if(i!=n)
t[i]|=o;}f(i=0;i<m;i++){o=q[i]&1;q[i]/=2;if(i)q[i-1]|=(o<<7);}}k=(r[a+b-1]==0)?a
+b-1:b+a;f(i=0;i<k;i++){printf("%02x ",r[i]);}putchar(10);}

Puedes probar con esto:

int main(void){
  m("1f 4a 07\n63 a3\n");
  m("ff ff ff ff\nff ff ff ff\n");
  m("10 20 30 40\n50 60 70\n");
  m("01 02 03 04 05 06\n01 01 01\n");
  m("00 00 00 00 00 00 00 00 00 00 00 00 01\n00 00 00 00 00 00 00 00 02\n");
  return 0;
}

Resultado:

$ ./long 
fd 66 03 a7 04 
01 00 00 00 fe ff ff ff 
00 05 10 22 34 2d 1c 
01 03 06 09 0c 0f 0b 06 
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 02 

OCaml + Batteries, 362 caracteres

Un algoritmo estándar de multiplicación de colegial O (n * m). Tenga en cuenta que para cumplir con los requisitos de desafío, las operaciones se realizan en los bytes de las cadenas, que en OCaml son (convenientemente, en este caso) mutables. Tenga en cuenta también que el acumulador snunca desborda 16 bits, ya que 2 (2 ^ 8 - 1) + (2 ^ 8 - 1) ^ 2 = (2 ^ 8 - 1) (2 ^ 8 + 1) = 2 ^ 16 - 1 .

let(@)=List.map
let m a b=Char.(String.(let e s=of_list(((^)"0x"|-to_int|-chr)@nsplit s" ")in
let a,b=e a,e b in let m,n=length a,length b in let c=make(m+n)'\000'in
iteri(fun i d->let s,x=ref 0,code d in iteri(fun j e->let y=code e in
s:=!s+code c.[i+j]+x*y;c.[i+j]<-chr(!s mod
256);s:=!s/256)b;c.[i+n]<-chr!s)a;join" "((code|-Printf.sprintf"%02x")@to_list c)))

Por ejemplo,

# m "1f 4a 07" "63 a3" ;;
- : string = "fd 66 03 a7 04"

# m "ff ff ff ff" "ff ff ff ff" ;;
- : string = "01 00 00 00 fe ff ff ff"

JavaScript (Node.js) , 160 bytes

x=>y=>x.map((t,i)=>y.map(u=>(f=i=>(c=s[i]>>8)&&f(i++,s[i]=c+~~s[i],s[i-1]%=256))(i,s[i]=~~s[i++]+`0x${t}`*`0x${u}`)),s=[])&&s.map(t=>(t<16?0:'')+t.toString(16))

Pruébalo en línea!

Lenguaje mucho más nuevo que ese tiempo