9 / 9 / 3
Регистрация: 14.12.2010
Сообщений: 129
|
||||||
1 | ||||||
Возведение в степень09.10.2011, 01:28. Показов 12627. Ответов 30
Метки нет (Все метки)
Подскажите, как написать программу возведения 2-ки в миллионную степень и вывести результат на экран.
0
|
09.10.2011, 01:28 | |
Ответы с готовыми решениями:
30
Возведение в степень! возведение в степень! Возведение в степень Возведение в степень |
9 / 9 / 3
Регистрация: 14.12.2010
Сообщений: 129
|
|
09.10.2011, 01:47 [ТС] | 3 |
т.е. на одной обычной машине эта программа будет работать очень долго?
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
|
09.10.2011, 02:00 | 4 |
Такое большое число как 2 в степени 1 млн не влезет в стандартные типы и значит использовать функцию pow нельзя
Нужен или собственный класс больших чисел - но это вряд ли хороший подход, если нужно только двойку рассматривать Или посмотреть что-то насчет представления степеней двойки, например в двоичном виде 2 в степени 1 млн запишется как 10.......0 - миллион нулей после единицы А еще можно заметить закономерности построения степеней двойки, например они заканчиваются на 2, 4, 8, 6 всегда и эти цифры повторяются в указанном порядке))
0
|
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
|
|
09.10.2011, 02:04 | 5 |
ну простая арифметика показывает, что число будет
2 ^ 10e6 = (2^10) ^ 10e5 ~ 10e3 ^ 100000 = 10e300000 ну довольно много тем не менее есть более менее быстрые алгоритмы возведения в степень, идея такая, несложно распространить на миллион 2^30 = 4^15 = 8^14 = 64^7 = 128^6 = 16384^3 = 32768^2 = 1073741824 получится всего лишь порядка полумиллиона операций умножения и деления конечно вопрос в том как промежуточные вычисления да и результа в 300000 знаков хранить
0
|
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
|
|
09.10.2011, 02:15 | 7 |
не, я кстати соврал там для получения степени числа надо порядка 20-30 умножений
но хранить результат все равно както нужно
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
||||||
09.10.2011, 03:29 | 8 | |||||
Написала программку, решающую задачу "в лоб", т.е. она действительно возводит 2 в степень 100 000 путем перемножения 2*2*2... Естественно, работает ОЧЕНЬ долго) При возведении в степень 1 млн вообще можно будет состариться)
Числа хранятся в виде массивов
Если есть какие-то мысли по оптимизации хранения числа. буду рада услышать
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
09.10.2011, 08:18 | 11 |
Кроме логических операций есть несколько интристик (не знаю, как их по человечески назвать), которые для студии заточены. Циклические сдвиги и т.п., чего в Си нет они реализуют.
А вообще я вопрос не понял.)
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
09.10.2011, 09:25 | 12 |
haskell считает чуть больше секунды
Добавлено через 32 минуты даже меньше, 0.3 секунды
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
|
09.10.2011, 13:46 | 13 |
Так я ж и не претендую на самый оптимальный вариант решения задачи) Я ж сказала, что решаю "в лоб"
А можно глянуть код хоть на яве, хоть на хаскеле - для вдохновения? Как будут силы, напишу бинарное возведение в степень, это ускорит работу. Еще наверное надо подумать над оптимизацией хранения числа
0
|
Higher
|
|||||||||||
09.10.2011, 13:49 | 14 | ||||||||||
Да все также "в лоб"
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
|
09.10.2011, 13:52 | 15 |
ну так здесь используются надстройки для работы с большими числами, включенные в среду, как я поняла
А если без них? т.е. самостоятельно реализовать задачу - есть пример?
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
09.10.2011, 13:53 | 16 |
Код
[nameless@desktop haskell]$ cat sample.hs import System.Environment (getArgs) main = getArgs >>= print . (2^) . read . head [nameless@desktop haskell]$ ghc --make sample.hs [1 of 1] Compiling Main ( sample.hs, sample.o ) Linking sample ... [nameless@desktop haskell]$ time ./sample 1000000 > /dev/null real 0m0.271s user 0m0.267s sys 0m0.001s [nameless@desktop haskell]$
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
|
09.10.2011, 14:05 | 17 |
Nameless One, я наверное, себя переоценила, потому что в хаскеле ничего не поняла ))
Но мне кажется строчка main = getArgs >>= print . (2^) . read . head берет аргументы из командной строки и возводит в степень средствами языка? типа запись 2^1000000? А мне хотелось увидеть именно сам алгоритм быстрого возведения Поправьте, если ошиблась, просто программу на хаскеле вижу первый раз
0
|
Higher
|
|
09.10.2011, 14:12 | 18 |
1
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
09.10.2011, 14:14 | 19 |
берет список аргументов из командной строки, берет первый элемент из списка, переводит его в число и возводит двойку в эту степень
так их в гугле полным-полно
0
|
448 / 211 / 21
Регистрация: 07.10.2011
Сообщений: 462
|
|
09.10.2011, 14:22 | 20 |
Я знаю этот алгоритм, сама его писала тоже в качестве тренировки, безотносительно к большим числам) Просто хотела посмотреть на его реализацию применительно к большим числам в разных форматах хранения/представления. Так понимаю, что от реализации математических операций над большими числами (ну хотя бы умножения) в конкретном представлении все равно не уйти. А когда будет умножение, можно уже и возведение в степень реализовать
Просто было подозрение, что помимо быстрого возведения в степень можно как-то оптимизировать способ хранения большого числа именно для этой задачи, где 2 в основании Nameless One, Спасибо. Примерно так и поняла. Т.е., используются средства языка для работы с большими числами
0
|
09.10.2011, 14:22 | |
09.10.2011, 14:22 | |
Помогаю со студенческими работами здесь
20
Возведение в степень Возведение в степень Возведение в степень возведение в степень Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |