Операции с длинным номером в сети

Question

Я хотел бы написать (не использовать существующую) библиотеку (или что-то еще), которая работает с длинными числами (я имею в виду не менее нескольких сотен цифр).

Первый вопрос: выбор языка для него. Какой из них лучше: Perl / JavaScript / PHP?

Второй вопрос: как реализовать операции с длинными числами? Единственное, что я получаю, - это работаю с ними, как с массивами, например:

.

arr1 = (12, 34); //1234
arr2 = (98, 76); //9876
sum = longnumbers_add(arr1, arr2); // +
// 34 + 76 = 110 = 10 -..> 1
// 12 + 98 = 110 = 110 + 1 = 11 -..> 1
//sum == (1, 11, 10);

Но это работало медленно (по крайней мере, с моей попыткой в ​​PHP). Может быть, есть какой-нибудь сверхбыстрый метод "бит сдвига"?

приписка

Я знаю, что есть gmp и другие классные библиотеки.

Любая помощь приветствуется.

Answer 1

Я написал пару больших библиотек для забавы.Что касается языка, я бы выбрал тот, который вам наиболее удобен, или тот, о котором вы хотите узнать больше.Для меня это был JavaScript совсем недавно, но, по моему мнению, ни один из этих языков не подходит для больших количеств.Для сети, тем не менее, большая часть решения сводится к тому, хотите ли вы выполнять вычисления на стороне клиента или сервера.На стороне клиента JavaScript является практически единственным вариантом.

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

• http://silentmatt.com/blog/2011/10/how-bigintegers-work/
• http://silentmatt.com/blog/2011/10/how-bigintegers-work-part-2-multiplication/

Вот несколько мыслей из моего опыта:

• Концептуально, вероятно, проще всего хранить числа в базе 10, потому что это более знакомо, но на самом деле не сильно меняет реализацию.Большие базы более эффективны (как по памяти, так и по скорости).
• Практически всегда проще хранить цифры в порядке «с прямым порядком байтов», поэтому младшая цифра стоит первой в массиве (или, если вы использовалистроки, храните их в обратном порядке).
• Не слишком переживайте по поводу производительности, пока она не заработает.Самый быстрый способ сделать что-то может иногда вызывать удивление, так что вы все равно ошибетесь, и вы легко сможете вернуться и оптимизировать каждую операцию, когда закончите.
• Если вы хотите поддерживать десятичные дроби, он можетпроще всего сначала написать целочисленный тип, а затем реализовать числа с плавающей точкой.По сути, вы можете отделить код для отслеживания десятичных разрядов, чтобы обеспечить чистоту алгоритмов.
• Вам нужно будет решить, хотите ли вы использовать дополнение к двум (дополнение к 10,или эквивалент для любой базы, которую вы выбираете, также работает) или величина знака (где вы храните знак отдельно от цифр) для обработки отрицательных чисел.Каждый метод более сложен в одних областях и проще в других.В целом, хотя n-дополнение, возможно, проще, если у вас фиксированный размер, но величина знака может быть проще для чисел произвольного размера.

Answer 2

Я не уверен, хотите ли вы написать высокоуровневую библиотеку для работы с длинными числами (например, для вычисления простых чисел или чего-то еще) или просто реализовать низкоуровневые операции (сложение, умножение) для целей обучения.Если вы заинтересованы в первом, вы должны рассмотреть Python вместо JavaScript / PHP / Perl.Python имеет встроенную поддержку для произвольно больших целых чисел и десятичный класс для точной арифметики с плавающей запятой в своей стандартной библиотеке.

Answer 3

Вы должны попробовать BCMath: http://php.net/manual/en/book.bc.php