6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
|
|
1 | |
Большие факториалы02.09.2011, 15:32. Показов 4034. Ответов 39
Метки нет (Все метки)
0
|
02.09.2011, 15:32 | |
Ответы с готовыми решениями:
39
Факториалы... Факториалы в while Факториалы Факториалы! |
03.09.2011, 09:49 | 21 |
Длинная арифметика это всегда интересно, так как реализовать по разному можно. Скажите, а никто не пробовал при вычислении больших факториалов взять за основание системы счисления степень двойки, то есть работать только со сдвигами, а уже после перевести полученное число по снованию степени 10? Возможно так быстрее будет, но руки не доходят проверить...
0
|
8384 / 3616 / 419
Регистрация: 03.07.2009
Сообщений: 10,709
|
|
03.09.2011, 09:53 | 22 |
В зависимости от способа хранения длинного. Если оно представлено одним числом, то не более чем за n, если массивом(как у меня), то мне его сложность будет О((Kx - Ny)*n), где Kx - количество задействованных элементов, Ny - количество младших нулей, n - основание факториала. И следует заметить, что K и N все время увеличивается
1
|
03.09.2011, 12:06 | 23 |
Гугл не возвращает, зато возвращает bing.
Добавлено через 55 секунд http://www.wolframalpha.com/bing/?i=999! Вот сайт для вычислений факториалов Добавлено через 1 минуту Возвращает до 815!
0
|
1069 / 848 / 60
Регистрация: 30.04.2011
Сообщений: 1,659
|
|
03.09.2011, 13:41 | 24 |
0
|
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
|
||||||
04.09.2011, 23:09 [ТС] | 25 | |||||
Ну вот посидел немного написал порогу которая щитает любые фактуриалы за принципом умножения и додавание в столбец вот код:
0
|
04.09.2011, 23:13 | 26 |
Работает медленно, на acmp.ru есть задача, про факториалы - вычислить факториал n (n<=1000), во времени ограничение - 1 секунда. А тут на 1000 работает уж точно больше. Вывод: надо писать версию 2.0 - модифицированную
0
|
6 / 6 / 0
Регистрация: 18.07.2011
Сообщений: 77
|
|
04.09.2011, 23:15 [ТС] | 27 |
Dani,я студент 1 курс)мне препод поставил задачу я выполнил) 1000!щитает около 15-20 сек)конешно буду улучшать свои навыки)
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
05.09.2011, 08:17 | 29 |
KING1994, я вообще школота, но у меня 100000! считает меньше чем за 10 секунд.
0
|
05.09.2011, 10:29 | 30 |
Для 32-битных машин, я брал за основание 2^16, для 64 - 2^32. Так, само собой, быстрее.
Только делал не через сдвиги. Но все равно быстрее, а памяти так вообще в разы меньше надо
1
|
TheAthlete
|
05.09.2011, 11:48
#31
|
2
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
05.09.2011, 15:40 | 32 |
fasked, а процедуры ввода-вывода показать можете?
0
|
05.09.2011, 15:42 | 33 |
Сейчас уже нет Исходники (как и все университетские) были утеряны. Но вообще преобразовывал в строку и обратно. Могу на досуге поковыряться и вспомнить, если интересно. Да мне и самому интересно
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
05.09.2011, 17:39 | 34 |
fasked, просто я всю жизнь считаю, что вывод длинного числа, хранящегося по основанию - довольно сложная задача
0
|
05.09.2011, 17:51 | 35 |
iama, либо я что-то неправильно понял, либо Вы.
Тут смысл в том, что в одной ячейке массива хранится не одна десятичная цифра, а максимум . И, грубо говоря, для хранения числа требуется не двадцать байт памяти, а 16. Плюс при том же сложении, надо выполнить не 20 итераций цикла, а всего 5. Даже на таких грубых подсчетах в 4 раза быстрее. Но это я отошел от темы... Ну а при выводе, тоже самое число хранится в памяти следующим образом: Код
0AD2h EB1Fh A98Ch AB54h
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
05.09.2011, 18:00 | 36 |
fasked, ааа, то есть основание таки будет не степень двойки, а максимальная степень десяти, помещающаяся в данных целочисленный тип, то есть, используя 32-битные беззнаковые числа мы можем хранить в каждой ячейке массива по 9 десятичных разрядов, вы это имеете в виду? Так я так всегда и пишу и с выводом удобно, и по памяти лучше, и размер массива меньше вычисления быстрее
0
|
05.09.2011, 18:10 | 37 |
Так это и есть основание по-моему Основание это же максимальное возможное значение для одного разряда числа. Здесь получается один разряд числа соответствует одной ячейки массива. Да и все операции выполняются с разрядами (ячейками), а не их частями. Просто символов не хватит, чтобы нарисовать число по основанию . А железка все равно все битами хранит, ну или байтами... это как посмотреть
Ну вообще немного не так. Десятичная система неудобна в том плане, что в 1 байт памяти помещается число 255, а 256 уже не помещается. То есть, если взять за основание 256, то 255 (dec) это число из одного разряда, а 256 (dec) уже из двух. В итоге считать в таких случаях проще как-то в HEX - количество памяти совпадает с количеством разрядов
0
|
1360 / 988 / 119
Регистрация: 30.07.2010
Сообщений: 5,297
|
|
05.09.2011, 18:23 | 38 |
Естественно, хранить удобней, даже операции арифметические выполнять удобней.
А вот выводить - не удобней
0
|
05.09.2011, 18:30 | 39 |
операции по-моему вообще пофигу не в уме же считаем, все машинка делает сама.
так как я занимался длинной арифметикой исключительно в криптографическом плане, то ... я ни разу не видел длинных десятичных чисел
0
|
06.09.2011, 10:37 | 40 |
Это все и так понятно. Думал кто-нибудь на время тестировал когда степень 10^m и степень 2^n.
0
|
06.09.2011, 10:37 | |
06.09.2011, 10:37 | |
Помогаю со студенческими работами здесь
40
Факториалы Факториалы числа Рекурсия: вывести факториалы от 1 до 10 Вычисление по формуле. Факториалы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |