2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Вычисление больших факториалов на JavaScript
Сообщение02.07.2018, 23:36 
Аватара пользователя
Продолжаю делать первые шаги в JavaScript. Пытаюсь написать процедуру, вычисляющую факториал:

Используется синтаксис Javascript
function factorial(n) {
 
  var i;

for (i = n-1; i > 0; i--) {
  n*=i;
 
}
 
  return(n);
}
 


Кажется, она потихонечку работает (типа, ура?), но только для маленьких чисел.
Например:

Используется синтаксис Javascript
console.log( factorial(10) );
 

выдаёт $3628800$, однако

Используется синтаксис Javascript
console.log( factorial(1000) );
 

уже выдаёт $\infty$.

С другой стороны, Альфа успешно вычисляет факториал числа 1000.
Можно ли заставить JavaScript сделать то же самое?

P. S.
Приму любые замечания по коду, включая эстетические. И вообще, любые замечания, так или иначе касающиеся программирования. Когда делаешь первые шаги, важна каждая мелочь.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение02.07.2018, 23:41 
Для таких задач нужна арифметика произвольной точности (либо встроенная в язык, либо реализованная в виде внешней библиотеки). Насколько я знаю, в Javascript недавно вставили соответствующий примитивный тип BigInt, но насколько это работоспособно уже сейчас, сказать не берусь.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение02.07.2018, 23:53 
Плюс почему не работает этот код: введите в консоли Number.MAX_VALUE и получите наверняка 1.7976931348623157e+308 — наибольшее положительное число, представимое плавающим форматом float64, который, по идее*, и используется в JS для чисел (даже для целых, кстати! что приводит к некоторым проблемам с битовыми операциями и некоторыми другими вещами; но этот факт тут ни при чём, потому что диапазон точно представимых целых намного уже). Этого не хватает, чтобы представить $1000!\approx 4\cdot10^{2567}$.

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

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 00:00 
Аватара пользователя
arseniiv в сообщении #1324061 писал(а):
Плюс почему не работает этот код: введите в консоли Number.MAX_VALUE и получите наверняка 1.7976931348623157e+308 ...

Вы правы, именно это значение и получилось.
А есть способ обойти это ограничение? Почему, например, в Альфе не так?

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 00:05 
Аватара пользователя
Потому что Альфа изначально представляет целые числа иначе и использует арифметику произвольной точности. В Питоне, например, целые тоже могут быть любой длины.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 00:16 
Аватара пользователя
Aritaborian
Я правильно понимаю, что в JavaScript, оказывается, нельзя - и точка? Он не для таких вещей создан?

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 00:33 
Аватара пользователя
Есть какие-то внешние библиотеки. И см. выше, что написал Pphantom про новый тип данных. Но подробностей вы от меня не добьётесь, не настолько хорошо разбираюсь.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 01:15 
Задействуйте мозг для смены алгоритма вычислений и замените умножение сложением логарифмов (для удобства можно даже десятичных). Точность пострадает, зато диапазон допустимых чисел вырастет на порядки. Преобразование в нормальную запись делать уже для результата при выводе человеку, тоже руками (вот тут десятичные сильно пригодятся).
Конечно это не решает проблему больших чисел в общем, но такие обходные пути часто можно найти, при желании, правда в каждом конкретном случае свои.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 01:28 
Аватара пользователя
Dmitriy40 в сообщении #1324078 писал(а):
Задействуйте мозг...

Для этого необходимо, как минимум, чтобы он у меня был.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 01:44 
Dmitriy40 в сообщении #1324078 писал(а):
Задействуйте мозг для смены алгоритма вычислений и замените умножение сложением логарифмов (для удобства можно даже десятичных).
Тогда уж можно сразу формулу Стирлинга использовать, результат будет практически таким же.
Ktina в сообщении #1324068 писал(а):
Я правильно понимаю, что в JavaScript, оказывается, нельзя - и точка? Он не для таких вещей создан?
Можно (мое первое сообщение в теме, вообще говоря, является сборником фраз для гугления; если таковым заняться, найдется довольно много информации), но действительно не нужно. Для решения специализированных задач лучше использовать специализированные языки.

 
 
 
 Re: Вычисление больших факториалов на JavaScript
Сообщение03.07.2018, 01:46 
Если использовать логарифмы, то для лучшей точности стоит идти в сторону увеличения чисел, а не уменьшения как сейчас в коде.
Точность в любом случае не превысит где-то девяти-десяти знаков, в отличии от BigInt, который вообще говоря точный, зато медленнее логарифмов (для достаточно длинных чисел).
PS. Ну а без мозга изучать программирование, и тем более заниматься им, полностью бессмысленно. :mrgreen:

-- 03.07.2018, 01:48 --

Pphantom в сообщении #1324083 писал(а):
Тогда уж можно сразу формулу Стирлинга использовать,
Это да, но это ещё дальше оптимизация алгоритма, я высказал лишь первый банальный шаг.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group