13

Você recebe uma máquina de 16 bits e é instruído a implementar a multiplicação de números inteiros de tamanho arbitrário. Seus registros podem conter apenas números de 16 bits, e a maior instrução de multiplicação usa duas entradas de 8 bits e gera um resultado de 16 bits.

Seu programa deve tomar como entrada dois números positivos de tamanho arbitrário e gerar o produto deles. Cada número de entrada é codificado em sua própria linha como uma matriz de bytes little-endian, em que cada byte é um número hexadecimal de 2 dígitos. A saída deve ser formatada de maneira semelhante. Talvez seja melhor explicado com um exemplo:

entrada

1f 4a 07
63 a3

resultado

fd 66 03 a7 04

que codifica a multiplicação 477727 * 41827 = 19981887229.

Você pode assumir que o último byte (mais significativo) de cada número de entrada é diferente de zero, e o último pedaço do número que você produz deve ser diferente de zero. Os dois números de entrada terão no máximo 100 bytes.

O menor código vence.

Lembre-se, a maior multiplicação que você tem permissão para usar é 1 byte * 1 byte, e nenhum tipo inteiro maior que 2 bytes!

code-golf math Keith Randall
fonte

Isso é crucial para idiomas que não possuem um tipo padrão de 8 bits, como Haskell.

FUZxxl

1

E a adição? Podemos fingir ter uma função de adição de tamanho arbitrário pronta? Se não, o que pode nos acrescentar?

Timwi #

@ Timwi: Você pode fazer o que quiser, 16 bits por vez. Adiciona, turnos, qualquer que seja. Qualquer operação maior que você precise se sintetizar.

Keith Randall

+1 para a ordem correta dos bytes

12Me21:

13

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

Ressalvas

Às vezes, imprime um 00byte extra no final do resultado. Obviamente, o resultado ainda está correto, mesmo com esse byte extra.
Imprime um espaço extra após o último hex byte no resultado.

Explicação

A explicação será um pouco longa, mas acho que a maioria das pessoas aqui achará interessante.

Antes de mais, quando eu tinha 10 anos, aprendi o pequeno truque a seguir. Você pode multiplicar quaisquer dois números positivos com isso. Descreverei isso usando o exemplo de 13 × 47. Comece escrevendo o primeiro número, 13 e dividindo -o por 2 (arredondar para baixo a cada vez) até chegar a 1:

Agora, ao lado dos 13, você escreve o outro número, 47, e continua multiplicando -o por 2 o mesmo número de vezes:

Agora você cruza todas as linhas em que o número à esquerda é par . Nesse caso, esse é apenas o 6. (Não consigo executar o código de correção, então vou removê-lo.) Finalmente, você adiciona todos os números restantes à direita:

E esta é a resposta certa. 13 × 47 = 611.

Agora, como todos vocês são viciados em computadores, perceberão que o que realmente estamos fazendo nas colunas esquerda e direita é x >> 1e y << 1, respectivamente. Além disso, adicionamos o yúnico se x & 1 == 1. Isso se traduz diretamente em um algoritmo, que escreverei aqui no 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 reescrever o ifpara usar uma multiplicação e, em seguida, podemos mudar isso facilmente para que funcione de byte a byte em vez de pouco a pouco:

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

Isso ainda contém uma multiplicação com ytamanho arbitrário, portanto, também precisamos mudar isso para um loop. Nós vamos fazer isso em Perl.

Agora traduza tudo para o Perl:

$xe $ysão as entradas no formato hexadecimal, para que tenham primeiro o byte menos significativo .
Assim, em vez de x >> 8eu faço $x =~ s/.. *//s. Eu preciso do espaço + estrela porque o último byte pode não ter espaço nele (também pode usar espaço + ?). Isso coloca automaticamente o byte removido ( x & 255) em $&.
y << 8é simplesmente $y = "00$y".
O resulté realmente uma matriz numérica @r,. No final, cada elemento de @rcontém um byte da resposta, mas, no meio do cálculo, pode conter mais de um byte. Vou provar a você abaixo que cada valor nunca é superior a dois bytes (16 bits) e que o resultado é sempre um byte no final.

Então, aqui está o código Perl desvendado e 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

Agora, a prova de que isso sempre gera bytes e que o cálculo nunca gera valores maiores que dois bytes. Vou provar isso por indução ao longo do whileloop:

O vazio @rno início claramente não possui valores maiores que 0xFF (porque não possui valores). Isso conclui o caso base.
Agora, dado que @rcontém apenas bytes únicos no início de cada whileiteração:
- O forloop explicitamente &=s todos os valores na matriz de resultados com 255, exceto o último , portanto, precisamos apenas olhar para esse último.
- Sabemos que sempre removemos apenas um byte $xe $y:
  - Portanto, $e*hexé uma multiplicação de dois valores de byte único, o que significa que está no intervalo 0 — 0xFE01.
  - Pela hipótese indutiva, $r[$i]é um byte; portanto, $s = $r[$i] += $e*hexestá no intervalo 0 — 0xFF00.
  - Portanto, $s >> 8é sempre um byte.
- $ycresce um extra 00em cada iteração do whileloop:
  - Portanto, em todas as iterações do whileloop, o forloop interno é executado por mais uma iteração do que na whileiteração anterior .
  - Portanto, o $r[++$i] += $s >> 8na última iteração do forloop de sempre adiciona $s >> 8a 0, e já estabeleceu que $s >> 8é sempre um byte.
- Portanto, o último valor armazenado no @rfinal do forloop também é um único byte.

Isso conclui um desafio maravilhoso e emocionante. Muito obrigado por publicá-lo!

Timwi
fonte

4

Solução C

Esta solução não faz validação de entrada. Também é apenas levemente testado. Velocidade não era realmente uma consideração. A memória de Malloc, e não é particularmente inteligente sobre o quanto ela agarra. Garantido o suficiente e mais do que o necessário.

m () aceita uma string, espera duas novas linhas na string, uma após cada número. Espera apenas números, caracteres minúsculos, espaços e novas linhas. Espera que os dígitos hexadecimais sejam sempre um par.

Nenhuma operação de multiplicação é usada (conscientemente). A troca é realizada em variáveis de 8 bits. Uma adição de 16 bits é realizada. Não há tipos de dados de 32 bits.

Encolhido à mão, e apenas levemente. edit: mais ofuscação, menos caracteres: D Compila com avisos com o gcc.

Personagens: 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);}

Você pode testar com isso:

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

mrmekon
fonte

3

OCaml + Baterias, 362 caracteres

Um algoritmo de multiplicação de aluno O (n * m) padrão. Observe que, para atender aos requisitos de desafio, as operações são realizadas nos bytes de strings, que no OCaml são (convenientemente, neste caso) mutáveis. Observe também que o acumulador snunca excede 16 bits, pois 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 exemplo,

# 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"

Matías Giovannini
fonte

0

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))

Experimente online!

Idioma muito mais recente que o da época

l4m2
fonte

Multiplicação longa, 8 bits por vez

Respostas:

Perl, 137 caracteres

Ressalvas

Explicação

OCaml + Baterias, 362 caracteres

JavaScript (Node.js) , 160 bytes