freepascal.ru

Всем доброго времени суток! Собственно говоря интересует сабж.
Быть может кто сталкивался с данной задачей? Требуется реализовать набор процедур для формирования целых чисел произвольной длины, их сложения, вычитания, деления и умножения.

Поспрашивал у яндекса, но он по большей части предлагает мудреные варианты на С++ в котором я не силен. Так что буду очень признателен за любую информацию по теме.

Что-то такое у меня было, и даже для Delphi/TurboPascal. Вечером дома поищу и выложу.

Погугли Delphi+RSA - в самописных модулях используется работа с большими числами (80 знаков и более).

Советовал бы более внимательно подходить к выбору алгоритмов для математических операций. Например, умножение и деление лучше реализовывать с помощью метода Фурье, для возведения в целую степень существует специальное дерево, которое минимизирует количество мультипликаций.

Astralis писал(а):Советовал бы более внимательно подходить к выбору алгоритмов для математических операций. Например, умножение и деление лучше реализовывать с помощью метода Фурье, для возведения в целую степень существует специальное дерево, которое минимизирует количество мультипликаций.

Я думаю, что в данном случае достаточно логических операций с "длинными" двоичными числами и без особого внимания к скорости.

А если вопросы производительности не так критичны, то значит числа не очень длинные, вполне может подойти данный модуль, который реализует работу с типом int256.

voltron писал(а):Что-то такое у меня было, и даже для Delphi/TurboPascal. Вечером дома поищу и выложу.

Было бы здорово! )

Astralis писал(а):А если вопросы производительности не так критичны, то значит числа не очень длинные, вполне может подойти данный модуль, который реализует работу с типом int256.

Модуль посмотрел... по большей части ассемблер. Если говорить о производительности, то она не так уж важна, здесь меня больше интересует сам принцип работы с длинными целыми числами.

вродеб принципы одинаковые на всех числах, что малых что больших

Сложение очень легко реализуется благодаря команде adc, которая оперирует с флагом переноса. Вычитание организуется за счет использования дополненительного кода (дополнение до 2). За счет дополнительного кода операции деления и умножения получаются чуть сложнее, но они и так являются медленными, а обычные алгоритмы являются квадратичными. В природе есть почти линейный алгоритм умножения, но он не так прост в реализации, а выигрыш заметен лишь для чисел очень большой размрности.

Когда-то очень давно баловался с возведением в степень больших чисел (типа 1996^1996). в итоге рассматривал вариант представления чисел как массивов. И соответственно работу с ними, как обычно в тетрадке в столбик умножали. Реализация проста до невозможности и вроде как не самая медленная.

Хотите сказать, что делали 1995 мультипликаций вместо возможных всего 15?

делал и так и так.

А какой самый "большой" стандартный тип для целых чисел? Есть ли больше чем Int64?

Максимальный стандартный это Int64. Но допустим в Object Pascal для 32 разрядных платформ он не был полноценным целочисленными например для цикла for с переменной типа int64 возникает ошибка компиляции, что-то вроде "тип с плавающей точкой нельзя использовать для цикла for".
С другой стороны никто не мешает сделать собственный тип данных и переопределить арифметические операции.
Например тип TGUID определен ка record, но сущность его все равно остается целочисленной.
А в совершенном языке программирования SmallTalk целые числа могут иметь произвольную длину.

Вот немного информации по работе с большими числами и примеры кода.