Sie erhalten eine 16-Bit-Maschine und müssen die Multiplikation von Ganzzahlen beliebiger Größe implementieren. Ihre Register können nur 16-Bit-Zahlen enthalten, und der größte Multiplikationsbefehl verwendet zwei 8-Bit-Eingänge und generiert ein 16-Bit-Ergebnis.

Ihr Programm muss zwei positive Zahlen beliebiger Größe als Eingabe verwenden und deren Produkt ausgeben. Jede Eingangsnummer wird in einer eigenen Zeile als Little-Endian-Byte-Array codiert, wobei jedes Byte eine zweistellige Hex-Zahl ist. Die Ausgabe muss ähnlich formatiert sein. Vielleicht am besten mit einem Beispiel erklärt:

Eingang

1f 4a 07
63 a3

Ausgabe

fd 66 03 a7 04

Dies codiert die Multiplikation 477727 * 41827 = 19981887229.

Sie können davon ausgehen, dass das letzte (höchstwertige) Byte jeder Eingabenummer ungleich Null ist und der letzte Teil der von Ihnen ausgegebenen Nummer ungleich Null sein muss. Beide Eingabenummern sind höchstens 100 Byte lang.

Kleinster Code gewinnt.

Denken Sie daran, dass die größte Multiplikation, die Sie verwenden dürfen, 1 Byte * 1 Byte und keine Integer-Typen größer als 2 Byte ist!

Perl, 137 Zeichen

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

Vorbehalte

• Druckt manchmal ein Extra 00 Byte am Ende des Ergebnisses aus. Natürlich ist das Ergebnis auch mit diesem zusätzlichen Byte noch korrekt.
• Gibt nach dem letzten Hex-Byte im Ergebnis ein zusätzliches Leerzeichen aus.

Erläuterung

Die Erklärung wird ein bisschen lang sein, aber ich denke, die meisten Leute hier werden es interessant finden.

Als ich 10 Jahre alt war, wurde mir zunächst der folgende kleine Trick beigebracht. Sie können damit zwei beliebige positive Zahlen multiplizieren. Ich beschreibe dies am Beispiel von 13 × 47. Sie schreiben zunächst die erste Zahl 13 und dividieren sie durch 2 (jeweils abrunden), bis Sie 1 erreichen:

13
 6
 3
 1

Nun schreiben Sie neben die 13 die andere Zahl 47 und multiplizieren sie immer wieder mit 2:

13     47
 6     94
 3    188
 1    376

Nun findet man alle Linien kreuzen, wo die Zahl auf der linken Seite ist sogar . In diesem Fall ist dies nur die 6. (Ich kann den Code nicht durchstreichen, daher entferne ich ihn einfach.) Zum Schluss fügen Sie alle verbleibenden Zahlen rechts hinzu:

13     47
 3    188
 1    376
     ----
      611

Und das ist die richtige Antwort. 13 × 47 = 611.

Jetzt, da Sie alle Computerfreaks sind, haben Sie gemerkt, dass wir in der linken und rechten Spalte jeweils x >> 1und tun y << 1. Darüber hinaus fügen wir die ynur wenn x & 1 == 1. Dies übersetzt sich direkt in einen Algorithmus, den ich hier in Pseudocode schreiben werde:

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

Wir können das umschreiben if, um eine Multiplikation zu verwenden, und dann können wir dies einfach so ändern, dass es byteweise statt bitweise funktioniert:

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

Dies enthält immer noch eine Multiplikation mit y, die eine beliebige Größe hat, also müssen wir diese auch in eine Schleife umwandeln. Das machen wir in Perl.

Übersetzen Sie jetzt alles in Perl:

• $xund $ysind die Eingaben im Hex-Format, so dass sie das niedrigstwertige Byte zuerst haben .

• Also, anstelle von x >> 8mir $x =~ s/.. *//s. Ich brauche das Leerzeichen + Stern, weil das letzte Byte möglicherweise kein Leerzeichen enthält (könnte auch Leerzeichen + verwenden ?). Dadurch wird das entfernte Byte ( x & 255) automatisch in eingefügt $&.

• y << 8ist einfach $y = "00$y".

• Das resultist tatsächlich ein numerisches Array @r. Am Ende @renthält jedes Element von ein Byte der Antwort, aber nach der Hälfte der Berechnung kann es mehr als ein Byte enthalten. Ich werde Ihnen im Folgenden beweisen, dass jeder Wert niemals mehr als zwei Bytes (16 Bits) beträgt und dass das Ergebnis immer ein Byte am Ende ist.

Also hier ist der Perl-Code entschlüsselt und kommentiert:

# 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

Nun zum Beweis, dass dies immer Bytes ausgibt und die Berechnung niemals Werte erzeugt, die größer als zwei Bytes sind. Ich werde dies durch Induktion über die whileSchleife beweisen :

• Das @rLeerzeichen am Anfang enthält eindeutig keine Werte größer als 0xFF (da es überhaupt keine Werte enthält). Damit ist der Basisfall abgeschlossen.

• Nun, da dies @rzu Beginn jeder whileIteration nur einzelne Bytes enthält :

  • Die forSchleife enthält explizit &=alle Werte im Ergebnis-Array mit 255, mit Ausnahme des letzten. Wir müssen uns also nur diesen letzten ansehen.

  • Wir wissen, dass wir immer nur ein Byte von $xund entfernen $y:

    • Daher $e*hexist eine Multiplikation von zwei Einzelbyte-Werten, was bedeutet, es liegt im Bereich 0 — 0xFE01.

    • Nach der induktiven Hypothese $r[$i]ist ein Byte; liegt daher $s = $r[$i] += $e*hexim bereich 0 — 0xFF00.

    • Daher $s >> 8ist immer ein Byte.

  • $ywächst ein Extra 00in jeder Iteration der whileSchleife:

    • Daher wird in jeder Iteration der whileSchleife die innere forSchleife eine Iteration länger ausgeführt als in der vorherigen whileIteration.

    • Daher addiert sich die $r[++$i] += $s >> 8in der letzten Iteration der forSchleife immer $s >> 8zu 0, und wir haben bereits festgestellt, dass dies $s >> 8immer ein Byte ist.

  • Daher ist der letzte @ram Ende der forSchleife gespeicherte Wert auch ein einzelnes Byte.

Dies schließt eine wunderbare und aufregende Herausforderung ab. Vielen Dank für die Veröffentlichung!

C Lösung

Diese Lösung führt keine Eingabevalidierung durch. Es ist auch nur wenig getestet. Geschwindigkeit war nicht wirklich eine Überlegung. Mallocs Gedächtnis, und es ist nicht besonders klug, wie viel es packt. Garantiert genug und mehr als nötig.

m () akzeptiert eine Zeichenfolge und erwartet zwei Zeilenumbrüche in der Zeichenfolge, einen nach jeder Zahl. Erwartet nur Zahlen, Kleinbuchstaben, Leerzeichen und Zeilenumbrüche. Erwartet, dass hexadezimale Ziffern immer ein Paar sind.

Es wird niemals (wissentlich) eine Multiplikationsoperation verwendet. Das Verschieben wird für 8-Bit-Variablen durchgeführt. Eine 16-Bit-Addition wird durchgeführt. Keine 32-Bit-Datentypen.

Von Hand geschrumpft und nur leicht. edit: mehr Verschleierung, weniger Zeichen: D Kompiliert mit Warnungen mit gcc.

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

Sie können damit testen:

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

Ergebnis:

$ ./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 + Batterien, 362 Zeichen

Ein standardmäßiger O (n * m) Schüler-Multiplikationsalgorithmus. Beachten Sie, dass zur Erfüllung der Herausforderungsanforderungen die Operationen an den Bytes von Zeichenfolgen ausgeführt werden, die in OCaml (in diesem Fall günstigerweise) veränderbar sind. Es ist auch zu beachten, dass der Akkumulator sniemals 16 Bits überläuft, da 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)))

Beispielsweise,

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

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

Probieren Sie es online!

Viel neuere Sprache als damals