Implementar divisão de precisão arbitrária

15

Implemente uma função divide(int a, int b, int c)que imprima o valor base 10 de a/b. sem usar nenhuma matemática de ponto flutuante nem BigInteger/ BigDecimalou bibliotecas equivalentes. Pelo menos ccaracteres precisos dentro do conjunto de 0123456789.devem ser impressos, exceto a (possível) exceção no ponto 4 abaixo.

  1. ae bpode ser qualquer número inteiro de 32 bits. Atualização: se, para fins de golfe, você gostaria que as entradas fossem primitivas de 64 bits, tudo bem, mas você não precisa oferecer suporte a todo o intervalo de dados de 64 bits.
  2. Você não precisa verificar se cé positivo (embora, esperançosamente, seu programa não trava), se não for.
  3. O limite superior mínimo suportado para cé 500. Tudo bem se o seu programa não oferecer suporte aos valores cacima 500, mas também estará bem se houver.
  4. Para números que se dividem igualmente, é sua escolha imprimir zeros extras (com base no valor de c) ou nada.
  5. Você não precisa usar a função para executar outras tarefas com o quociente, o único objetivo é imprimir.
  6. Para números entre -1e 1, é sua escolha imprimir um líder 0. No entanto, esse é o único cenário em que a impressão de um zero à esquerda é aceitável e você pode imprimir apenas um desses zero.
  7. Você pode usar qualquer lógica de arredondamento / piso / teto que você preferir para a última casa decimal.
  8. Para uma resposta negativa, você deve imprimir um líder -. Isso não conta para c. No entanto, é sua escolha se você deseja imprimir , +ou nada para uma resposta positiva.
  9. Divisão inteira e módulo inteiro são permitidos. No entanto, lembre-se de que você está restrito a primitivos, a menos que opte por implementar sua própria BigInteger/ BigDecimalbiblioteca, que conta com o tamanho do código.
  10. Você não precisa lidar com o bser 0, mas pode, se quiser. Seu programa pode inserir um loop infinito, ou travar, se b=0, e você não será penalizado.
  11. Ligeira alteração de regra por comentário. Para garantir que o campo de jogo esteja nivelado ae com bgarantia de números inteiros de 32 bits, você pode usar números inteiros de 64 bits. Se o idioma escolhido exceder os números inteiros de 64 bits como primitivo, você não poderá, em nenhum momento, usar essa funcionalidade (finja que ele está limitado a 64 bits).
  12. Outro ponto que não está claro (embora não deva alterar nenhuma das respostas válidas atuais): embora cpossa ser interpretado como o número de caracteres impressos ou o número de espaços após o decimal, seu programa deve usar de calguma forma de maneira relevante para decidir quantos caracteres imprimir. Em outras palavras, divide(2,3,2)deve ter uma saída muito menor do que divide(2,3,500); não é bom imprimir 500 caracteres sem levar em consideração c.
  13. Na verdade, eu não ligo para o nome da função. dé bom para fins de golfe.

Entrada

Uma chamada de função e leitura stdinsão aceitas. Se você ler stdin, qualquer caractere que não esteja no conjunto [-0123456789]é considerado um delimitador de argumento.

Resultado

Caracteres stdoutconforme descrito acima.

Exemplo

para divide(2,3,5), todos os itens a seguir são saídas aceitáveis:

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

Outro exemplo: para divide(371,3,5)o seguinte, são todas as saídas aceitáveis:

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

E para divide(371,-3,5)o seguinte são todos aceitáveis:

-123.6
-123.7
-123.66666
-123.66667
durron597
fonte
Por uma questão de igualdade de condições, pode ser aconselhável fornecer um tamanho máximo específico de bit que possa ser usado (primitivo ou não), a menos que você role sua própria implementação maior, porque: a) em alguns idiomas, o tamanho dos bits das primitivas varia de acordo com a arquitetura subjacente eb) em alguns idiomas, grandes tipos de números são primitivos.
Jonathan Van Matre
@JonathanVanMatre Adicionou a regra 11 pelo seu comentário
durron597
1
Como você conta dígitos precisos ? No seu exemplo, vejo três ou quatro, mas nunca cinco, como o último argumento indica.
266 Howard Howard
@ Howard, se você fez 92,3,5a resposta seria, por exemplo, #30.67
durron597 26/02
1
Entre 370/3 = 123,333 lol
izabera

Respostas:

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

Eu tive que improvisar para que aou bpudesse ser -2147483648, pois números inteiros positivos de 32 bits contam apenas para 2147483647, por isso ase tornou a long. Poderia haver uma maneira melhor de lidar com resultados negativos, mas eu sei que nenhum ( doubleprovavelmente faria isso funcionar abs(a) < abs(b)como eles têm, -0mas apenas o complemento de um manteria a precisão).

Por que números de dois bytes? Eu precisava de 92 bytes para o cálculo e 36 para o auxiliar de impressão ( System.out.printé uma porcaria; geralmente Java não é tão bom assim).

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

O método basicamente exercita o que a maioria de nós aprendeu na escola para gerar os dígitos decimais solicitados.

TheConstructor
fonte
Decisão oficial: eu diria que ignorar Integer.MIN_VALUEnão é bom, mas que longcomo entrada é bom.
durron597
Isso é muito mais curto. Bem feito.
durron597
@ durron597 obrigado. Ainda assim, a digitação estrita e System.outfaz Java parecer volumoso ;-) Ainda é uma sensação boa, já que há respostas mais longas postadas.
TheConstructor
1
@ durron597 você pediu especificamente uma função, então eu pensei que ela não contaria. Se eu tivesse que usar importações do que provavelmente sim.
TheConstructor
1
Pelo menos não há $ para cada variável ;-) #
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 após o.

saída de exemplo:

d(2,3,5);
0.66666

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

d(24352345,31412,500);
775.25611231376543995925124156373360499172290844263338851394371577740990704189481726728638736788488475741754743410161721635043932255189099707118298739335285878008404431427479943970457150133706863618999108620909206672609193938622182605373742518782630841716541449127721889723672481854068508850120972876607665860180822615560932127849229593785814338469374761237743537501591748376416656055010823888959633261174073602444925506175983700496625493441996689163377053355405577486310963962816757926906914554947153953

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

deve funcionar para -2147483647 <= a <= 2147483647, o mesmo para b. lidar com isso -era uma dor.

versão online: ideone

izabera
fonte
Isso funciona para um ser -2147483648? Não conhece os compiladores c o suficiente para saber qual tipo de número inteiro é atribuído aos seus parâmetros.
TheConstructor
Obrigado por apontar isso. funciona corretamente para -2147483647 <= a <= 2147483647, o mesmo para b. há um problema quando a = -2147483648 eb é positivo devido a a=-a.
Izabera
Tentei, mas finalmente obtive essencialmente a mesma solução que você. Você pode salvar um personagem ao perceber que printf("-")retorna 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 simplesmente emitindo o quociente de a/ bdurante um loop de cetapas, atornando-se o restante multiplicado por 10 a cada iteração.

DEMO

Razvan
fonte
Produz resultados estranhos quando a ou b são negativos
TheConstructor
Corrigi o bug para números negativos. Obrigado!
Razvan
Acabei de encontrar uma versão 112 do seu 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;}}consulte o valor de retorno
TheConstructor
Obrigado. Até atualizei sua versão e consegui ganhar 1 byte extra.
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 solução não viola nenhuma das regras declaradas.

Abhijit
fonte
2

C: 72 caracteres

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

Faz quase inteiramente o que é suposto fazer. No entanto, como algumas das outras respostas aqui fornecerão valores instáveis ​​ou falharão, d(-2147483648,b,c)e d(a,-2147483648,c)como o valor absoluto de -2147483648 está fora dos limites para uma palavra de 32 bits.

Para s
fonte
2

Perl, sem aritmética, 274 bytes

Essa é a divisão longa euclidiana , que provavelmente consumirá uma quantidade incomum de memória. O mais próximo possível da matemática dos números de ponto flutuante é usar operações de bits para analisá-los.

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

Exemplos:

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

Resultado:

-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
user130144
fonte
1

Ruby, 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

Versão online para teste.

O truque é multiplicar um com um número bastante alto, para que o resultado seja apenas um múltiplo inteiro da operação de ponto flutuante. Em seguida, o ponto e os zeros devem ser inseridos no lugar certo na sequência resultante.

David Herrmann
fonte
Isso funciona para c maior que 350?
durron597
Eu testei com c = 1000 - o código me deu uma resposta, talvez eu deveria verificar o resultado real embora ...
David Herrmann
2
não gir além de 64 bits para grande c? Edit: Eu acho que você está usando implicitamente BigIntegeraqui
durron597 25/02
Err, gé uma cadeia, mas antes de chamar to_svocê criou um número na memória que está além de 64 bits em tamanho
durron597
1
Isso é compreensível - e torna a tarefa mais desafiadora (e interessante)! É melhor excluir a resposta ou deixar que outras pessoas tenham um exemplo de como não implementar a tarefa?
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:]

eu acho que um pouco mais de golfe é possível ...

Maltysen
fonte
2
não eir além de 64 bits para grandes c? Edit: Eu acho que você está usando implicitamente BigIntegeraqui.
durron597
1
@ durron597 eu duvido disso. Vai para BigInt (Long em python), mas 2 ** 45 são 48 bits. Isso é presicion suficiente ?? Além disso, python NÃO tem primitivas então ...
Maltysen
Se a=5e c=400depois e=10**c, em hexadecimal, o número terá 333 dígitos. Começa que 8889e7dd7f43fc2f7900bc2eac756d1c4927a5b8e56bbcfc97d39bac6936e648180f47d1396bc905a47cc481617c7...isso é mais do que 64 bits.
durron597
@ durron597 400 ... eu preciso disso
Maltysen
1
Sim, a regra 3 diz que você precisa suportar até pelo menos 500 ... Eu estava tentando impedir essa solução (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);}

Mesma ideia que usei na minha implementação python

Abhijit
fonte
Muito agradável! No entanto, ele trava emd(-2147483648,-1,10)
durron597