Às vezes, durante o golfe, é necessário representar um número grande (s) em seu código. Escrevê-los como estão pode aumentar significativamente a contagem de bytes.

O que em geral ¹ dicas você daria para representar números longos concisa em código?

Poste uma dica por resposta.

¹ Em geral , quero dizer dicas que podem ser aplicadas a mais de um único idioma. Para obter dicas específicas do idioma, poste no respectivo segmento.

Procure números especiais

Alguns idiomas possuem funções internas para quadrados, exponenciação com procedimentos de base 2, n- ésima primação, fatorial ou outros que podem gerar números grandes. Verifique se o seu número se enquadra em qualquer uma dessas categorias.

E se isso não acontecer, pode acontecer que um número maior seja adequado aos seus objetivos e possa ser usado.

Use operadores booleanos bit a bit

Alguns idiomas têm AND, OR, XOR e, às vezes, NÃO.

Expressar um número grande específico como uma combinação bit a bit de resultado de uma exponenciação ou deslocamento à esquerda e outro número pode levá-lo exatamente ao número necessário. Isso geralmente só vale a pena se os números ficarem muito grandes.

Por exemplo, 2147483722são 10 bytes, mas 2<<30^74(2 ^ 31 bits por XOR com 74) é apenas 8.

Use Strings para números repetitivos

Para números de natureza muito repetitiva, você pode usar Strings e convertê-los em Inteiro. Por exemplo, em JavaScript

+"1".repeat(100) // returns 100 1s (saves 84 bytes!)

Usar notação científica

A notação científica pode salvar bytes em caso de números longos. Por exemplo:

3564e-8 // returns 0.00003564 (saves 3 bytes!)

Procure outro número para usar

Isso pode parecer uma não resposta, mas nem sempre é óbvio que um número maior possa ser calculado por um código mais curto. Um exemplo que me lembro é o Output a googol, cópias de uma string , em que as respostas óbvias exigem computação 10 ¹⁰⁰ . Como se vê, calcular qualquer múltiplo de 10 ¹⁰⁰ leva a uma resposta igualmente correta, mas em alguns idiomas, mais curta. A resposta de Dennis usa 100 ¹⁰⁰ , a minha usa 250 ²⁵⁵ .

Compressão de Base

O código de descompressão de base pode ser bastante complexo, mas se você tiver um número realmente enorme, às vezes pode ajudar a compactá-lo em uma base superior a 10.

Também ajuda que, em alguns idiomas, o código de compactação básico seja muito simples. Por exemplo, o PHP possui base64_decode(_), o Python int(_,36), o JavaScript parseInt(_,36)e muitas linguagens de golfe têm builtins básicos de descompressão. Por exemplo, no CJam:

"+ÜTbô±"256b

Este contém um imprimível. Experimente online!

Isso produz:

12345678987654321

Use frações exponenciais para grandes números repetitivos

Digamos que você queira gerar o número composto de 100 1's. Você pode usar int("1"*100), +"1".repeat(100)etc., mas também pode aproveitar o fato de estar muito próximo

1e100/9

Isso funciona melhor para números muito repetitivos, como os feitos de um único dígito. Alguns dígitos repetidos também funcionam bastante bem:

12e100/99  // Generates 121212121212... (100 digits)

Ocasionalmente, você encontrará algum outro padrão estranho que também pode ser representado de maneira bastante concisa neste método. Se você precisar int("123456790"*11), por exemplo:

1e100/81

Porém, tenha cuidado: números como esses int("1234567890"*10)não têm uma representação tão fácil.

Use o deslocamento à esquerda bit a bit para exponenciação de 2

Embora existam muitos idiomas que suportam o operador para exponenciação, alguns não. E aqueles que não precisam, geralmente requerem funções de chamada (ou métodos de Classe / Objeto), que podem custar alguns bytes.

Mas você pode salvar alguns bytes quando precisar aumentar 2 para a potência n usando o operador Bitwise Left Shift <<como 1<<n. Observe que isso só salvará bytes se n for maior ou igual a 17. No entanto, isso sempre salvará bytes se n for dinâmico. Alguns exemplos:

1<<2 // returns 4 (3 bytes more :( )
1<<3 // returns 8 (3 bytes more :( )
1<<6 // returns 64 (2 bytes more :( )
1<<14 // returns 16384 (no bytes saved)
1<<17 // returns 131072 (saves 1 byte!)
1<<18 // returns 262114 (saves 1 byte!)

Teorema do Restante Chinês

Se números inteiros grandes arbitrários aparecerem com freqüência ou uma representação inteira grande na linguagem de programação de destino custar muitos bytes, considere o uso do Teorema do Restante Chinês.

Escolha alguns números inteiros relativamente primos emparelhados m _i > = 2, e você pode expressar um grande número de 0 a lcm (m ₁ , m ₂ , ..., m _i ) -1

Por exemplo, eu escolho 2, 3, 5, 11, 79, 83, 89, 97, então posso expressar um número menor que 18680171730 exclusivamente. 10000000000 (1e10) pode ser expresso como 0,1,0,1,38,59,50,49 (1e10 mod 2, 3 ..., 97) que não precisam ser expressos como classe / estrutura grande inteiro inteiro especial que pode salvar alguns bytes em alguma linguagem de programação.

A adição e a subtração podem ser feitas diretamente usando essa representação. Exemplo:

(0,1,0,1,38,59,50,49)+(0,2,0,6,23,20,16,53) = 1e10 + 5000 
                                            = (0+0 mod 2, 1+2 mod 3, 0+0 mod 5, 1+6 mod 11, 38+23 mod 79, 59+20 mod 83, 50+16 mod 89, 49+53 mod 97)

Use o preenchimento de cordas (sempre que possível)

Se um número grande incluir um dígito repetido no início ou no final, você poderá salvar bytes usando um dos métodos de preenchimento do seu idioma para construir uma sequência do número que está procurando, que poderá ser convertido em um inteiro.

Exemplo

Para gerar o número 1111111111111111111111112(25 bytes) em JavaScript (ES8):

+"2".padStart(25,1) // 19 bytes

Usar expoentes

Se o seu idioma tiver um operador de expoente, você poderá usá-lo para gerar, se não o número desejado, pelo menos um número, você poderá executar um cálculo simples ou 2 para chegar ao seu número. Mesmo sem um operador, você ainda poderá salvar bytes com uma função ou método interno.

Exemplo

O inteiro máximo seguro em JavaScript é 9007199254740991, que é de 16 dígitos. No ES7, isso pode ser calculado com os seguintes 7 bytes:

2**53-1

O equivalente no ES6 e versões anteriores, embora o mesmo tamanho do número inteiro nesta instância, demonstre que o uso de um método mais detalhado pode não necessariamente custar bytes.

Math.pow(2,53)-1

No entanto, as opções acima podem ser mais curtas se, por exemplo, você já tiver um Mathalias para um único caractere em outra parte do seu código.

Use frações no lugar da bóia

Exemplo: 1./3no lugar de0.333333333