Блог пользователя oursaco

Very Big Mod
Автор oursaco, история, 3 года назад, По-английски

I've been working on an NTT implementation, which needs a big modulo in the form of x*2^k + 1. Does anyone know any mods of this form around 1e25. I rly don't want to use Chinese remainder theorem T-T.

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится

I used a Python snippet to find these examples:

$$$542110 \cdot 2^{64} + 1 = 10000164429798685026549761$$$
$$$1192092895510222934 \cdot 2^{23} + 1 = 10000000000020220185935873$$$
$$$1192092895510222937 \cdot 2^{23} + 1 = 10000000000020220211101697$$$

And for fun, I have this one as well:

$$$10002400000000000000000001$$$

It's easy enough to find such examples with sympy.isprime.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Thanks!

    → Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is there any way to implement it in other programming languages? Problem setters say that they are not biased towards any languages (Like giving any constraint which a programming language cannot compile or handle).

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, there is a way.

      → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The main difficulty in this (at least in my opinion) is not testing primality, for which Miller-Rabin is very common, but the requirement of a BigInteger library.

      In Python and Java, BigIntegers are built in.

      In Rust, it's easy to find a package that gives BigInteger support to find these numbers on your own computer, but afaik you can't use it in a solution since I believe codeforces compiles rust with rustc and not cargo.

      In C++, you can probably find biginteger libraries, which shouldn't be too hard, though I don't know any.

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        In your experience of competitive programming, have you encountered any problem (Particularly on Codeforces or Atcoder) which required primality testing with a very big Constraint like 2e18 or smth?

        → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        In C++ you can use __int128. Also isn't bigint in python incredibly slow and you would better not use it in ntt?

        → Ответить
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          However in Miller-Rabin when testing the primality of some $$$n$$$, you need to multiply two numbers of size around $$$n$$$ (specifically, you need to repeatedly calculate $$$a^2 \bmod n$$$), and multiplying two numbers around $$$10^{25}$$$ gives you a result around $$$10^{50}$$$. C++'s $$$\scriptsize\texttt{__int128}$$$ can only store numbers up to $$$3.4 \times 10^{38}$$$, so this is not viable.

          Yes, Python is slow, I should have mentioned that above. I'm not sure how much it could be optimized with numpy (on online judges that have support, like Atcoder I believe).

          Here's a problem (not in a contest though) that required $$$\scriptsize\texttt{__int128}$$$ since the inputs went up to the max $$$\scriptsize\texttt{long long}$$$ capacity. I'll tag SilentVisitor since they asked about it too. However I haven't seen any problem with larger inputs than this.

          → Ответить
          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            ← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

            Well, you can multiply two numbers too big to fit in the type by some modulo same way you find a (power of a number) too big to fit in the type

            → Ответить