Implementar división de precisión arbitraria

15

Implemente una función divide(int a, int b, int c)que imprima el valor base 10 de a/b. sin utilizar ningún cálculos de coma flotante ni BigInteger/ BigDecimalo bibliotecas equivalentes de ningún tipo. Se deben imprimir al menos ccaracteres precisos dentro del conjunto de 0123456789., excepto la (posible) excepción en el punto 4 a continuación.

  1. ay bpuede ser cualquier número entero de 32 bits. Actualización: si, para fines de golf, desea que la entrada sea primitiva de 64 bits, está bien, pero no necesita admitir todo el rango de datos de 64 bits.
  2. No necesita verificar que csea ​​positivo (aunque es de esperar que su programa no se bloquee) si no lo es.
  3. El límite superior mínimo admitido para ces 500. Está bien si su programa no admite valores de carriba 500, pero también está bien si lo hace.
  4. Para números que se dividen en partes iguales, usted elige si desea imprimir ceros adicionales (según el valor de c) o nada.
  5. No necesita poder utilizar la función para realizar otras tareas con el cociente, el único objetivo es imprimir.
  6. Para los números entre -1y 1, es su elección si imprime un encabezado 0. Sin embargo, este es el único escenario donde la impresión de un cero inicial es aceptable, y solo puede imprimir uno de esos cero.
  7. Puede usar cualquier lógica de redondeo / piso / techo que prefiera para el último decimal.
  8. Para una respuesta negativa, debe imprimir un encabezado -. Esto no cuenta para c. Sin embargo, es su elección si desea imprimir , +o nada por una respuesta positiva.
  9. La división entera y el módulo entero están permitidos. Sin embargo, tenga en cuenta que está restringido a primitivas, a menos que elija implementar su propia BigInteger/ BigDecimalbiblioteca que cuenta en función de la longitud de su código.
  10. No necesita manejar el bser 0, aunque puede hacerlo si lo desea. Su programa puede entrar en un bucle infinito o bloquearse si b=0no será penalizado.
  11. Ligero cambio de regla por comentario. Para asegurarse de que el campo de juego esté nivelado ay bgarantizado que sean enteros de 32 bits, puede usar enteros de 64 bits. Si su idioma elegido va más allá de los enteros de 64 bits como primitivo, en ningún momento puede usar esa funcionalidad (pretenda que tiene un límite de 64 bits).
  12. Otro punto que no está claro (sin embargo, no debería cambiar ninguna de las respuestas válidas actuales): aunque cpuede interpretarse como el número de caracteres impresos o el número de espacios después del decimal, su programa debe usar de calguna manera relevante para decidir cuántos caracteres imprimir. En otras palabras, divide(2,3,2)debería ser un resultado mucho más corto que divide(2,3,500); no está bien imprimir 500 caracteres sin tener en cuenta c.
  13. En realidad no me importa el nombre de la función. dEstá bien para fines de golf.

Entrada

stdinSe aceptan tanto una llamada de función como la lectura de . Si lees stdin, cualquier carácter que no esté en el conjunto [-0123456789]se considera un delimitador de argumento.

Salida

Caracteres a los stdoutdescritos anteriormente.

Ejemplo

para divide(2,3,5), todos los siguientes son resultados aceptables:

0.666
0.667
.6666
.6667
 0.666
 0.667
 .6666
 .6667
+0.666
+0.667
+.6666
+.6667

Otro ejemplo: para divide(371,3,5)lo siguiente son todos los resultados aceptables:

123.6
123.7
 123.6
 123.7
+123.6
+123.7
123.66666
123.66667
 123.66666
 123.66667
+123.66666
+123.66667

Y para divide(371,-3,5)lo siguiente son todos aceptables:

-123.6
-123.7
-123.66666
-123.66667
durron597
fuente
En aras de un campo de juego nivelado, podría ser aconsejable proporcionar una longitud de bits máxima específica que se pueda utilizar (primitiva o de otro tipo) a menos que ejecute su propia implementación más grande, porque a) en algunos idiomas la longitud de bits de las primitivas varía según la arquitectura subyacente yb) en algunos idiomas los tipos de números grandes son primitivos.
Jonathan Van Matre
@JonathanVanMatre Se agregó la regla 11 por su comentario
durron597
1
¿Cómo se cuentan los dígitos exactos ? En su ejemplo, veo tres o cuatro, pero nunca cinco, como lo indica el último argumento.
Howard
@Howard, si hicieras 92,3,5la respuesta sería, por ejemplo,30.67
durron597
1
por cierto 370/3 = 123.333 lol
izabera

Respuestas:

5

Java, 92/128

void d(long a,int b,int c){if(a<0^b<0){a=-a;p('-');}for(p(a/b+".");c>0;c--)p((a=a%b*10)/b);}<T>void p(T x){System.out.print(x);}

Tuve que improvisar para que ao bpudiera ser -2147483648 ya que los enteros positivos de 32 bits solo cuentan para 2147483647, por eso se aconvirtió en a long. Podría haber una mejor manera de manejar los resultados negativos, pero sé que ninguno ( doubles probablemente haría que esto funcione abs(a) < abs(b)como lo han hecho, -0pero solo el complemento de uno mantendría la precisión).

¿Por qué dos números de byte? Necesitaba 92 bytes para el cálculo y 36 para el asistente de impresión ( System.out.printapesta; generalmente Java no es tan golfoso).

public class Div {

    void d(long a, int b, int c) {
        if (a < 0 ^ b < 0) {
            a = -a;
            p('-');
        }
        for (p(a / b + "."); c > 0; c--) {
            p((a = a % b * 10) / b);
        }
    }

    <T> void p(T x) {
        System.out.print(x);
    }

    public static void main(String[] args) {
        final Div div = new Div();
        div.d(12345, 234, 20);
        div.p('\n');
        div.d(-12345, 234, 20);
        div.p('\n');
        div.d(234, 234, 20);
        div.p('\n');
        div.d(-234, 234, 20);
        div.p('\n');
        div.d(234, 12345, 20);
        div.p('\n');
        div.d(234, -12345, 20);
        div.p('\n');
        div.d(-234, 12345, 20);
        div.p('\n');
        div.d(-234, -12345, 20);
        div.p('\n');
        div.d(-2147483648, 2147483647, 20);
        div.p('\n');
        div.d(2147483647, -2147483648, 20);
        div.p('\n');
    }
}

El método básicamente ejercita lo que la mayoría de nosotros aprendimos en la escuela para generar los dígitos decimales solicitados.

El constructor
fuente
Sentencia oficial: diría que ignorar Integer.MIN_VALUEno está bien, pero que longcomo aporte está bien
durron597
Eso es mucho más corto. Bien hecho.
durron597
@ durron597 gracias. Sigue siendo un tipeo estricto y System.outhace que Java se sienta voluminoso ;-) Todavía es una buena sensación, que ya hay respuestas más largas publicadas.
TheConstructor
1
@ durron597 solicitó específicamente una función, así que pensé que no contaría. Si tuviera que usar importaciones, probablemente sí.
TheConstructor
1
Al menos no hay $ para cada variable ;-)
TheConstructor
9

C, 98 95 89

d(a,b,c){if(a>0^b>0)a=-a,printf("-");for(printf("%d.",a/b);c--;putchar(a/b+48))a=a%b*10;}

imprime cdígitos después del.

salida de ejemplo:

d(2,3,5);
0.66666

d(-2,3,5);
-0.66666

d(24352345,31412,500);
775.25611231376543995925124156373360499172290844263338851394371577740990704189481726728638736788488475741754743410161721635043932255189099707118298739335285878008404431427479943970457150133706863618999108620909206672609193938622182605373742518782630841716541449127721889723672481854068508850120972876607665860180822615560932127849229593785814338469374761237743537501591748376416656055010823888959633261174073602444925506175983700496625493441996689163377053355405577486310963962816757926906914554947153953

d(-77,12346463,500);
-0.00000623660395693892250760399962321192717298873369644407471192356871761572524859953818352673150196943043525906974329409159530142357369879940514137530724386409289850866600418273638369142644334656816288195250736992448768525852302801215214430238036593962173620088603513411087855687900251270343579371679160258286118056645048869461642577311412993340683886551152342172814999729072204727783171585254821563066280601982932277851559592411203111368818745903178910429650985873444078680671541315111866451144752954

debería funcionar para -2147483647 <= a <= 2147483647, lo mismo para b. manejar el -fue un dolor.

versión en línea: ideone

izabera
fuente
¿Funciona esto para un ser -2147483648? No conozco los compiladores de c lo suficientemente bien como para decir qué tipo de entero se asigna a sus parámetros.
TheConstructor
Gracias por mencionarlo. funciona correctamente para -2147483647 <= a <= 2147483647, lo mismo para b. hay un problema cuando a = -2147483648 yb es positivo debido a a=-a.
izabera
Lo intenté pero finalmente obtuve esencialmente la misma solución que tú. Puede guardar un personaje al darse cuenta de que printf("-")devuelve 1.
Thomas
4

PHP, 108

function d($a,$b,$c){$a*$b<0&&$a*=-print'-';for($p='.';$c--;$a.=0,print$i.$p,$p='')$a-=$b*$i=($a-$a%$b)/$b;}

Funciona simplemente emitiendo el cociente de a/ bdurante un ciclo de cpasos, aconvirtiéndose el resto multiplicado por 10 en cada iteración.

MANIFESTACIÓN

Razvan
fuente
Produce resultados extraños cuando aob son negativos
TheConstructor
Arreglé el error para los números negativos. ¡Gracias!
Razvan
Acabo de encontrar una versión 112 de su código: function d($a,$b,$c){if($a*$b<0)$a*=-print'-';for($p='.';$c--;$a*=10,$p=''){$a-=$b*$i=($a-$a%$b)/$b;echo$i.$p;}}vea el valor de retorno
TheConstructor
Gracias. Incluso actualicé su versión y logré ganar 1 byte adicional.
Razvan
2

Python 111

f=lambda a,b,c:'-'[a*b>=0:]+'%s'%reduce(lambda(d,r),c:(d%c*10,r+`d/c`+'.'[r!='':],),[abs(b)]*c,(abs(a),''))[-1]

Esta solución no viola ninguna de las reglas establecidas.

Abhijit
fuente
2

C: 72 caracteres

d(a,b,c){for(printf("%d.",a/b);c--;putchar((a=abs(a)%b*10)/abs(b)+48));}

Hace casi por completo lo que se supone que debe hacer. Sin embargo, como algunas de las otras respuestas aquí, dará valores inestables o fallará, d(-2147483648,b,c)y d(a,-2147483648,c)dado que el valor absoluto de -2147483648 está fuera de los límites para una palabra de 32 bits.

Fors
fuente
2

Perl, sin aritmética, 274 bytes

Esta es una división larga euclidiana , que probablemente consuma una cantidad inusual de memoria. Lo más parecido a las matemáticas en números de punto flotante es usar operaciones de bits para analizarlas.

sub di{($v,$i,$d,$e)=(0,@_);($s,$c,$j)=$i=~s/-//g;$s^=$d=~s/-//g;
$i=~s/\.(\d+)/$j=$1,""/e;$d=~s/\.(\d+)/$c=$1,""/e;
$z=0.x+length($c|$j);$i.=$j|$z;$d.=$c|$z;
($e,$m,$z,$t)=(1.x$e,0.x$i,0.x$d,"-"x($s&1));
for(;$e;$t.="."x!$v,$v=chop$e){$t.=$m=~s/$z//g||0;$m="$m"x10}
print"$t\n"}

Ejemplos:

di(-355,113,238);
di(1.13,355,239);
di(27942,19175,239);
di(1,-90.09,238);
di("--10.0","----9.801",239);
di(".01",".200",239);

Salida:

-3.141592920353982300884955752212389380530973451327433628318
584070796460176991150442477876106194690265486725663716814159
292035398230088495575221238938053097345132743362831858407079
646017699115044247787610619469026548672566371681415929203539

0.0031830985915492957746478873239436619718309859154929577464
788732394366197183098591549295774647887323943661971830985915
492957746478873239436619718309859154929577464788732394366197
183098591549295774647887323943661971830985915492957746478873

1.4572099087353324641460234680573663624511082138200782268578
878748370273794002607561929595827900912646675358539765319426
336375488917861799217731421121251629726205997392438070404172
099087353324641460234680573663624511082138200782268578878748

-0.011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011
100011100011100011100011100011100011100011100011100011100011

1.0203040506070809101112131415161718192021222324252627282930
313233343536373839404142434445464748495051525354555657585960
616263646566676869707172737475767778798081828384858687888990
919293949596979900010203040506070809101112131415161718192021

0.0500000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
usuario130144
fuente
1

Rubí, 178

def d(a,b,c)
    n=(a<0)^(b<0)
    a=-a if n
    m=a/b-b/a
    l=m.to_s.size-1
    g=(a*10**(10+c)/b).to_s
    f=m<0?"."+"0"*(l-1)+g[0..c-l-1] : g[0..l]+"."+g[l+1..c-2]
    p n ? "-"+f : f
end

Versión en línea para pruebas.

El truco consiste en multiplicar un con un número bastante alto, por lo que el resultado es solo un múltiplo entero de la operación de coma flotante. Luego, el punto y los ceros deben insertarse en el lugar correcto de la cadena resultante.

David Herrmann
fuente
¿Funciona esto para c más grande que 350?
durron597
Lo probé con c = 1000 - el código me dio una respuesta, quizás debería verificar el resultado real ...
David Herrmann
2
no gir más allá de 64 bits para grandes c? Editar: Creo que está usando implícitamente BigIntegeraquí
durron597
Err, ges una cadena, pero antes de llamar to_sha creado un número en la memoria que supera el tamaño de 64 bits
durron597
1
Eso es comprensible, ¡y hace que la tarea sea más desafiante (e interesante)! ¿Es mejor eliminar la respuesta o dejar que otros tengan un ejemplo de cómo no implementar la tarea?
David Herrmann
1

Python 92 bytes:

def d(a,b,c):c-=len(str(a/b))+1;e=10**c;a*=e;a/=b;a=str(a);x=len(a)-c;return a[:x]+'.'+a[x:]

Creo que un poco más de golf es posible .....

Maltysen
fuente
2
¿ esupera los 64 bits para c grande? Editar: creo que está usando implícitamente BigIntegeraquí.
durron597
1
@ durron597 lo dudo mucho. Va a BigInt (Long en python) pero 2 ** 45 es 48 bits. ¿Es eso suficiente presición? Además, python NO tiene primitivas, así que ...
Maltysen
Si a=5y c=400luego e=10**c, en hexadecimal, el número tiene 333 dígitos. Comienza 8889e7dd7f43fc2f7900bc2eac756d1c4927a5b8e56bbcfc97d39bac6936e648180f47d1396bc905a47cc481617c7...esto es más de 64 bits.
durron597
@ durron597 400 ... ¿necesito eso
Maltysen
1
Sí, la regla 3 dice que debe admitir hasta al menos 500 ... Estaba tratando de evitar esta solución (imo trivial).
durron597
1

C 83

d(a,b,c){printf("%d.",a/b);for(a=abs(a),b=abs(b);c--&&(a=a%b*10);)putchar(a/b+48);}

La misma idea que usé en mi implementación de Python

Abhijit
fuente
¡Muy agradable! Sin embargo, se bloquead(-2147483648,-1,10)
durron597