Otrzymujesz 16-bitową maszynę i każesz zaimplementować mnożenie liczb całkowitych o dowolnym rozmiarze. W twoich rejestrach mogą znajdować się tylko 16-bitowe liczby, a największa instrukcja mnożenia pobiera dwa 8-bitowe wejścia i generuje 16-bitowy wynik.

Twój program musi przyjąć jako dane wejściowe dwie liczby dodatnie o dowolnej wielkości i wygenerować swój produkt. Każda liczba wejściowa jest kodowana w osobnym wierszu jako tablica bajtów little-endian, gdzie każdy bajt jest 2-cyfrową liczbą szesnastkową. Dane wyjściowe muszą być podobnie sformatowane. Być może najlepiej wyjaśnione przykładem:

Wejście

1f 4a 07
63 a3

wynik

fd 66 03 a7 04

który koduje mnożenie 477727 * 41827 = 19981887229.

Możesz założyć, że ostatni (najbardziej znaczący) bajt każdej liczby wejściowej jest niezerowy, a ostatni fragment liczby, którą wypisujesz, musi być niezerowy. Obie liczby wejściowe będą miały maksymalnie 100 bajtów.

Najmniejszy kod wygrywa.

Pamiętaj, że największy mnożnik, jaki możesz użyć, to 1 bajt * 1 bajt i żadne typy całkowite nie są większe niż 2 bajty!

Perl, 137 znaków

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

Ostrzeżenia

• Czasami drukuje dodatkowy 00bajt na końcu wyniku. Oczywiście wynik jest nadal poprawny, nawet z tym dodatkowym bajtem.
• Drukuje dodatkową spację po ostatnim bajcie szesnastkowym w wyniku.

Wyjaśnienie

Wyjaśnienie to będzie trochę długie, ale myślę, że większość ludzi uzna to za interesujące.

Po pierwsze, kiedy miałem 10 lat, nauczyłem się następującej małej sztuczki. Możesz pomnożyć przez to dowolne dwie liczby dodatnie. Opiszę to na przykładzie 13 × 47. Zaczynasz od napisania pierwszej liczby, 13, i podzielenia jej przez 2 (za każdym razem zaokrąglaj w dół), aż osiągniesz 1:

13
 6
 3
 1

Teraz, obok 13, napisz drugą liczbę, 47, i mnoż ją przez 2 tyle samo:

13     47
 6     94
 3    188
 1    376

Teraz wykreślisz wszystkie linie, w których liczba po lewej jest parzysta . W tym przypadku jest to tylko 6. (Nie mogę przekreślić kodu, więc po prostu go usunę). Na koniec dodajesz wszystkie pozostałe liczby po prawej stronie:

13     47
 3    188
 1    376
     ----
      611

I to jest właściwa odpowiedź. 13 × 47 = 611.

Teraz, ponieważ wszyscy jesteście maniaków komputerowych, będziesz sobie sprawę, że to, co my właściwie robi w lewej i prawej kolumny jest x >> 1i y << 1, odpowiednio. Ponadto dodajemy ytylko jeśli x & 1 == 1. To przekłada się bezpośrednio na algorytm, który napiszę tutaj w pseudokodzie:

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

Możemy ponownie napisać, ifaby użyć mnożenia, a następnie możemy łatwo to zmienić, aby działało na zasadzie bajt po bajcie zamiast bit po bicie:

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

To wciąż zawiera mnożenie y, które ma dowolny rozmiar, więc musimy też zmienić to w pętlę. Zrobimy to w Perlu.

Teraz przetłumacz wszystko na Perla:

• $xi $ysą nakłady w formacie hex, więc mają one najmniejszy bajt pierwszy .

• Dlatego zamiast tego x >> 8robię $x =~ s/.. *//s. Potrzebuję spacji + gwiazdy, ponieważ ostatni bajt może nie mieć na nim spacji (mógłby użyć spacji + ?). To automatycznie wstawia usunięty byte ( x & 255) do $&.

• y << 8jest po prostu $y = "00$y".

• resultJest rzeczywiście tablica liczbowa @r. Na koniec każdy element @rzawiera jeden bajt odpowiedzi, ale w połowie obliczeń może zawierać więcej niż jeden bajt. Udowodnię ci poniżej, że każda wartość nigdy nie jest większa niż dwa bajty (16 bitów) i że wynik jest zawsze jeden bajt na końcu.

Oto kod Perla rozwiązany i skomentowany:

# 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

Teraz dowód, że to zawsze generuje bajty i że obliczenia nigdy nie generują wartości większych niż dwa bajty. Udowodnię to przez indukcję w whilepętli:

• Pusty @rna początku wyraźnie nie ma w nim wartości większych niż 0xFF (ponieważ nie ma w nim żadnych wartości). To kończy przypadek podstawowy.

• Teraz, biorąc pod uwagę, że @rzawiera tylko pojedyncze bajty na początku każdej whileiteracji:

  • forPętla wyraźnie &=s wszystkie wartości w tablicy wynikowej z 255 wyjątkiem ostatniego , więc tylko trzeba spojrzeć na tego ostatniego.

  • Wiemy, że zawsze usuwamy tylko jeden bajt $xi $y:

    • Dlatego $e*hexjest mnożeniem dwóch jednobajtowych wartości, co oznacza, że ​​należy do zakresu 0 — 0xFE01.

    • Zgodnie z hipotezą indukcyjną $r[$i]jest jeden bajt; dlatego $s = $r[$i] += $e*hexjest w zakresie 0 — 0xFF00.

    • Dlatego $s >> 8zawsze ma jeden bajt.

  • $yrośnie 00w każdej iteracji whilepętli:

    • Dlatego w każdej iteracji whilepętli wewnętrzna forpętla działa o jeszcze jedną iterację niż w poprzedniej whileiteracji.

    • Dlatego $r[++$i] += $s >> 8w ostatniej iteracji forpętli zawsze dodaje $s >> 8się 0i już ustaliliśmy, że $s >> 8zawsze jest to jeden bajt.

  • Dlatego ostatnia wartość przechowywana @rna końcu forpętli jest również pojedynczym bajtem.

To kończy wspaniałe i ekscytujące wyzwanie. Wielkie dzięki za opublikowanie go!

Rozwiązanie C.

To rozwiązanie nie sprawdza poprawności danych wejściowych. Jest również tylko lekko przetestowany. Prędkość nie była tak naprawdę brana pod uwagę. Pamięć Malloca i nie jest szczególnie sprytna w kwestii tego, jak bardzo ją chwyta. Gwarantuje, że wystarczy i więcej niż to konieczne.

m () akceptuje ciąg znaków, oczekuje dwóch znaków nowego wiersza, jeden po każdym numerze. Oczekuje tylko liczb, małych liter, spacji i znaków nowej linii. Oczekuje, że cyfry szesnastkowe zawsze będą parą.

Żadna operacja zwielokrotniania nie jest nigdy używana (świadomie). Przesunięcie jest wykonywane na zmiennych 8-bitowych. Przeprowadzane jest jedno 16-bitowe dodawanie. Brak 32-bitowych typów danych.

Zmniejszone ręcznie i tylko delikatnie. edycja: więcej zaciemnienia, mniej znaków: D Kompiluje z ostrzeżeniami z gcc.

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

Możesz to przetestować:

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

Wynik:

$ ./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 + Baterie, 362 znaków

Standardowy algorytm mnożenia przez uczniów (n * m). Zauważ, że aby spełnić wymagania wyzwania, operacje są wykonywane na bajtach łańcuchów, które w OCaml są (dogodnie w tym przypadku) zmienne. Zauważ też, że akumulator snigdy nie przepełnia 16 bitów, ponieważ 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)))

Na przykład,

# 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 bajtów

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

Wypróbuj online!

Jednak dużo nowszy język niż ten czas