Schreiben Sie den schnellsten (besten Big-O) und kleinsten Multiplikationsalgorithmus für positive ganze Zahlen, ohne Multiplikationsoperatoren zu verwenden. Sie dürfen nur Addition, Subtraktion, logische Funktionen (UND, ODER, XOR, NICHT), Bitverschiebung, Bitdrehung, Bit-Flip / Set / Clear und Bittest durchführen. Ihr Programm sollte in der Lage sein, 16-Bit-Zahlen zu multiplizieren, um ein 32-Bit-Ergebnis zu erzielen. Nehmen Sie Eingaben in stdin vor, getrennt durch Kommas, Leerzeichen oder neue Zeilen (nach Ihrer Wahl), aber machen Sie deutlich, wie die Daten eingegeben werden sollen.

Beispiel für eine Ein- / Ausgabe:

734 929
681886

C, 84 83 78 Zeichen

m;main(a,b){for(scanf("%d%d",&a,&b);a;b+=b)a&1?m+=b:0,a>>=1;printf("%d\n",m);}

In einer besser lesbaren Form

m;main(a,b)
{
    scanf("%d%d",&a,&b);
    while (a)
    {
        if (a&1)
           m+=b;
        a>>=1;
        b+=b;
    }
    printf("%d\n",m);
}

Der Algorithmus ist besser bekannt als die äthiopische Multiplikation oder die russische Bauernmultiplikation. Hier ist der Algorithmus:

1. Die beiden zu multiplizierenden Zahlen seien a und b.
2. Wenn a Null ist, brechen Sie und drucken Sie das Ergebnis.
3. Wenn a ungerade ist, addiere b zum Ergebnis.
4. Halb a, Doppel b. Weiter zu Schritt 2.

APL (5)

Übernimmt Eingaben für Standardeingaben, die durch Zeilenumbrüche getrennt sind.

+/⎕⍴⎕

Golfscript - 12 Zeichen

~0\{1$+}*\;

Bitte beachten Sie, dass *hier nicht der Multiplikationsoperator, sondern ein Wiederholungsoperator ist, siehe die zweite Verwendung hier .

Golfscript - 27 Zeichen

Bauernvermehrung. Dort zuerst * gibt es eine Multiplikation, aber nur mit 0 oder 1

~2base-1%{1&\..+\@*}%{+}*\;

Hier ist bei 31 Zeichen, die sich überhaupt nicht multiplizieren

~2base-1%{1&\..+\[0\]@=}%{+}*\;

Python, 64 Zeichen

Wahrscheinlich nicht die effizienteste (oder die konformste, aber ich "füge hinzu", nicht wahr?):

a=int(raw_input())
print sum(a for i in range(int(raw_input())))

Ruby, 30

->(a){Array.new(*a).inject:+}

Basierend auf der GigaWat-Antwort .

Golfscript - 43

~\:@;0 1{.3$&{\@+\}{}if@@+:@;.+.3$>!}do;\;

Umsetzung der Bauernvermehrung . Ich denke, ich kann später vielleicht noch mehr Golf spielen.

J, 18 17 Zeichen

+/({.${:)".1!:1]3

Die Eingabe muss durch Leerzeichen getrennt werden.

Python, auch 64 Zeichen

m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())

VBA, 70 Zeichen

Dies ist für große Zahlen eigentlich ziemlich langsam, aber es ist klein. Ich habe es geschafft, die Codegröße zu verbessern und gleichzeitig die Geschwindigkeit zu verbessern. Die Berechnungszeit variiert je nach Position des Arguments - nicht nur der Größe. (dh 1000, 5000 werden in ungefähr 4 Sekunden berechnet, während 5000, 1000 in ungefähr 19 Sekunden berechnet werden.) Da das OP sowohl schnell als auch klein auflistet, dachte ich, ich würde mit diesem gehen. Die Eingabe besteht aus zwei numerischen Argumenten, die durch Kommas getrennt sind.

Sub i(j,k)
For m=1 To j:n=n & String(k," "):Next
MsgBox Len(n)
End Sub

Diese längere Version ( 103 Zeichen ) stellt sicher, dass sie mit der schnelleren der beiden möglichen Anordnungen ausgeführt wird:

Sub i(j,k)
If j<k Then a=j:b=k Else b=j:a=k
For m=1 To a:n=n & String(b," "):Next
MsgBox Len(n)
End Sub

Perl: 52 Zeichen

Dies ist eine alte Frage, aber Perl muss vertreten sein:

perl -pl '($m,$n,$_)=split;$_+=$m&1&&$n,$m>>=1,$n<<=1while$m'

(Dies ist der binäre Algorithmus; iterierter hinaus ist kleiner , aber Art und Weise zu langweilig.)

Dieses Programm enthält eine unbeabsichtigte Funktion: Wenn Ihre Eingabezeile eine dritte Zahl enthält, berechnet das Programm tatsächlich A * B + C.

Eine Variation in Scala, optimiert für Größe: 48 Zeichen

def m(a:Int,b:Int):Int=if(b==1)a else a+m(a,b-1)

ein bisschen auf Geschwindigkeit optimiert:

def mul (a:Int, b:Int) : Int = {
  print (".")
  if (a == 1) b
  else if (a > b) mul (b, a)
  else if (a % 2 == 0) mul (a >> 1, b << 1) 
  else b + mul (a - 1, b) 
}

Ich tausche (a, b) wenn (a> b), um das Ende schneller zu erreichen. Der Unterschied beträgt 11 bis 20 Schritte beim Aufrufen von mul (1023,31), verglichen mit dem Weglassen dieser Codezeile.

Golf: 95 Zeichen:

def m(a:Int,b:Int):Int=if(a==1)b
else if(a>b)m(b,a)
else if(a%2==0)m(a>>1,b<<1)
else b+m(a-1,b)

K, 18 16

{#,/(!y),\:/:!x}

.

k){#,/(!y),\:/:!x}[4;20]
80
k){#,/(!y),\:/:!x}[13;21]
273
k){#,/(!y),\:/:!x}[3;6]
18

Ruby, 35 Zeichen

p $*.map!(&:to_i).pop*$*.inject(:+)

Es ist ein Programm , das Ein- und Ausgänge übernimmt, nicht nur eine Funktion.

.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> wc -c golf.rb         
35 golf.rb
.-(~/virt)-----------------------------------------------------------------------------------------------------------------------------------------------------(ice@distantstar)-
`--> ruby ./golf.rb 734 929
681886

Ruby, 35 Bytes

def x(a)Array.new(*a).inject :+end

Verwendungszweck: x([123, 456]) #=> 56088

Könnte wahrscheinlich verkürzt werden, wenn die Zahlen aus ARGV gelesen werden, aber es wird beanstandet, dass sie das falsche Format haben (Zeichenfolgen, keine Ints). Irgendwelche Vorschläge wären toll.

Mathematica 12

Die folgenden Summeninstanzen #2von #1.

Code

#1~Sum~{#2}&

Verwendungszweck

#1~Sum~{#2} &[734, 929]

(* out *)

681886

9 Zeichen?

Wenn Programmparameter a, bfür die Eingabe verwendet werden kann, kann das gleiche Ergebnis erreicht werden durch 9 Zeichen .

a~Sum~{b}

VB11, 101 Zeichen

   Dim m As Func(Of Integer, Integer, Integer, Integer) = Function(a, b, t) If(a = 0, t, m(a >> 1, b << 1, t + If(a Mod 2 = 1, b, 0)))