OberonCore

Задумался я, что лучше использовать (BlackBox или Java), если по ходу дела требуется много и упорно считать (в основном целочисленная арифметика большой точности). Почему выбор из этих двух? Просто на Java есть опыт, а Компонентный Паскаль легко освоить. В BlackBox есть модуль Integers. Делаем простой тест:
считаем факториал 20000 в BlackBox и Java. Получаем что Java быстрее в три раза.
На моей машине время вычислений такое: Java 4 sec, BlackBox 14 sec.
Java


BlackBox

Хотелось бы понять, с чем это связано, с неэффективной реализацией алгоритмов в BlackBox или время тратится на работу с памятью?

Я бы не сказал, что модуль Integers подходит для вычислительных целей (возможно следует посмотреть специфические подсистемы на http://www.zinnamturm.de). Скорее, это учебный модуль.

Разница в скорости объясняется просто. В Java класс BigInteger поддерживается непосредственно виртуальной машиной, предполагаю, что там все тщательно оптимизированно. В ББ, модуль полностью выполнен на верхнем уровне, причем используются достаточно ресурсоемкие (для таких вещей) операции, например NEW.

Думаете Java работает быстро? Сревните с Maple. 20000! он считает (на моей машине) за 0,2 с. При том что ваш пример у меня работает 18 с, следовательно ваша машина быстрее моей.

Maple использует распространяемую по GPL библиотеку GMP. Сия штуковина написана на жуткой смеси C и Ассемблера и пересобирается под конкретный процессор со всей оптимизацией. Думаю, быстрее ее ничего нет. Теоретически ее можно привезать к ББ (как ДЛЛ). Если сделаете это и поделитесь опытом, выразим вам большую благодарность, т. к. проблема актуальна.

Другой вариант, написать для ББ модуль с CODE вставками.

Mathematica 5.0 сосчитала за 0.02 сек (Athlon 1700+)

А у меня СLisp за 0.06c. Правда это встроенный факториал. Честно написанный считался 1.4с.

BlackBox - те же 14.

Ну, дык зависит еще от того как с библиотекой работать. Насколько я помню, числа в Maple хранятся во внутреннем формате. Для того чтобы обратиться к GMP, их нужно преобразовать к соотв. формату. При инсталяции мапл определяет тип процессора и ставит GMP специально для него. Mathematica похоже имеет оптимизированное монолитное вычислительное ядро, которое она ставит под конкретный процессор.

Вот, попробовал MultiMath.

Fact(20000) считало 2с.

Справедливости ради, объясню почему Mathematica чрезвычайно быстро вычисляет факториалы. Тут дело не только в очень хорошей реализации ее библиотек, тут выше берите - дело в алгоритме. Как известно, существует метод быстрого умножения длинных чисел, который имеет сложность O(N*Log(N)) вместо O(N*N), где N-число разрядов в числе. Так, вот оказывается факториалы тоже можно вычислять "достаточно быстро".

Пусть: N - количество чисел которые нужно перемножить.

1) Сначала делаем попарные умножения 1-разрядных чисел (под разрядом здесь условно понимаю машинное слово), т.е. N/2 умножений сложность каждого равна 1.
2) Потом полученные 2-разрядные числа опять умножаем попарно, получая 4-разрядные, выполнив при этом N/4 двухразрядных умножений.
3) Повторяем пока всё не перемножилось.

Сложность(N) = N/2*S(1) + N/4*S(2) + N/8*S(4) + N/16*S(8) +...+ 1*S(N/2) = Sum[(N*S[2^(p-1)])/2^p, {p, 1, Log2[2*N]-1}]

S(k) - сложность умножения k-разрядных чисел. Если использовать обычное умножение в столбик, то S(k) = k^2 и ускорения не будет (а будет O(N^2)). Но можно использовать быстрое умножение. S(k) = k*Log(k), тогда (если я ничего тут не напутал), получаем сложность
O(N*Log2[N]*Log2[N/2]) вместо O(N^2).

Mathematica 5.0 - ДЕМОН. Нужно было построить график достаточно сложной функции. Поставил MatLab, MathCAD, Mathematica.
Быстрее всего справился в Математике(прекрасный туториал), в Маткаде вообще не разобрался - хелп весь запутанный, а Матлаб вообще завис на построении графика.