Czasami, podczas gry w golfa, w kodzie należy przedstawiać duże liczby. Zapisywanie ich w obecnej postaci może znacznie zwiększyć liczbę bajtów.

Jakie masz ¹ ogólne wskazówki na temat zwięzłego przedstawiania długich liczb w kodzie?

Proszę zamieścić jedną wskazówkę na odpowiedź.

¹ W ogóle , to znaczy wskazówek, które mogą być stosowane w odniesieniu do więcej niż jednego języka. Aby uzyskać wskazówki dotyczące języka, publikuj posty w odpowiednich wątkach.

Zwróć uwagę na numery specjalne

Niektóre języki mają wbudowane funkcje kwadratów, potęgowania z bazą 2, n-tą liczbą pierwszą, silnią lub innymi procedurami, które mogą generować duże liczby. Sprawdź, czy Twój numer przypadkowo należy do którejkolwiek z tych kategorii.

A jeśli nie, może się zdarzyć, że większa liczba będzie pasować do twoich celów i może zostać użyta zamiast tego.

Użyj bitowych operatorów logicznych

Niektóre języki mają bitowe AND, OR, XOR, a czasem NIE.

Wyrażenie określonej dużej liczby jako bitowej kombinacji wyniku potęgowania lub przesunięcia w lewo i innej liczby może doprowadzić do dokładnie takiej liczby, jakiej potrzebujesz. Jest to zwykle warte zachodu tylko wtedy, gdy liczby stają się dość duże.

Na przykład 2147483722ma 10 bajtów, ale 2<<30^74(2 ^ 31 bitowo-XOR z 74) ma tylko 8.

Użyj ciągów znaków dla powtarzających się liczb

W przypadku liczb, które mają bardzo powtarzalny charakter, możesz użyć ciągów znaków i rzucić je na liczbę całkowitą. Na przykład w JavaScript

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

Użyj notacji naukowej

Notacja naukowa może oszczędzać bajty w przypadku długich liczb. Na przykład:

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

Zamiast tego poszukaj innej liczby

Może to zabrzmieć jak brak odpowiedzi, ale nie zawsze jest oczywiste, że większą liczbę można obliczyć za pomocą krótszego kodu. Przykład, który pamiętam, to wypisywanie googolowych kopii ciągu znaków , gdzie oczywiste odpowiedzi wymagają obliczenia 10 ¹⁰⁰ . Jak się okazuje, obliczenie dowolnej wielokrotności 10 ¹⁰⁰ prowadzi do równie poprawnej, ale w niektórych językach, krótszej odpowiedzi. Odpowiedź Dennisa używa tam 100 ¹⁰⁰ , moje własne 250 ²⁵⁵ .

Kompresja podstawowa

Podstawowy kod dekompresyjny może być dość złożony, ale jeśli masz naprawdę ogromną liczbę, czasami może pomóc skompresować go w bazie większej niż 10.

Pomaga również, że w niektórych językach podstawowy kod kompresji jest bardzo prosty. Na przykład PHP ma base64_decode(_), Python ma int(_,36), JavaScript ma parseInt(_,36), a wiele języków golfa ma wbudowane podstawowe dekompresje. Na przykład w CJam:

"+ÜTbô±"256b

Zawiera to niedrukowalne. Wypróbuj online!

To daje:

12345678987654321

Użyj ułamków wykładniczych dla dużych powtarzalnych liczb

Załóżmy, że chcesz wygenerować liczbę 100 100. Można użyć int("1"*100), +"1".repeat(100)itp, ale można również skorzystać z faktu, że jest bardzo blisko

1e100/9

Działa to najlepiej w przypadku bardzo powtarzalnych liczb, takich jak liczby jednocyfrowe. Kilka powtarzających się cyfr również działa całkiem dobrze:

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

Czasami można znaleźć jakiś inny dziwny wzór, który również może być dość zwięźle przedstawiony w tej metodzie. Jeśli potrzebujesz int("123456790"*11), na przykład:

1e100/81

Uważaj jednak: liczby takie int("1234567890"*10)nie mają tak łatwej reprezentacji.

Użyj Bitowego Lewego Przesunięcia dla potęgowania 2

Chociaż istnieje wiele języków, które obsługują potęgowanie potęgowania, niektóre nie. A te, które tego nie wymagają, zazwyczaj wymagają wywoływania funkcji (lub metod klasy / obiektu), co może kosztować kilka bajtów.

Ale możesz zaoszczędzić kilka bajtów, gdy musisz podnieść 2 do potęgi n , używając operatora Bitowego Lewego Przesunięcia <<jako 1<<n. Zauważ, że pozwoli to zaoszczędzić bajty tylko wtedy, gdy n jest większe lub równe 17. Jednak to zawsze zaoszczędzi ci bajtów, jeśli n jest dynamiczne. Kilka przykładów:

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

Twierdzenie o chińskiej reszcie

Jeśli często pojawiają się arbitralne duże liczby całkowite lub reprezentacja dużej liczby całkowitej w docelowym języku programowania kosztuje zbyt wiele bajtów, możesz rozważyć użycie twierdzenia o chińskim reszcie.

Wybierz kilka par względnie pierwszych liczb całkowitych m _i > = 2, a możesz wyrazić dużą liczbę od 0 do lcm (m ₁ , m ₂ , ..., m _i ) -1

Na przykład wybieram 2, 3, 5, 11, 79, 83, 89, 97, a następnie mogę jednoznacznie wyrazić liczbę mniejszą niż 18680171730. 10000000000 (1e10) można wyrazić jako 0,1,0,1,38,59,50,49 (1e10 mod 2, 3 ..., 97), które nie muszą być wyrażane jako specjalna klasa / struktura Big Integer, która mogłaby zaoszczędzić niektóre bajty w jakimś języku programowania.

Dodawanie i odejmowanie można wykonać bezpośrednio przy użyciu tej reprezentacji. Przykład:

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

Użyj dopełnienia sznurka (tam, gdzie to możliwe)

Jeśli duża liczba zawiera powtarzającą się cyfrę na początku lub na końcu, możesz być w stanie zaoszczędzić bajty, używając jednej z metod wypełniania w swoim języku do skonstruowania ciągu szukanej liczby, który możesz następnie przekonwertować na liczba całkowita.

Przykład

Aby wygenerować liczbę 1111111111111111111111112(25 bajtów) w JavaScript (ES8):

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

Użyj wykładników

Jeśli twój język ma operator wykładnika, możesz go użyć do wygenerowania, jeśli nie pożądanej liczby, przynajmniej liczby, którą możesz wykonać prostym obliczeniem lub 2, aby otrzymać swój numer. Nawet bez operatora nadal możesz zapisywać bajty za pomocą wbudowanej funkcji lub metody.

Przykład

Maksymalna bezpieczna całkowitą w JavaScript to 9007199254740991, co jest 16 cyfr. W ES7 można to obliczyć za pomocą następujących 7 bajtów:

2**53-1

Odpowiednik w ES6 i wcześniejszych wersjach, mimo że w tym przypadku ma taką samą długość jak sama liczba całkowita, pokazuje, że użycie bardziej szczegółowej metody niekoniecznie kosztuje więcej bajtów.

Math.pow(2,53)-1

Powyższe może jednak działać krócej, jeśli na przykład już Mathaliasujesz do jednego znaku w innym miejscu w kodzie.

Zamiast frakcji używaj ułamków

Przykład: 1./3zamiast0.333333333