Иногда во время игры в гольф нужно представлять большое количество кода в своем коде. Запись их как есть может значительно увеличить количество байтов.

Какие общие ¹ советы вы имеете для краткого представления длинных чисел в коде?

Пожалуйста, оставьте один совет за ответ.

¹ Под общими я подразумеваю советы, которые могут быть применены к более чем одному языку. Советы по конкретным языкам публикуются в соответствующей ветке.

Ищите специальные номера

Некоторые языки имеют встроенные функции для квадратов, возведения в степень с основанием 2, n-го простого, факториального или других процедур, которые могут генерировать большие числа. Проверьте, попадает ли ваш номер в какую-либо из этих категорий.

И если это не так, может случиться так, что большее число, которое подходит для ваших целей и может быть использовано вместо.

Используйте побитовые логические операторы

У некоторых языков есть побитовое И, ИЛИ, XOR, а иногда НЕТ.

Выражение определенного большого числа в виде побитовой комбинации результата возведения в степень или сдвига влево и другого числа может привести вас к именно тому числу, которое вам нужно. Обычно это того стоит, если цифры становятся достаточно большими.

Например, 2147483722это 10 байтов, но 2<<30^74(2 ^ 31 бит-XORed с 74) только 8.

Используйте строки для повторяющихся чисел

Для чисел, которые очень повторяются по своей природе, вы можете использовать строки и привести их к целому числу. Например, в JavaScript

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

Используйте научную нотацию

Научная запись может сохранять байты в случае длинных чисел. Например:

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

Ищите другой номер, чтобы использовать вместо

Это может звучать как отсутствие ответа, но не всегда очевидно, что большее число может быть вычислено с помощью более короткого кода. Пример, который я помню, это Вывод googol-копий строки , где очевидные ответы требуют вычисления 10 ¹⁰⁰ . Как выясняется, вычисление любого кратного 10 ¹⁰⁰ приводит к одинаково правильному, но в некоторых языках более короткому ответу. Ответ Денниса там использует 100 ¹⁰⁰ , мой собственный использует 250 ²⁵⁵ .

Базовое сжатие

Базовый декомпрессионный код может быть довольно сложным, но если у вас действительно огромное количество, иногда это может помочь сжать его в некоторой базе выше 10.

Также помогает то, что в некоторых языках базовый код сжатия очень прост. Например, PHP имеет base64_decode(_), Python имеет int(_,36), JavaScript имеет parseInt(_,36), и многие языки гольфа имеют встроенные декомпрессионные встроенные функции. Например, в CJam:

"+ÜTbô±"256b

Это содержит непечатный. Попробуйте онлайн!

Это дает:

12345678987654321

Используйте экспоненциальные дроби для больших повторяющихся чисел

Допустим, вы хотите сгенерировать число, состоящее из 100 единиц. Вы могли бы использовать int("1"*100), +"1".repeat(100)и т.д. , но вы также можете воспользоваться тем , что это очень близко к

1e100/9

Это лучше всего подходит для очень повторяющихся чисел, например, из одной цифры. Пара повторяющихся цифр также работает довольно хорошо:

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

Изредка вы можете найти какой-то другой странный шаблон, который также может быть представлен довольно кратко в этом методе. Если вам это понадобилось int("123456790"*11), например:

1e100/81

Однако будьте осторожны: такие числа int("1234567890"*10)не имеют такого простого представления.

Используйте побитовый сдвиг влево для возведения в степень 2

Хотя существует много языков, которые поддерживают оператор для возведения в степень, некоторые этого не делают. А те, которые этого не делают, обычно требуют вызова функций (или методов класса / объекта), которые могут стоить несколько байтов.

Но вы можете сохранить несколько байтов, когда вам нужно поднять 2 до степени n , используя оператор Bitwise Left Shift <<as 1<<n. Обратите внимание, что это сохранит ваши байты только в том случае, если n больше или равно 17. Однако это всегда будет сохранять ваши байты, если n является динамическим. Несколько примеров:

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

Китайская теорема об остатках

Если часто появляются произвольные большие целые числа или если большое целочисленное представление в целевом языке программирования стоит слишком много байтов, вы можете использовать китайскую теорему об остатках.

Выберите несколько попарно относительно простых чисел m _i > = 2, и вы можете выразить большое число от 0 до lcm (m ₁ , m ₂ , ..., m _i ) -1

Например, я выбираю 2, 3, 5, 11, 79, 83, 89, 97, тогда я могу однозначно выразить число меньше 18680171730. 10000000000 (1e10) можно выразить как 0,1,0,1,38,59,50,49 (1e10 mod 2, 3 ..., 97), которые не нужно выражать как специальный класс / структуру Big Integer, которые могут сохранять несколько байтов в некотором языке программирования.

Сложение и вычитание могут быть сделаны непосредственно с использованием этого представления. Пример:

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

Используйте String Padding (где это возможно)

Если большое число включает в себя повторяющуюся цифру в начале или конце, вы можете сохранить байты, используя один из методов заполнения вашего языка, чтобы создать строку нужного числа, которую затем можно преобразовать в целое число.

пример

Чтобы сгенерировать число 1111111111111111111111112(25 байт) в JavaScript (ES8):

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

Используйте экспоненты

Если на вашем языке есть оператор экспоненты, вы можете использовать его для генерации, если не нужного вам числа, хотя бы числа, которое вы можете выполнить простым вычислением или 2, чтобы получить свой номер. Даже без оператора вы все равно сможете сохранять байты с помощью встроенной функции или метода.

пример

Максимально безопасное число в JavaScript является 9007199254740991, длиной 16 цифр. В ES7 это можно рассчитать с помощью следующих 7 байтов:

2**53-1

Эквивалент в ES6 и более ранних версиях, хотя и такой же длины, что и само целое число в этом случае, демонстрирует, что использование более подробного метода может не обязательно стоить вам байтов.

Math.pow(2,53)-1

Выше, однако, может получиться короче, если, например, у вас уже естьMath указали псевдоним для одного символа в другом месте своего кода.

Используйте дроби на месте поплавка

Пример: 1./3вместо0.333333333