Привет, Codeforces!
Когда говорят про языки программирования со встроенной реализацией длинной арифметики, обычно говорят о таких языках, как Java или Python. Сегодня я расскажу про длинку в языке Pascal, а, точнее, в его реализации Free Pascal Compiler.
Простейший код, который читает два "длинных" числа и складывает их, выглядит так:
Модуль gmp
содержит все классы и операторы дя работы с "длинными" числами.
Как он работает? Этот модуль содержит заголовки функций, импортируемые из GNU Multiprecision Library. Программа и библиотека связываются динамически, поэтому для работы программы необходимо, чтобы эта библиотека была установлена. К счастью, в большинстве дистрибутивов Linux она установлена по умолчанию и поэтому может быть использована в таких системах, как ejudge и Яндекс.Контест. В тестирующих системах на Windows библиотека не установлена, поэтому такая штука не сработает.
Для удобства работы в модуле реализована объектно-ориентированная обёртка над функциями libgmp
, для которой перегружены все необходиые операторы (да-да, во Free Pascal есть перегрузка операторов!)
Что еще примечательно, в libgmp
реализовано быстрое извлечение целочисленного квадратного корня. Поэтому можно написать очень простой, быстрый и короткий код на задачу F с заочного тура Открытки.
Auto comment: topic has been translated by gepardo (original revision, translated revision, compare)
В диалекте PascalABC.NET, который используется под Windows во многих школах и доступен на некоторых олимпиадах, тоже есть длинные числа BigInteger из .NET, уже несколько лет (в истории версий написано, что с февраля 2014 года).
Немного напоминает историю о том, как на Codeforces можно было использовать numpy из-под pypy.
Если не трудно пиши разные алгоритмы на паскале )
К сожалению эта длинка есть только на ejudge, codeforces, informatics.mccme, и hackerrank. На Яндекс.Контест и spoj.com нет, хотя там Linux. Видимо зависит от того как устанавливать компилятор.
Решил проверить, на Яндекс.Контесте в частности. Выдает ошибку компиляции в духе
Error: cannot find unit gmp
.То, что оно рабтает на codeforces, несколько неожиданно. Значит, там по какой-то причине стоит прописанный в PATH
libgmp
(возможно, требуется каким-то другим компилятором).В linux-дистрибутивах, в частности, Debian, Ubuntu, поставляемые с fpc модули разбиты на несколько пакетов. Например,
gmp
содержится в пакетеfp-units-math
, которой не установлен на Я.Контесте, по всей видимости. Но, в крайнем случае, можно скопировать необходимые биндинги к себе в код и слинковать его динамически сlibgmp
: FPC, в отличие от плюсовых компиляторов, позволять линковать библиотеки прямо из кода.Если устанавливать fpc с помощью apt или аналогичного установщика то все эти пакеты ставятся автоматически.
Но, в крайнем случае, можно скопировать необходимые биндинги к себе в код и слинковать его динамически с libgmp: FPC, в отличие от плюсовых компиляторов, позволять линковать библиотеки прямо из кода.
Хотелось бы поподробнее узнать как.
Можно сразу
sudo aptitude install fpc
, а можно что-то вродеsudo apt install fp-compiler fp-units-base
. Неизвестно, как там ставились компиляторы.Пусть у нас есть динамическая библотека (назовем ее
libtest.so
). Она имеет функциюint test(int val)
.Воспользовать этой функцией из кода на Паскале можно так:
Затем ее можно просто вызывать из кода.
Это для linux, в windows код будет слегка отличаться (возможно,
stdcall
вместоcdecl
, а также расширение.dll
, не.so
)Спасибо. А переменные можно так же объявлять?
Да. Более подробно здесь: https://www.freepascal.org/docs-html/prog/progsu148.html#x187-1900007.1.2
Там все это работает на LXC. Так что я полагаю, что они никак не ставились, а просто компилятор с необходимыми библиотеками уже лежит в rootfs.
Также не работает на codechef и тимусе
На csacademy не работает
Решать задачи на длинную арифметику в 2k18.. Да вы, батенька, некрофил
И какой в жопу паскаль в 2k18???
Огромное спасибо автору. Сейчас наткнулся на подходящую задачу, зашел в ваш блог, почитал полчасика pdf и сдал. Решение работает за 0.02 сек, в то время, как на С++, например, работало бы больше 3 секунд.
Ну не надо так плохо о C и C++. Ведь GMP написан как раз таки на C.