21
\$\begingroup\$

Sometimes, while golfing, one needs to represent large number(s) in their code. Writing them as is can significantly increase the byte-count.

What general1 tips do you have for representing long numbers concisely in code?

Please post one tip per answer.


1With general, I mean tips that can be applied to more than a single language. For language-specific tips, post in their respective thread.

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Martin Ender May 30 '17 at 8:51
  • \$\begingroup\$ Also related \$\endgroup\$ – Blue May 30 '17 at 10:05
  • \$\begingroup\$ I saw someone misunderstanding the question - perhaps the title should say this is about golfing. \$\endgroup\$ – Ørjan Johansen May 30 '17 at 10:34
  • \$\begingroup\$ Also also related \$\endgroup\$ – Beta Decay May 30 '17 at 14:04

12 Answers 12

15
\$\begingroup\$

Look out for special numbers

Some languages have built-in functions for squares, exponentiation with base 2, n-th prime, factorial, or other procedures that can generate large numbers. Check if you number happens to fall into any of those categories.

And if it doesn't, it may happen that a larger number that does will fit for your purposes and can be used instead.

\$\endgroup\$
  • 4
    \$\begingroup\$ Even if the number you want cannot be generated with a builtin function, it may be possible to generate a number that you can use as the basis for a simple calculation to arrive at your number, while still saving bytes over writing it out. \$\endgroup\$ – Shaggy May 30 '17 at 9:06
  • 7
    \$\begingroup\$ +1 for "larger number" -- if 1.01e6 iterations is enough, 1e7 saves 3 bytes at the expense of running time. \$\endgroup\$ – Chris H May 30 '17 at 12:34
13
\$\begingroup\$

Use bitwise boolean operators

Some languages have bitwise AND, OR, XOR, and sometimes NOT.

Expressing a specific large number as a bitwise combination of a result of an exponentiation or left shift and another number can get you to precisely the number you need. This is usually only worth it if the numbers get quite big.

For example, 2147483722 is 10 bytes, but 2<<30^74 (2^31 bitwise-XORed with 74) is only 8.

\$\endgroup\$
  • 3
    \$\begingroup\$ The shift operator can be replaced with exponentiation, if the language has that operator (eg bc). And XOR is never more useful than + and -: in this case, xor and add give the same result, but in all cases there is some integer which can be added or subtracted to produce the same result as xor with an integer, and the addend is no larger and sometimes shorter. \$\endgroup\$ – rici May 30 '17 at 15:32
  • 3
    \$\begingroup\$ @rici True if all integers are written as simple decimals, but it's just possible the integer to be used with xor can be shortened in ways that the integer to be used with plus or minus can't: think of something like 1e9^2e9. \$\endgroup\$ – hvd May 30 '17 at 17:54
  • 2
    \$\begingroup\$ @rici How would you express 9<<49^7<<19 using addition instead of xor? \$\endgroup\$ – L3viathan May 30 '17 at 18:52
  • 2
    \$\begingroup\$ @rici No, I meant what I wrote. It evaluates to 1286561280 in JavaScript and Perl (and probably other languages), and it's a shorter expression to produce that value than the equivalent using + or -. \$\endgroup\$ – hvd May 30 '17 at 18:53
  • \$\begingroup\$ @hvd: OK, point taken. \$\endgroup\$ – rici May 30 '17 at 18:58
11
\$\begingroup\$

Use Strings for repetitive numbers

For numbers that are very repetitive in nature, you can use Strings and cast them to Integer. For Example, in JavaScript

+"1".repeat(100) // returns 100 1s (saves 84 bytes!)
\$\endgroup\$
  • 2
    \$\begingroup\$ Or you could use a very large fraction, 1e100/9 in this case. \$\endgroup\$ – ETHproductions May 30 '17 at 15:17
11
\$\begingroup\$

Use Scientific Notation

Scientific notation can save bytes in case of long numbers. For Example:

3564e-8 // returns 0.00003564 (saves 3 bytes!)
\$\endgroup\$
  • 3
    \$\begingroup\$ Why not just use 3564e-8 in that case? \$\endgroup\$ – Joey May 30 '17 at 12:24
  • \$\begingroup\$ @Joey Yes, of course! Thank you! :) \$\endgroup\$ – Arjun May 30 '17 at 14:06
  • \$\begingroup\$ Granted, you can usually write the other number as .00003564, which is also one byte shorter again. \$\endgroup\$ – Joey May 30 '17 at 17:32
  • \$\begingroup\$ @Joey Not every language does, hence, I won't edit that in. \$\endgroup\$ – Arjun May 31 '17 at 6:05
  • \$\begingroup\$ Is it intentional that 3564 (left) becomes 354 (right) or is that a typo? \$\endgroup\$ – Erik May 31 '17 at 10:24
10
\$\begingroup\$

Look for another number to use instead

This may sound like a non-answer, but it is not always obvious that a larger number can be calculated by shorter code. An example I remember is Output a googol copies of a string, where the obvious answers require computing 10100. As it turns out, computing any multiple of 10100 leads to an equally correct, but in some languages, shorter answer. Dennis's answer there uses 100100, my own uses 250255.

\$\endgroup\$
  • 4
    \$\begingroup\$ Another example of this is CJam where you can get the current timestamp with es if you just need a large number but don't care about its value (or that it's always the same). \$\endgroup\$ – Martin Ender May 31 '17 at 7:31
10
\$\begingroup\$

Base Compression

Base decompression code can be fairly complex, but if you have a truly enormous number sometimes it can help to compress it in some base higher than 10.

It also helps that in some languages, the base compression code is very simple. For example, PHP has base64_decode(_), Python has int(_,36), JavaScript has parseInt(_,36), and many golfing languages have base decompression builtins. For example, in CJam:

"+ÜTbô±"256b

This contains an unprintable. Try it online!

This yields:

12345678987654321
\$\endgroup\$
9
\$\begingroup\$

Use exponential fractions for large repetitive numbers

Say you wanted to generate the number made of 100 1's. You could use int("1"*100), +"1".repeat(100), etc. but you can also take advantage of the fact that it's very close to

1e100/9

This works best for very repetitive numbers, such as those made of a single digit. A couple repeated digits also works fairly well:

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

Occasionally you'll find some other weird pattern which also can be represented fairly tersely in this method. If you happened to need int("123456790"*11), for example:

1e100/81

Be careful, though: numbers such as int("1234567890"*10) don't have such an easy representation.

\$\endgroup\$
9
\$\begingroup\$

Use Bitwise Left Shift for 2's exponentiation

Although, there are many languages that support operator for exponentiation, some do not. And those which don't, usually require calling functions (or Class/Object methods), which can cost a few bytes.

But you can save some bytes when you need to raise 2 to the power n by using the Bitwise Left Shift operator << as 1<<n. Note that this will only save you bytes if n is greater than or equal to 17. However, this will always save you bytes if n is dynamic. Few Examples:

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!)
\$\endgroup\$
  • 4
    \$\begingroup\$ Note that you can use other values instead of 1. 8<<9 // 4096 so we can get up to 99<<61 in 6 bytes, which equals 6,917,529,027,641,081,856 saving 13 bytes! \$\endgroup\$ – Draco18s May 30 '17 at 19:18
  • \$\begingroup\$ @Draco18s Yes, and it's covered here. \$\endgroup\$ – Arjun May 31 '17 at 6:05
  • \$\begingroup\$ That one more covers the boolean bitwise operators. Yes, it has the bitshifting too, but it's talking about using two large numbers to XOR and get a third, specific number. \$\endgroup\$ – Draco18s May 31 '17 at 13:43
7
\$\begingroup\$

Chinese Remainder Theorem

If arbitrary big integers frequently appear, or big integer representation in target programming language costs too many bytes, you can consider using Chinese Remainder Theorem.

Choose some pairwise relatively prime integers mi >=2, and you can express a big number from 0 to lcm(m1, m2, ... , mi) -1

For example, I choose 2, 3, 5, 11, 79, 83, 89, 97, then I can express number less than 18680171730 uniquely. 10000000000 (1e10) can be expressed as 0,1,0,1,38,59,50,49 (1e10 mod 2, 3 ... , 97) which need not be expressed as special Big Integer class/struct which might save some bytes in some programming language.

Addition and substraction can be done directly using this representation. Example:

(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)
\$\endgroup\$
  • 1
    \$\begingroup\$ Care to elaborate on that? \$\endgroup\$ – Skidsdev May 30 '17 at 12:23
  • \$\begingroup\$ @Mayube I have added some explanation, but I doubt it is useless in most cases. \$\endgroup\$ – Aria Ax May 30 '17 at 12:56
  • 1
    \$\begingroup\$ It's "remainder theorem". \$\endgroup\$ – Ørjan Johansen May 30 '17 at 17:02
6
\$\begingroup\$

Use String Padding (where possible)

If a large number includes a repeating digit at the beginning or end, you may be able to save bytes by using your one of your language's padding methods to construct a string of the number you're looking for, which you can then convert to an integer.


Example

To generate the number 1111111111111111111111112 (25 bytes) in JavaScript (ES8):

+"2".padStart(25,1) // 19 bytes
\$\endgroup\$
3
\$\begingroup\$

Use Exponents

If your language has an exponent operator you might be able to use it to generate, if not the number you want, at least a number you can perform a simple calculation or 2 on to arrive at your number. Even without an operator, you may still be able to save bytes with a built-in function or method.

Example

The maximum safe integer in JavaScript is 9007199254740991, which is 16 digits long. In ES7, this can be calculated with the following 7 bytes:

2**53-1

The equivalent in ES6 and earlier, while the same length as the integer itself in this instance, demonstrates that using a more verbose method might not necessarily cost you any bytes.

Math.pow(2,53)-1

The above, though, may work out shorter if, for example, you already have Math aliased to a single character elsewhere in your code.

\$\endgroup\$
2
\$\begingroup\$

Use fractions in the place of float

Example: 1./3 in place of 0.333333333

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.