Посмотрел недавно исходники bcmath. Что тут можно сказать?
Philip A. Nelson, автор этой бибилиотеки, особо не беспокоится по поводу быстродействия своей библиотеки и объему потребляемой ей памяти. Для хранения чисел он использует массив
char * n_ptr. Это, конечно, универсально и подходит для большинства аппартаных платформ (сейчас сложно найти АЛУ, не поддерживающего арифметические операции с 8-битными числами). НО! В этом случае логично использовать основание
B = 2^8 = 256. Нельсон использует более привычное основание
B = 10, вследствие чего требование к размерам оперативной памяти возрастает в три раза. Выбор такого основания можно оправдать только для операций сложения и вычитания. В этом случае намного упрощается функции перевода числа в строку по основанию 10 и обратно. Но, если вспомнить про существование операций умножения, деления и вычисления квадратного корня, то становится грустно...
Сейчас большинство процессоров поддерживает 32-битные арифметические операции. Так почему бы не воспользоваться этим? Тогда быстродействие сложения и вычитание автоматически повышается в 4 раза по сравнению с 8-битными операциями, а умножения и деления - в 16 раз при использовании классических алгоритмов.
Но, если вспомнить про существования более изощренных и быстродействующих алгоритмов умножения и деления, описанных во втором томе Дональда Кнута, то можно еще выше поднять производительность библиотеки.
Справедливости ради стоит сказать, что Нельсон использует рекурсивный алгоритм умножения, основанный на формулах:
A = 2^n * a1 + a0
B = 2^n * b1 + b0
A * B = 2^(2*n) * (a1 * b1) + 2^n * (a1 * b0 + b1 * a0) + (a0 * b0)
Время его выполнения оценивается величиной
O(n^log(3)), что существенно меньше времени выполнения классического алгоритма
O(n^2) при больших
n. Но есть и более скоростные алгоритмы, основанные на быстром преобразовании Фурье. Например, в этой
http://www.perfsci.com/free/giantint/giantint.zip библиотеке реализован самый быстродействующий на сегодня алгоритм умножения, используемый в проекте поиска простых чисел Мерсенна
http://www.mersenne.org/prime.htm .
Вывод: нужно будет найти свободное время и заново все переписать
-~{}~ 28.02.04 17:02:
Оказывается, существует замечательная библиотека под названием
GMP, в которой реализованы большинство необходимых функций для работы с большими числами, в том числе и упомянутая мной проверка числа на простоту.
Я просто восхищен этой библиотекой! Ее автор,
Станислав Малышев, в отличие от
Филиппа нельсона, хорошо знаком с понятием "быстродействие".
Скачать исходники
GMP можно на официальном сайте http://www.swox.com/gmp/
Посмотреть список доступных через РНР функций можно тут http://www.php.net/gmp
-~{}~ 28.02.04 18:27:
Ой, я немного ошибся в авторстве
Станислав Малышев всего лишь реализовл интерфейс этой библиотеки для РНР, а авторов у нее много.
