EvgeniSergeev's blog

1000000007 considered harmful
By EvgeniSergeev, history, 9 years ago, In English

Suggested upgrade: 1000999777 (prime)

Update. See below for why this is not an ideal candidate.

However, either of the following should be just as good as 1000000007:

  • Vote: I like it
  • +49
  • Vote: I do not like it

Comments Comments (37)
| Write comment?
»
9 years ago, # |
  Vote: I like it +58 Vote: I do not like it

Why is 1000000007 harmful?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Think it is easier to make mistake in number of zeroes when typing. (I use 1000 * 1000 * 1000 + 7)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Either copy paste from the problem statement or write (int)(1e9 + 7).

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I agree, just trying to explain why that modulo might be harmful.

        → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        (int)(1e9 + 7) is bad. Use (int)1e9 + 7.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +23 Vote: I do not like it

          const int x = 1e9 + 7; works pretty fine because no conversion needed for precise doubles.

          → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      in c++14 you can write

      int n = 1'000'000'007;
      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +84 Vote: I do not like it

        Once, in a hurry, I used a combination of two: 1000 * 000 * 000 + 7

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      I think it is easier to remember and write (int)1e9 + 7 than remembering this weird number 1000999777. In any case you will have to copy + paste.

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Maybe the original title was "An alternative to 1000000007 modulo", but... Niklaus Wirth had much better suggestion.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Those pioneers used to take important things like titles seriously. Nowadays you typically get something meaningless. Sometimes even with spelling errors. Not exaggerating — I saw one in a keynote slide title last year.

      → Reply
»
9 years ago, # |
  Vote: I like it +71 Vote: I do not like it

Not as harmful, as 1000000009)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which is still not as harmful as 1234567891 (yes, it's prime).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Which is still not as harmful as 1000696969... Just kidding, awesome, easy prime ^^

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        1000696969 does not cause integer overflow when you try to add two residues.

        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it 
          #define int long long

          ( ͡° ͜ʖ ͡°)

          → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            it could cause some other issues! imagine what printf looks like with that! it better too use typedef. Also I failed in system testing once because o using long long instead of int! so this is harmful too! ;)

            → Reply
          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
              Vote: I like it +11 Vote: I do not like it 
            #define long long long
            → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        lewd

        → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Why is it so? Just curious.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because 10^9+7 is used in most of the problems and when 10^9+9 occur a lot of contestants don't pay attention and still use 10^9+7.

      → Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +93 Vote: I do not like it

Note that choice of p = 1 000 000 007 is not random. Not only is it the smallest prime larger than 109, but also p - 1 is a semiprime (its only prime divisors are 2 and 500 000 003).

There are some techniques exploiting the factorization of p - 1 (for example, it has very many 2s in its prime factorization or has no large prime divisors). And... The largest prime divisor of 1 000 999 777 - 1 is only 317.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I wonder if that's because if we multiply any n from [1, p) by any m from [1, p), then (n*m) % p is never a zero? Making that a closed set under multiplication, of size p-1.

    I guess I haven't appreciated all the virtues of 1 000 000 007. While I don't think that it would have much direct effect if occasionally somebody got points for designing a scheme to exploit that weakness (I'm assuming that it's not bad enough such that every solution using addition and multiplication mod p would be automatically exploitable...), but the secondary effects seem undesirable. Such as: problemsetters having to worry about such things; strong contenders spending time perfecting such techniques to get the odd advantage, while they could be learning something useful; and the general public awareness that this is a source of weakness, and any mention of weakness is bad, due to the Chinese whispers effect.

    I've looked up 1 000 000 007 before posting the original memo, but none of the answers dealing with what's special about it mentioned anything other than the ramifications of it being a prime. This shows once again that the best way of asking a question is by making a provocative suggestion.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Yup, this kind of weaknesses come out from what you said — nonzero residues mod p create a group under multiplication of order p - 1.

      You told that strong contestants might want to look for some properties of moduli they get. I'll tell you what I do when I see a prime p different than 109 + 7 and 109 + 9: I automatically open my terminal, run 'factor p' and 'factor p-1' and check if something interesting happens — no learning weird techniques. Still, as for me, it's better to be safe than sorry.

      As for people trying to take advantage of bad modulus: if you choose a random prime, most probably nobody will exploit it. However, I have never heard of a solution noticing that 'blah, blah, 1 000 000 007 has some special property, so we can do blah blah blah and we're done' (I'm aware that some funny properties can be found, but as for now I don't know any).

      Moreover, I (and surely you) have already seen a few solutions exploiting weird things about other primes — but none of them seemed extendable to the case of our 'beloved' prime xD.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I must have been the first to expose the cult of 1000000007 and its evil twin 1000000009 by drawing attention to their inconvenient truth: that nobody can read them without digit separators. And not everybody is aware that int(1e9 + 7) is safe to do (with evidence even on this page).

        Though I agree that right now, after thousands of problems using 1000000007, seeing something else suggests that it has a special property that needs to be used (like properties of digital roots of certain numbers in that field, or something to do with the FFT). This shouldn't be a problem for simpler questions however, targeted at newcomers, where the hypnotising nature of 1000000007 becomes a bigger problem.

        Briefly, define a competition prime as a prime P between 9e8 and 2**30, such that both P and (P-1)/2 are primes. After a search, I'm pretty sure there aren't any highly readable numbers among the competition primes. The best I could find are probably 1000111787, 1060777919 and 1007111999.

        → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If given number is not a prime, you'll need to use Euler Totient Function to use modular multiplicative inverse. Other uses are mentioned

      I think a competitive programming problem should not require knowledge about some hard arithmetic theorems. Those would rather fit the syllabus of IMO, IMO.

      → Reply
»
9 years ago, # |
  Vote: I like it +82 Vote: I do not like it

If you are a problemsetter and you are writing a problem where you do computation modulo p, it is recommended to include an example where the result is obvious and the modulo actually gets used. E.g., "Here the answer is obviously 2^40, so you should return 2^40 mod 1,000,000,007 = 511,620,083.". This doesn't give away the solution and it prevents typos.

Obviously, there are some problems where this cannot be done, but often it's possible to find a test case that's large but simple enough.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah, someone I know(I'd just mention he's red here) wasn't fully aware how dangerous it was... he failed in regional round of KOI(Korean OI) last year. I hope he do well in IOI next week! ;)

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by EvgeniSergeev (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what about FFT-friendly primes? Pretty ones I was able to find between 109 and 1010:

2003304449 = 2^19 * 3821 + 1
3221225473 = 2^30 * 3 + 1
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    adding two 'int' type integers under 2003304449 can cause overflow.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well, then, what about

      1006108673 = 2^19 * 1919 + 1
1056440321 = 2^19 * 2015 + 1
      → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Which is why we have long long :D

      → Reply