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

Автор gepardo, история, 7 лет назад, По-русски

Привет, Codeforces!

Когда говорят про языки программирования со встроенной реализацией длинной арифметики, обычно говорят о таких языках, как Java или Python. Сегодня я расскажу про длинку в языке Pascal, а, точнее, в его реализации Free Pascal Compiler.

Простейший код, который читает два "длинных" числа и складывает их, выглядит так:

Код

Модуль gmp содержит все классы и операторы дя работы с "длинными" числами.

Как он работает? Этот модуль содержит заголовки функций, импортируемые из GNU Multiprecision Library. Программа и библиотека связываются динамически, поэтому для работы программы необходимо, чтобы эта библиотека была установлена. К счастью, в большинстве дистрибутивов Linux она установлена по умолчанию и поэтому может быть использована в таких системах, как ejudge и Яндекс.Контест. В тестирующих системах на Windows библиотека не установлена, поэтому такая штука не сработает.

Для удобства работы в модуле реализована объектно-ориентированная обёртка над функциями libgmp, для которой перегружены все необходиые операторы (да-да, во Free Pascal есть перегрузка операторов!)

Что еще примечательно, в libgmp реализовано быстрое извлечение целочисленного квадратного корня. Поэтому можно написать очень простой, быстрый и короткий код на задачу F с заочного тура Открытки.

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

»
7 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Auto comment: topic has been translated by gepardo (original revision, translated revision, compare)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В диалекте PascalABC.NET, который используется под Windows во многих школах и доступен на некоторых олимпиадах, тоже есть длинные числа BigInteger из .NET, уже несколько лет (в истории версий написано, что с февраля 2014 года).

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

Немного напоминает историю о том, как на Codeforces можно было использовать numpy из-под pypy.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Если не трудно пиши разные алгоритмы на паскале )

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

К сожалению эта длинка есть только на ejudge, codeforces, informatics.mccme, и hackerrank. На Яндекс.Контест и spoj.com нет, хотя там Linux. Видимо зависит от того как устанавливать компилятор.

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

    Решил проверить, на Яндекс.Контесте в частности. Выдает ошибку компиляции в духе Error: cannot find unit gmp.

    То, что оно рабтает на codeforces, несколько неожиданно. Значит, там по какой-то причине стоит прописанный в PATH libgmp (возможно, требуется каким-то другим компилятором).

    Видимо зависит от того как устанавливать компилятор.

    В linux-дистрибутивах, в частности, Debian, Ubuntu, поставляемые с fpc модули разбиты на несколько пакетов. Например, gmp содержится в пакете fp-units-math, которой не установлен на Я.Контесте, по всей видимости. Но, в крайнем случае, можно скопировать необходимые биндинги к себе в код и слинковать его динамически с libgmp: FPC, в отличие от плюсовых компиляторов, позволять линковать библиотеки прямо из кода.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Если устанавливать fpc с помощью apt или аналогичного установщика то все эти пакеты ставятся автоматически.

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

      Хотелось бы поподробнее узнать как.

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

        Если устанавливать fpc с помощью apt или аналогичного установщика то все эти пакеты ставятся автоматически.

        Можно сразу sudo aptitude install fpc, а можно что-то вроде sudo apt install fp-compiler fp-units-base. Неизвестно, как там ставились компиляторы.

        Хотелось бы поподробнее узнать как.

        Пусть у нас есть динамическая библотека (назовем ее libtest.so). Она имеет функцию int test(int val).

        Воспользовать этой функцией из кода на Паскале можно так:

        function test(val: integer): integer; cdecl; external 'libtest.so';
        

        Затем ее можно просто вызывать из кода.

        Это для linux, в windows код будет слегка отличаться (возможно, stdcall вместо cdecl, а также расширение .dll, не .so)

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

    Также не работает на codechef и тимусе

»
7 лет назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Решать задачи на длинную арифметику в 2k18.. Да вы, батенька, некрофил

»
7 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

И какой в жопу паскаль в 2k18???

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

Огромное спасибо автору. Сейчас наткнулся на подходящую задачу, зашел в ваш блог, почитал полчасика pdf и сдал. Решение работает за 0.02 сек, в то время, как на С++, например, работало бы больше 3 секунд.

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

    Ну не надо так плохо о C и C++. Ведь GMP написан как раз таки на C.