On vous donne une machine 16 bits et on vous dit d'implémenter la multiplication d'entiers de taille arbitraire. Vos registres ne peuvent contenir que des nombres 16 bits, et la plus grande instruction de multiplication prend deux entrées 8 bits et génère un résultat 16 bits.

Votre programme doit prendre en entrée deux nombres positifs de taille arbitraire et sortir leur produit. Chaque numéro d'entrée est codé sur sa propre ligne comme un tableau d'octets petit-boutien où chaque octet est un nombre hexadécimal à 2 chiffres. La sortie doit être formatée de manière similaire. Peut-être mieux expliqué avec un exemple:

contribution

1f 4a 07
63 a3

production

fd 66 03 a7 04

qui code pour la multiplication 477727 * 41827 = 19981887229.

Vous pouvez supposer que le dernier octet (le plus significatif) de chaque numéro d'entrée est différent de zéro et que le dernier bloc du nombre que vous avez sorti doit être différent de zéro. Les deux numéros d'entrée auront une longueur maximale de 100 octets.

Le plus petit code gagne.

Rappelez-vous, la plus grande multiplication que vous êtes autorisé à utiliser est de 1 octet * 1 octet, et aucun type entier supérieur à 2 octets!

Perl, 137 caractères

($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

Avertissements

• Imprime parfois un 00octet supplémentaire à la fin du résultat. Bien sûr, le résultat est toujours correct, même avec cet octet supplémentaire.
• Imprime un espace supplémentaire après le dernier octet hexadécimal du résultat.

Explication

L'explication va être un peu longue, mais je pense que la plupart des gens ici trouveront cela intéressant.

Tout d'abord, quand j'avais 10 ans, on m'a appris le petit truc suivant. Vous pouvez multiplier deux nombres positifs avec ceci. Je vais décrire cela en utilisant l'exemple de 13 × 47. Vous commencez par écrire le premier nombre, 13, et en le divisant par 2 (arrondir à chaque fois) jusqu'à ce que vous atteigniez 1:

13
 6
 3
 1

Maintenant, à côté du 13, vous écrivez l'autre nombre, 47, et continuez à le multiplier par 2 le même nombre de fois:

13     47
 6     94
 3    188
 1    376

Maintenant, vous biffez toutes les lignes où le nombre sur la gauche est pair . Dans ce cas, ce n'est que le 6. (Je ne peux pas barrer dans le code, donc je vais juste le supprimer.) Enfin, vous ajoutez tous les chiffres restants à droite:

13     47
 3    188
 1    376
     ----
      611

Et c'est la bonne réponse. 13 × 47 = 611.

Maintenant, puisque vous êtes tous des geeks informatiques, vous aurez réalisé que ce que nous faisons réellement dans les colonnes de gauche et de droite est x >> 1et y << 1, respectivement. De plus, nous ajoutons le yseul if x & 1 == 1. Cela se traduit directement par un algorithme, que j'écrirai ici en pseudocode:

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

Nous pouvons réécrire le ifpour utiliser une multiplication, puis nous pouvons facilement le changer pour qu'il fonctionne octet par octet au lieu de bit par bit:

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

Cela contient toujours une multiplication avec y, qui est de taille arbitraire, nous devons donc aussi changer cela en boucle. Nous le ferons en Perl.

Maintenant, traduisez tout en Perl:

• $xet $ysont les entrées au format hexadécimal, donc elles ont d' abord l' octet le moins significatif .

• Ainsi, au lieu de x >> 8 moi $x =~ s/.. *//s. J'ai besoin de l'espace + étoile parce que le dernier octet pourrait ne pas avoir d'espace (pourrait utiliser l'espace + ?aussi). Cela place automatiquement l'octet supprimé ( x & 255) dans $&.

• y << 8est tout simplement $y = "00$y".

• Le resultest en fait un tableau numérique,@r . À la fin, chaque élément de @rcontient un octet de la réponse, mais à mi-chemin du calcul, il peut contenir plus d'un octet. Je vais vous prouver ci-dessous que chaque valeur ne dépasse jamais deux octets (16 bits) et que le résultat est toujours un octet à la fin.

Voici donc le code Perl démêlé et commenté:

# 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

Maintenant, pour la preuve que cela génère toujours des octets et que le calcul ne génère jamais de valeurs supérieures à deux octets. Je vais le prouver par induction sur la whileboucle:

• Le vide @rau début n'a clairement aucune valeur supérieure à 0xFF (car il ne contient aucune valeur). Ceci conclut le scénario de base.

• Maintenant, étant donné qu'il @rne contient que des octets uniques au début de chaquewhile itération:

  • La forboucle contient explicitement &=toutes les valeurs du tableau de résultats avec 255 sauf la dernière , nous n'avons donc qu'à regarder cette dernière.

  • Nous savons que nous supprimons toujours un seul octet $xet $y:

    • Par conséquent, $e*hexest une multiplication de deux valeurs à un octet, ce qui signifie qu'il est dans la plage0 — 0xFE01 .

    • Par l'hypothèse inductive, $r[$i]est un octet; est donc $s = $r[$i] += $e*hexdans la plage0 — 0xFF00 .

    • Par conséquent, $s >> 8est toujours un octet.

  • $yaugmente de plus 00à chaque itération de la whileboucle:

    • Par conséquent, à chaque itération de la whileboucle, la forboucle interne s'exécute pour une itération de plus que lors de l' whileitération précédente .

    • Par conséquent, la $r[++$i] += $s >> 8dans la dernière itération de la forboucle ajoute toujours $s >> 8à 0, et nous avons déjà établi que $s >> 8est toujours un octet.

  • Par conséquent, la dernière valeur stockée @rà la fin de la forboucle est également un octet unique.

Ceci conclut un défi merveilleux et passionnant. Merci beaucoup de l'avoir posté!

Solution C

Cette solution ne fait aucune validation d'entrée. Il n'est également que légèrement testé. La vitesse n'était pas vraiment une considération. La mémoire de Malloc, et n'est pas particulièrement intelligent sur combien il saisit. Garanti suffisant et plus que nécessaire.

m () accepte une chaîne, attend deux sauts de ligne dans la chaîne, un après chaque numéro. N'attend que des chiffres, des minuscules, des espaces et des retours à la ligne. S'attend à ce que les chiffres hexadécimaux soient toujours une paire.

Aucune opération de multiplication n'est jamais utilisée (sciemment). Le décalage est effectué sur des variables 8 bits. Un ajout de 16 bits est effectué. Aucun type de données 32 bits.

Rétréci à la main, et seulement légèrement. edit: plus d'obscurcissement, moins de caractères: D Compile avec des avertissements avec gcc.

Caractères: 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);}

Vous pouvez tester avec ceci:

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;
}

Résultat:

$ ./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 caractères

Un algorithme de multiplication d'écolier standard O (n * m). Notez que pour répondre aux exigences du défi, les opérations sont effectuées sur les octets de chaînes qui, dans OCaml, sont (commodément, dans ce cas) mutables. Notez également que l'accumulateur sne déborde jamais de 16 bits, car 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)))

Par exemple,

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

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

Essayez-le en ligne!

Beaucoup plus récent que cette époque