Multiplicar sin multiplicar [cerrado]

8

Escriba el algoritmo de multiplicación más rápido (mejor big-O) y más pequeño para enteros positivos, sin usar operadores de multiplicación. Solo se permiten sumas, restas, funciones lógicas (AND, OR, XOR, NOT), desplazamiento de bits, rotación de bits, giro / ajuste / limpieza de bits y prueba de bits. Su programa debe ser capaz de multiplicar números de 16 bits para producir un resultado de 32 bits. Tome la entrada en stdin, separada por comas, espacios o nuevas líneas (su elección), pero deje en claro cómo ingresar los datos.

Ejemplo de entrada / salida:

734 929
681886
Thomas O
fuente
1
¿Qué pasa con el operador de división?
st0le
3
¿Es este codegolf o un desafío? : - \
st0le
44
Los más pequeños O más rápidos : no puede tener ambos, o necesita un formulario de traducción para calcular la compensación.
usuario desconocido
3
Marqué para cerrar como "no es una pregunta real", ya que todavía no se ha dado una solución, cómo comparar el código más rápido y el más corto. ¿Cuál es de prioridad? ¿O en qué relación es el intercambio? Podría curarse si se proporcionara algo de comparación en un idioma portátil, por ejemplo: si el std-algo alcanza las operaciones de 500k en C y su algo alcanza los 50k, debe multiplicar la longitud del código * 10. De esa forma, todos podrían elegir acortar el código o hacerlo más rápido. El ganador no necesita ser ganador en ambas categorías, pero el criterio ganador sería mucho más objetivo.
usuario desconocido
2
Esta pregunta es una locura como se dijo. El algoritmo de multiplicación conocido asintóticamente más rápido para enteros positivos es el algoritmo de Fürer ( en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm ) y es ridículamente complejo y tomaría miles de líneas para implementarse en cualquier idioma. Supongo que en realidad solo significa que su algoritmo tiene que ser O (n ^ 2) (multiplicación larga).
D Coetzee

Respuestas:

11

C, 84 83 78 caracteres

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

En una forma más legible

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

El algoritmo se conoce mejor como Multiplicación etíope o Multiplicación campesina rusa. Aquí está el algoritmo:

  1. Deje que los dos números que se multiplicarán sean a y b.
  2. Si a es cero, entonces rompa e imprima el resultado.
  3. Si a es impar, agregue b al resultado.
  4. La mitad a, doble b. Ir al paso 2.
fR0DDY
fuente
no funciona sin inicializar m=0(al menos para mí)
st0le
@ st0le Funcionará ahora, he movido 'm' para comenzar en la función principal. Ver aquí: ideone.com/XCz8C
fR0DDY
Olvidé este, aquí hay uno más corto for(;(a&1&&m+=b)|a;a>>=1,b<<=1);Sí, estoy muy avergonzado. :)
st0le
for(m=0;(a&1&&m+=b)|a;a/=2,b*=2);por qué usar shift, ¿verdad?
st0le
2
@ fR0DDY: se podría decir en b+=blugar de b*=2. Por supuesto, aún necesitará el cambio correcto.
Joey Adams
7

APL (5)

Toma entrada en entrada estándar separada por nuevas líneas.

+/⎕⍴⎕
marinus
fuente
5

Golfscript - 12 caracteres

~0\{1$+}*\;

Tenga en cuenta que *aquí no está el operador de multiplicación, en cambio es un operador de repetición, vea el segundo uso aquí .

Juan
fuente
4

Golfscript - 27 caracteres

La multiplicación de los campesinos. Hay primero * allí es una multiplicación, pero sólo por 0 o 1

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

Aquí hay 31 caracteres que no se multiplican en absoluto

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

Python, 64 caracteres

Sin embargo, probablemente no sea el más eficiente (o el más compatible, pero estoy "agregando", ¿no?):

a=int(raw_input())
print sum(a for i in range(int(raw_input())))
Taylor Scott
fuente
77
Puede usar input()en lugar de int(raw_input())guardar 18 caracteres. Puede considerar esta trampa, pero print sum([input()]*input())también funciona ( *se usa para la repetición, no para la multiplicación).
James
r=input;a=r();print sum(map(lambda x:a,range(r())))es mucho más corto
Joel Cornett
@JoelCornett r=input;a=r();r(sum(a for b in range(r())))es aún más corto (43 frente a 51 bytes)
FatalError
2

Golfscript - 43

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

Implementación de la multiplicación campesina . Creo que más adelante podré jugar al golf.

Juan
fuente
2

J, 18 17 caracteres

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

La entrada debe estar separada por espacios.

Gareth
fuente
2

Python, también 64 caracteres

m=lambda x,n:0 if n==0 else x+m(x,n-1);print m(input(),input())
Doug T.
fuente
1
Puede acortarlo asignando i=inputy usandoi()
st0le
3
en realidad, eso es exactamente el mismo número de personajes
Doug T.
2
podría reemplazar 0 if n==0 elseconn and
recursivo
1

VBA, 70 caracteres

En realidad, esto es bastante lento para grandes cantidades, pero es pequeño. Logré mejorar el tamaño del código mientras mejoraba la velocidad. El tiempo de cálculo varía, dependiendo de la posición del argumento, no solo del tamaño. (es decir, 1000, 5000 calcula en aproximadamente 4 segundos, mientras que 5000, 1000 calcula en aproximadamente 19) Dado que el OP enumera tanto rápido como pequeño, pensé que iría con este. La entrada es dos argumentos numéricos, separados por comas.

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

Esta versión más larga ( 103 caracteres ) asegurará que se ejecute con el más rápido de los dos arreglos posibles:

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
Gaffi
fuente
Se puede perder un buen número de bytes mediante la eliminación de espacios en blanco antes Toy en la concatenación, así como por outputiing a la ventana inmediata a través de VBEDebug.?
Taylor de Scott
1

Perl: 52 caracteres

Esta es una vieja pregunta, pero Perl necesita ser representado:

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

(Este es el algoritmo binario; la suma iterada es más pequeña pero mucho demasiado aburrido.)

Este programa incluye una característica no intencional: si su línea de entrada contiene un tercer número, el programa realmente calculará A * B + C.

caja de pan
fuente
Que tan rapido es
usuario desconocido
Se ejecuta en O (log n), naturalmente. ¿Estás preguntando sobre su velocidad real? En mi máquina mido aproximadamente 2-3 veces más lento que el multiplicador incorporado de Perl, pero no sé cuán significativo es eso.
breadbox
1

Una variación en Scala, optimizada para el tamaño: 48 caracteres

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

optimizado para la velocidad un poco:

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

Cambio (a, b) if (a> b), para llegar al final más rápido. La diferencia es de 11 a 20 pasos, cuando se llama a mul (1023,31), en comparación con omitir esa línea de código.

Golfizado: 95 caracteres:

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)
usuario desconocido
fuente
1

K, 18 16

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

.

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

Ruby, 35 caracteres

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

Es un programa que toma entradas y salidas, no solo una función.

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

Ruby, 35 bytes

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

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

Probablemente podría acortarse si los números se leen desde ARGV, pero se queja de que tienen el formato incorrecto (cadenas, no ints). Cualquier sugerencia seria genial.

Señor llama
fuente
0

Mathematica 12

Los siguientes #2casos de sumas de #1.

Código

#1~Sum~{#2}&

Uso

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

(* out *)

681886


9 caracteres?

Si los parámetros del programa, a, b, se pueden utilizar para la entrada, el mismo resultado se puede lograr con 9 caracteres .

a~Sum~{b}
DavidC
fuente
0

VB11, 101 caracteres

   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)))
Adam Speight
fuente
1
Usaste
No creo que esto use operaciones no permitidas (a menos que se desactive el flujo de control; la pregunta no está clara al respecto, lo cual es parte de la razón por la que está en espera). "mod 2" es una operación de prueba de bits. Supongo que las comparaciones ( ==) no están permitidas por la pregunta, pero muchas respuestas las están usando.