Модуль для очень быстрых операций с большими числами (256 бит) со знаком Опции

[Aelita]

Мне нужен модуль для очень быстрых операций с довольно большими числами (256 бит) со знаком.
Т. е. что-то типа Int256.
Причем принципиальна именно скорость, так как программе приходится выполнять
многие миллионы перемножений и сложений.

В Интернете есть довольно много разных модулей с массой операций для очень-очень больших чисел
(тысячи десятичных знаков).
Какой из них самый быстрый (для чисел не очень-то длинных: 256 бит)?
Или есть какой-то шустрый код в какой-нибудь классической книге?

Кто профи в этом вопросе, откликнитесь, плиз.

P. S. Я работаю во FReePascal-e

[Романтик]

Я не профи, но боюсь тебя расстроить: сомневаюсь что во freepascal можно такое творить.

[volvo]

James_Bond, ты даже не представляешь, ЧТО можно творить в FPC... Можно, например, перегрузить операции, и ты даже не почувствуешь разницы при работе Int256 по сравнению со стандартным Integer-ом...

Aelita, у нас в FAQ-е есть кое-что: Длинная арифметика, опять же у Vit-а есть в DRKB модуль, хотя я подозреваю, что для максимального повышения быстродействия придется подключать ассемблер. Сами ассемблерные вставки для работы с Int256 можно посмотреть здесь: Реализация арифметики для 256-битных чисел. (к сожалению основная программа там не на Паскале, а на С )

[Романтик]

volvo, ты извини меня конечно, но я говорил про freepascal, а ты рассказал и скинул все на С. Я почитал по этой теме немного и остался при своем мнении.

твое мнение здесь никого не волнует, человек пришел и задал вопрос, если тебе нечего сказать по теме - лучше молчи!
Администратор.

Сообщение отредактировано: Altair - 11.03.2006 13:24

[volvo]

James_Bond, ты можешь оставаться при своем мнении столько времени, сколько захочешь. Если ты не научился читать - то учись... Я что написал?

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

И ПРЕДУПРЕДИЛ (!!!) что основной модуль написан на С.

Я не понимаю, что тебе не понравилось в ассемблере. FPC (он же FreePascal, как ты его называешь) - 32 битный компилятор, с полной поддержкой 32-битного же ASM-а, все вставки, которые есть в программе по ссылке компилируются БЕЗ ИЗМЕНЕНИЙ!!!

А теперь я задам тебе вопрос: ты ВООБЩЕ FPC видел? Работал с ним? Знаешь его возможности?
С чего это вдруг тебе вздумалось рассуждать и составлять мнение о вещах, которых ты видеть не видел? Пофлудить больше негде? А если видел - значит, плохо смотрел, загрузи FPC, и попробуй откомпилировать ЛЮБУЮ из функций, содержащих ассемблерные вставки, приведенных там, где я показал (все, что тебе нужно - только изменить заголовок)...

Кстати,

Я почитал по этой теме немного и остался при своем мнении

Ну, выделенное слово я комментировать не буду, оно говорит само за себя. А при каком мнении ты остался? Что этого сделать нельзя? ВЫНУЖДЕН тебя огорчить: вот тут FAQ: Длинная Арифметика содержится 2 реализации, одна из которых тестировалась, а вторая - так и вообще создавалась на FPC, так что это вполне возможно... RTFM...

[Aelita]

Огромное спасибо, volvo, за обстоятельный ответ.

Я, к сожалению, весьма слабо разбираюсь в ассемблере и C (училась программировать на Паскале и его возможностей с учетом перехода на FreePascal до сих пор хватало. Программы пишу для собственных нужд научного характера -- автоматизации некоторых зубодробительных алгебраических выкладок).
Поэтому задам вероятно глупый вопрос: что нужно сделать, чтобы данный модуль Int256 (со всеми ассемблерными вставками) работал под FreePascal? Как должен выглядеть Unit, его использующий?
(Я совершенно не представляю, как пишутся переменные, функции и процедуры, корректно включающие эти ассемблерные строчки)

Еще раз спасибо.

Сообщение отредактировано: Aelita - 12.03.2006 6:57

[volvo]

Aelita, можно получить хотя бы фрагмент программы, чтобы можно было сравнить быстродействие нескольких реализаций? (Если не хочешь выкладывать сюда - можешь выслать в "Приват")

[Aelita]

Большое спасибо, volvo

Размещаю упрощенный вариант моей программы. Она работает с символьными комплексными выражениями с целыми коэффициентами, включая определители небольших матриц. Фактически, программа просто раскрывает скобки и таким образом проверяет, равна ли правая часть формулы левой. (В полном варианте программа работает с гиперкомплексными числами и раз в 5 длиннее).

В полном варианте приходится многие миллионы раз производить примерно следующее:
пара чисел (именно чисел, а не символьных выражений) порядка 10^20--10^35 умножается,
результат складывается (вычитается) с произведением другой подобной пары чисел
(т. е. на 2 этапе складываются 2 знаковых числа порядка 10^60--10^70),
после чего итог сравнивается с неким заданным числом.
(При равенстве программа выходит из цикла; если равенства не было, выдает сообщение о неудаче.)

Для иллюстрации этого я добавила небольшую подпрограмку NConstructor, имитирующую реальные процессы.

Кроме того, помещаю небольшой тестовый файл, иллюстрирующий действие программы (программа запускается на этот файл, все тесты должны давать 0).
Последний тест в этом файле как раз запускает NConstructor. Для измерения времени только его и нужно оставить.

Программа конечно весьма кривая, но как известно отстрел пианистов строго запрещен законом.
Если нужны комментарии, не вопрос.

Сообщение отредактировано: Aelita - 13.03.2006 0:54

[volvo]

Aelita, вопрос:
тебе нужно

type
  TNumber = record
    M: Int256;
    P: Byte;
    MI: Int256;
    PI: Byte;
  end;

?

А вопрос, собственно, потому, что у меня программа толком не работает:

Runtime error 216 at $004046C4
  $004046C4  SCANE,  line 1362 of f:/.../al_m8ext.pas
  $00404841  SCANMAIN,  line 1397 of f:/.../al_m8ext.pas
  $00406116  main,  line 1869 of f:/.../al_m8ext.pas

[Aelita]

Я не совсем понимаю, что именно не работает.

Я компилирую программу под FreePascal 2.0.2 (версия 1.0.10 не подходит, так как в ней Int64 реализован криво -- это и по моему опыту, и по мнению разработчиков).
Программу я компилирую FreePascal-ем для DOS-а и она работает в псевдоDOS режиме (под управлением Windows XP). (В реальных задачах я работаю даже в чистом DOS-e, поскольку критично не только быстродействие, но и нередко -- объем памяти, а Windows жрет ее много и не пойми на что).
После этого в командной строке я запускаю программу, подавая имя тестового файла как первый аргумент:
Al-m8ext.exe test-ext.txt

Программа считает файл секунд за 10-20.
Runtime error 216 я не получаю, по крайней мере на данном тесте.

Сообщение отредактировано: Aelita - 17.03.2006 8:25

[volvo]

Я задал вопрос относительно ИЗМЕНЕНИЙ, которые ты хочешь внести в программу. Я не собираюсь искать ошибки в программе, это меня не интересует. Target Win32 при запуске выдает то, что я скопировал. "Segmentation Fault". Если тебя интересует более конкретно - то это происходит здесь:

  function ScanE: PSumm;
  var
    Res: PSumm;
  begin
    LeftPart:= nil;
    while Ch = '#' do begin
      ReadLn(InFile, SS);
      WriteCurrentStr;
      Pos:= 1;
      Ch:= SS[Pos]; { <--- !!! Watches: (SS = ANSISTRING($0)) !!! }
      SkipSpace;
    end;

Если ты мне скажешь, ЧТО ИМЕННО ты хочешь заменить на Int256, я сделаю модуль, с которым твоя программа будет компилироваться. Проверять на работоспособность будешь сама, я Dos Extender ставить не буду...

[Aelita]

Я поняла.

Мне действительно нужно именно то, что ты написал:

type
  TNumber = record
    M: Int256;
    P: Byte;
    MI: Int256;
    PI: Byte;
  end;

Cпасибо! Жду с терпением.

Сообщение отредактировано: volvo - 2.11.2006 22:51

[volvo]

Aelita, я не забыл, просто не хотелось бы выкладывать незаконченную версию... Как только доделаю (я надеюсь, это произойдет довольно скоро) - выложу ...

[volvo]

Aelita, проверь PM ...