14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
1 | |
Вычисление большой степени числа 6.31.12.2009, 02:49. Показов 4269. Ответов 17
Метки нет (Все метки)
Всем привет!
Есть следующая проблема. Нужно возвести число шесть в степень 2500000000 за 1 сек. Ограничения по памяти 5000К. Какие есть идеи ?
0
|
31.12.2009, 02:49 | |
Ответы с готовыми решениями:
17
Вычисление 2 в степени n Вычисление степени числа и запись цифр степени числа в массив Вычисление факториала и вычисление степени числа Вычисление степени числа 3 |
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
31.12.2009, 03:01 | 2 |
это называется длинная арифметика в место чисел берутся массивы char в зависимости от грамотности кода будет менятся время компилирования
Добавлено через 8 минут 5000k - 5000kb - 5mb? - места достаточно но проца (на олимпиадные задачки обычно дают от 3 до 6-ти сек) не хватит возможно как вариант использовать BCD 6=3 *2 тобишь можно просто 3 возвести в степень n тем самым ты выиграешь 2 в n операций а потом побитово сместить следующий момент нужно разобрать на кратность 3 9 27 91 ..3 ...9 ..27 и тд..
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
||||||
31.12.2009, 03:20 [ТС] | 3 | |||||
Да ты что говоришь... длинная арифметика...
Время выполнения будет в зависить от алгоритма в большей мере. Тут нужна какая - то специальная реализация длинной арифметики. Сначала я думал представить число в виде массива
104166667 умножений. Какие ещё есть мысли ?
0
|
31.12.2009, 12:38 | 4 |
Может попробовать возводить много раз в квадрат?..
И еще 6 в такой степени громаднейшее число, уверен, что возводить надо не по модулю??? Кстати зачем тебе unsigned long long ??? Во первых это не стандартная переменная, а во вторых, если говорить про скорость, то сработает только на 64-разрядных машинках.
0
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
31.12.2009, 13:19 | 5 |
А откуда эта задачка?
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
31.12.2009, 13:29 [ТС] | 6 |
асm.lviv.ua
Добавлено через 2 минуты To fasked, я уверен, и unsigned long long реализуется на 32 битных машинах x86 в регистрах edx:eax.
0
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
31.12.2009, 13:56 | 7 |
1. максимальное значение uint64 есть 2^64
2. 6^ 2500000000 это приблизительно 2^(25*(10^8))*2^(25*(10^8))+o(x) 3. 2^(50^(10*8))/2*64 = 50*(10^8)/64 число получится x*10[x>5]*10^7 а 5mb это 5*10^6 и плюс о маленькое от х точно в условии нет ошибки?
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
31.12.2009, 13:58 [ТС] | 8 |
нету
0
|
56 / 56 / 6
Регистрация: 23.10.2009
Сообщений: 250
|
|
31.12.2009, 14:15 | 9 |
тогда 3 возводи в степень 2,5e9 и побитово смещай на 2,5e9,
кста при реализации умножения uint64 вам нужно будет делать проверку разрядности - при простом умножении в секунду не влезешь на компе с 2,5GHZ
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
31.12.2009, 14:23 [ТС] | 10 |
Не получиться это уже надо задействовать числа с п.т. и тогда я точно не влезу по времени
Добавлено через 1 минуту упс провтыкал Добавлено через 44 секунды но этот вариант сомневаюсь что прокатит
0
|
133 / 132 / 29
Регистрация: 04.01.2009
Сообщений: 415
|
|
31.12.2009, 14:33 | 11 |
Используй Алгоритм быстрого возведения в степень, а результат записывай в строковый массив.
0
|
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
|
|
31.12.2009, 15:13 | 12 |
Можно конкретно номер задачи на Контестере?
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
01.01.2010, 18:13 [ТС] | 13 |
1245
0
|
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
|
|
02.01.2010, 08:37 | 14 |
Максимальное значение uint64 есть 2^64-1
0
|
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
|
|
07.01.2010, 13:57 | 16 |
Тогда будут лишние проблемы - ответ же нужен в десятичной. При более-менее объёмных вычислениях можно считать в системе по основанию 10^n, например 10000, чтобы произодить меньше операций.
0
|
10 / 10 / 4
Регистрация: 18.11.2009
Сообщений: 47
|
|
10.01.2010, 18:31 | 17 |
Посмотрел на задачу - сама тема не имеет практической ценности, так как автор решил задачу неверно. У квадратов есть общие стороны - поэтому ответ будет намного меньше.
Самое простое доказание этого - жадником найти ответы для маленьких чисел. Еще проще - посчитать длину ответа (6 в степени 2500000000), это будет 194... словом, почти 2 миллиарда, тоесть 2 гига. Такое не только в лимит памяти, но и в лимит вывода не лезет. Да и за секунду не посчитать, как не старайся.
0
|
14 / 14 / 4
Регистрация: 08.10.2009
Сообщений: 114
|
|
14.01.2010, 17:12 [ТС] | 18 |
Да, ты прав. Нечего сказать.
Ответ, найден это невозможно.
0
|
14.01.2010, 17:12 | |
14.01.2010, 17:12 | |
Помогаю со студенческими работами здесь
18
Вычисление степени числа Вычисление степени числа Напишите программу, осуществляющую заполнение числа типа BigInteger случайными цифрами и вычисление целой степени этого числа Вычисление числа 4 в степени 500 Вычисление 7-ой степени числа за 4 операции Вычисление n-ной степени числа Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |