2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение30.07.2008, 17:56 
Аватара пользователя
Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее. Если на каком-то шаге пришли к 1 - значит, имеем факториал и сразу определили, для какого числа это факториал. А если на некотором шаге не 1, но на очередное число нацело не делится - значит, не факториал.

 
 
 
 
Сообщение30.07.2008, 18:19 
Аватара пользователя
Цитата:
Касательно формулы Стирлинга (которая оценивает с двух сторон), для больших чисел она дает довольно неплохую точность.

Неплохую _относительную_ точность.
Цитата:
Причем, по-моему, достаточно подставлять предполагаемые ответы в границы оценочного интервала

А откуда у вас возьмется некий оценочный интервал для _обращения_ формулы Стирлинга?

PAV, именно это выше предложил Sergei Suvorov.

Добавлено спустя 5 минут 55 секунд:

Spook писал(а):
Бодигрим под бинарными Вы имеете ввиду обычные x86 совместимые? И что значит $ord_2 N$?

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

$ord_2 x$ - это наибольшая степень 2, которая все еще делит $x$ нацело.
Spook писал(а):
Sergei Suvorov у Вас вроде как тоже перебор и скорее всего потребуется вводить длинные числа.

В алгоритме перебора только одно условие завершения - превышение текущим найденным факториалом заданного числа. А в алгоритме Sergei Suvorov есть возможность предварительного завершения, если на каком-то из шагов не разделилось нацело. Поэтому он будет выполняться куда быстрее.
Spook писал(а):
Мне тут удалось узнать еще такой вариант для случая не совсем больших чисел, который знакомые как-то раз применили на ACM: просто посчитали заранее и загнали в таблицу, а потом оттуда брали.

Ну, это уже не в кассу.

 
 
 
 
Сообщение30.07.2008, 20:27 
Аватара пользователя
Бодигрим писал(а):
А откуда у вас возьмется некий оценочный интервал для _обращения_ формулы Стирлинга?
Я вот про какую формулу:
$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$

 
 
 
 
Сообщение30.07.2008, 20:32 
Аватара пользователя
И? Как вы применяете эту формулу для решения поставленной задачи?

 
 
 
 
Сообщение30.07.2008, 22:17 
Аватара пользователя
Я думал подставлять числа $n$ и сравнивать со значением факториала. Из тех $n$, которые подойдут, потом можно непосредственно выбрать нужное. Вот такой был мой план.

Касательно идеи с нулями, Вы не получали зависимости пяти последовательных чисел от количества нулей? Я пока ее проследить не смог, как-то хитро эти нули добавляются.

 
 
 
 
Сообщение30.07.2008, 22:40 
Аватара пользователя
Spook писал(а):
Я думал подставлять числа $n$ и сравнивать со значением факториала. Из тех $n$, которые подойдут, потом можно непосредственно выбрать нужное. Вот такой был мой план.

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

Как известно, количество нулей, на которое заканчивается $n!$, есть $ord_5 n! = \sum_{k=1}^\infty \lfloor n/5^k \rfloor$. Не следует пугаться последней суммы - на самом деле все ее члены, за исключением конечного их числа, суть нули. Кроме того отметим, что $\sum_{k=1}^\infty \lfloor n/5^k \rfloor < \sum_{k=1}^\infty n/5^k = n/4 $. C другой стороны
$$\sum_{k=1}^\infty \lfloor n/5^k \rfloor > \sum_{k=1}^{\log_5 n} (n/5^k-1) = {n(1-1/5^{\lfloor \log_5 n \rfloor})\over 4} -\lfloor \log_5 n \rfloor > (n-5)/4 - \log_5 n. $$

 
 
 
 
Сообщение30.07.2008, 23:27 
PAV писал(а):
Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее.
В отъезде с... по ....

Похоже, не хотят ребята попроще... Хорошего отъезда! :wink:

 
 
 
 
Сообщение31.07.2008, 00:41 
Аватара пользователя
Spook писал(а):
$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$


$2\pi n$ под корнем должно быть

 
 
 
 
Сообщение31.07.2008, 01:47 
Факториал интересен тем, что для вычисления его значения в точке $n$ нужно его значение в точке $n-1$. Поэтому даже если у нас есть гипотеза, что число $n$ - антифакториал заданного числа $N$, то нам всё равно надо будет проверить её тем, что посчитать $n!$.
Поэтому мне простейшим представляется следующее решение: пока $n! < N$ увеличиваем $n$ на один и считаем новый факториал умножением на одно короткое число. По окончании цикла проверяем равенство $n! == N$ и получаем ответ.
По сложности, вроде, минимальные затраты, и элементарен в написании - нужно только умножение длинного числа на короткое.

 
 
 
 
Сообщение31.07.2008, 08:44 
Аватара пользователя
Представление в компьютере больших целых чисел все равно надо будет делать в двоичном виде. В этом формате достаточно элементарно и быстро определяется число нулей, на которые оканчивается число, т.е. макисмальная степень двойки. Для числа $n!$ эта степень равна $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor + \lfloor\frac{n}{8}\rfloor + \cdots$, где $\lfloor\cdot\rfloor$ обозначают целую часть числа снизу.

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.

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

 
 
 
 
Сообщение31.07.2008, 09:54 
Аватара пользователя
PAV писал(а):
Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$.

Эта оценка ошибочна.

 
 
 
 
Сообщение31.07.2008, 10:04 
Аватара пользователя
Да, действительно. Должно быть от $n-\log_2 n$ до $n$, если я снова не ошибся.

 
 
 
 Re: Антифакториал
Сообщение31.07.2008, 10:09 
Spook писал(а):
1. Определить, является ли заданное число факториалом.


"Инженерный калькулятор Плюс" моего компьютера за 9 мин. подсчитал
$ 200000! = 1,4202253454703144049669463336823...e+973350 $, т.е. число имеет $ 973350 $ знаков.
Неужели, Вы оперируете более высокими величинами?

Если Вас вопрос интересует теоретически, то в принципе, для первой прикидки можно проверить делится ли без остатка заданное число, например, на тот же $ 200000! $

p.s. Кстати, в соседней теме Вы спрашивали, как можно проверить число на простоту?
Так вот, при помощи указанного выше факториала можно проверить все числа от $ 200000$ до $600000$.
Если данный факториал имеет остаток по модулю заданного числа, отличный от нуля, то это число - простое.
Если Вы отдельно введете проверку, делится ли число на $3$, то диапазон можно увеличить до $ 1000000$ и т.д.

 
 
 
 
Сообщение31.07.2008, 12:06 
PAV писал(а):
Представление в компьютере больших целых чисел все равно надо будет делать в двоичном виде. В этом формате достаточно элементарно и быстро определяется число нулей, на которые оканчивается число, т.е. макисмальная степень двойки. Для числа $n!$ эта степень равна $\lfloor\frac{n}{2}\rfloor + \lfloor\frac{n}{4}\rfloor + \lfloor\frac{n}{8}\rfloor + \cdots$, где $\lfloor\cdot\rfloor$ обозначают целую часть числа снизу.

Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.

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

Однако выгодно это только тогда, когда используется длинная арифметика, реализованная программным путём (т.к. реально в этом алгоритме требуется лишь аппаратная арифметика). И только для вычисления $N$ в случае, когда "$N!$" -- это действительно факториал. Для проверки же на факториальность всё равно понадобится та или иная последовательность делений.

Более того, тупой перебор натурального ряда статистически в любом случае эффективнее, т.к. в большинстве случаев проверка будет очень быстро обрываться.

 
 
 
 
Сообщение01.08.2008, 18:47 
Аватара пользователя
Echo-Off писал(а):
Spook писал(а):
$\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n+1}}<n!<\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n+\frac{1}{12n}}$

$2\pi n$ под корнем должно быть
Вы уверены? У меня в показателе степени стоит "$$+\frac{1}{2}$$"

Алексей К. писал(а):
PAV писал(а):
Послушайте, а не проще ли поступать так: берем требуемое число и последовательно делим на 2, 3, 4 и так далее.
В отъезде с... по ....

Похоже, не хотят ребята попроще... Хорошего отъезда! :wink:
Я, в общем, присоединяюсь, за исключением "нехотят" :) Думаю, в принципе, нужно
сделать как сказали PAV и Cave, вот только можно оптимизировать, напрмер, посчитать кол-во цифр и начать делить(умножать) не с 2, а с большего числа.

Бодигрим, да, пожалуй Стирлинг тут не лучший способ. Вариант с количеством нулей я все-таки на досуге попробую проверить. За неравенства спасибо, думаю, смогу получить точное выражение.

Батороев писал(а):
Неужели, Вы оперируете более высокими величинами?
Ну это просто задачка по программированию, в принципе, вряд ли числа будут больше.

Батороев писал(а):
p.s. Кстати, в соседней теме Вы спрашивали, как можно проверить число на простоту?
Так вот, при помощи указанного выше факториала можно проверить все числа от $ 200000$ до $600000$.
Если данный факториал имеет остаток по модулю заданного числа, отличный от нуля, то это число - простое.
Если Вы отдельно введете проверку, делится ли число на $3$, то диапазон можно увеличить до $ 1000000$ и т.д.
Интересная идея, оценить бы временную сложность и объем памяти.

PAV писал(а):
Это количество лежит в диапазоне от $n$ до $n+\log_2 n$, что достаточно неплохо локализует $n$. Более того, для разумных величин $n$ это количество считается достаточно быстро и легко, что позволит либо сразу забраковать проверяемый факториал, либо сузить диапазон $n$ до двух кандидатов.
В принципе получается, что мы вибираем меньшего кандидата и все-таки считаем полностью его факториал?

ewert писал(а):
Более того, тупой перебор натурального ряда статистически в любом случае эффективнее, т.к. в большинстве случаев проверка будет очень быстро обрываться.
Вы имеете ввиду просто последовательное деление?

 
 
 [ Сообщений: 40 ]  На страницу Пред.  1, 2, 3  След.


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