Вычисление большой степени числа 6.

@Sich_Taras · Регистрация: 08.10.2009

Author24 — интернет-сервис помощи студентам

Всем привет!
Есть следующая проблема. Нужно возвести число шесть в степень 2500000000 за 1 сек.
Ограничения по памяти 5000К.

Какие есть идеи ?

@breate · 31.12.2009, 03:01

это называется длинная арифметика в место чисел берутся массивы char в зависимости от грамотности кода будет менятся время компилирования

Добавлено через 8 минут
5000k - 5000kb - 5mb? - места достаточно
но проца (на олимпиадные задачки обычно дают от 3 до 6-ти сек) не хватит возможно как вариант использовать BCD 6=3 *2 тобишь можно просто 3 возвести в степень n тем самым ты выиграешь 2 в n операций а потом побитово сместить следующий момент нужно разобрать на кратность 3 9 27 91 ..3 ...9 ..27 и тд..

@Sich_Taras · 31.12.2009, 03:20 **[ТС]**

Да ты что говоришь... длинная арифметика...

Время выполнения будет в зависить от алгоритма в большей мере.
Тут нужна какая - то специальная реализация длинной арифметики.
Сначала я думал представить число в виде массива

C++

1	unsigned long long

и умножать не на 6 2500000000 раз, а умножать на шесть в 24 степени в 24 раза меньше, но и это слишком много -
104166667 умножений.
Какие ещё есть мысли ?

@fasked · 31.12.2009, 12:38

Может попробовать возводить много раз в квадрат?..
И еще 6 в такой степени громаднейшее число, уверен, что возводить надо не по модулю???

Кстати зачем тебе unsigned long long ??? Во первых это не стандартная переменная, а во вторых, если говорить про скорость, то сработает только на 64-разрядных машинках.

@breate · 31.12.2009, 13:19

А откуда эта задачка?

@Sich_Taras · 31.12.2009, 13:29 **[ТС]**

асm.lviv.ua

Добавлено через 2 минуты
To fasked, я уверен, и unsigned long long реализуется на 32 битных машинах x86 в регистрах edx:eax.

@breate · 31.12.2009, 13:56

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
и плюс о маленькое от х
точно в условии нет ошибки?

@Sich_Taras · 31.12.2009, 13:58 **[ТС]**

нету

@breate · 31.12.2009, 14:15

тогда 3 возводи в степень 2,5e9 и побитово смещай на 2,5e9,

кста при реализации умножения uint64 вам нужно будет делать проверку разрядности - при простом умножении в секунду не влезешь на компе с 2,5GHZ

@Sich_Taras · 31.12.2009, 14:23 **[ТС]**

Не получиться это уже надо задействовать числа с п.т. и тогда я точно не влезу по времени

Добавлено через 1 минуту
упс провтыкал

Добавлено через 44 секунды
но этот вариант сомневаюсь что прокатит

@manfeese · 31.12.2009, 14:33

Используй Алгоритм быстрого возведения в степень, а результат записывай в строковый массив.

@LeBron23 · 31.12.2009, 15:13

Можно конкретно номер задачи на Контестере?

@Sich_Taras · 01.01.2010, 18:13 **[ТС]**

1245

@odip · 02.01.2010, 08:37

1. максимальное значение uint64 есть 2^64

Ерунда.
Максимальное значение uint64 есть 2^64-1

@pigah · 06.01.2010, 14:21

А если сделать возведение в шестнадцатиричной системе?

@Somebody · 07.01.2010, 13:57

Сообщение от pigah

А если сделать возведение в шестнадцатиричной системе?

Тогда будут лишние проблемы - ответ же нужен в десятичной. При более-менее объёмных вычислениях можно считать в системе по основанию 10^n, например 10000, чтобы произодить меньше операций.

@LeBron23 · 10.01.2010, 18:31

Посмотрел на задачу - сама тема не имеет практической ценности, так как автор решил задачу неверно. У квадратов есть общие стороны - поэтому ответ будет намного меньше.
Самое простое доказание этого - жадником найти ответы для маленьких чисел.
Еще проще - посчитать длину ответа (6 в степени 2500000000), это будет 194... словом, почти 2 миллиарда, тоесть 2 гига. Такое не только в лимит памяти, но и в лимит вывода не лезет. Да и за секунду не посчитать, как не старайся.

@Sich_Taras · 14.01.2010, 17:12 **[ТС]**

Да, ты прав. Нечего сказать.
Ответ, найден это невозможно.

@manfeese 133 / 132 / 29 Регистрация: 04.01.2009 Сообщений: 415
	31.12.2009, 14:33	11
	Используй Алгоритм быстрого возведения в степень, а результат записывай в строковый массив. 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
		1
	Вычисление большой степени числа 6. 31.12.2009, 02:49. Показов 4269. Ответов 17 Метки нет (Все метки) Всем привет! Есть следующая проблема. Нужно возвести число шесть в степень 2500000000 за 1 сек. Ограничения по памяти 5000К. Какие есть идеи ? 0

@breate 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

@fasked 5043 / 2622 / 241 Регистрация: 07.10.2009 Сообщений: 4,310 Записей в блоге: 1
	31.12.2009, 12:38	4
	Может попробовать возводить много раз в квадрат?.. И еще 6 в такой степени громаднейшее число, уверен, что возводить надо не по модулю??? Кстати зачем тебе unsigned long long ??? Во первых это не стандартная переменная, а во вторых, если говорить про скорость, то сработает только на 64-разрядных машинках. 0

@breate 56 / 56 / 6 Регистрация: 23.10.2009 Сообщений: 250
	31.12.2009, 13:19	5
	А откуда эта задачка? 0

@Sich_Taras 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

@breate 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^(108))/264 = 50(10^8)/64 число получится x10[x>5]10^7 а 5mb это 5*10^6 и плюс о маленькое от х точно в условии нет ошибки? 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	31.12.2009, 13:58 [ТС]	8
	нету 0

@breate 56 / 56 / 6 Регистрация: 23.10.2009 Сообщений: 250
	31.12.2009, 14:15	9
	тогда 3 возводи в степень 2,5e9 и побитово смещай на 2,5e9, кста при реализации умножения uint64 вам нужно будет делать проверку разрядности - при простом умножении в секунду не влезешь на компе с 2,5GHZ 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	31.12.2009, 14:23 [ТС]	10
	Не получиться это уже надо задействовать числа с п.т. и тогда я точно не влезу по времени Добавлено через 1 минуту упс провтыкал Добавлено через 44 секунды но этот вариант сомневаюсь что прокатит 0

@LeBron23 10 / 10 / 4 Регистрация: 18.11.2009 Сообщений: 47
	31.12.2009, 15:13	12
	Можно конкретно номер задачи на Контестере? 0

	14.01.2010, 17:12

Опции темы

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	01.01.2010, 18:13 [ТС]	13
	1245 0

@odip 7175 / 3234 / 81 Регистрация: 17.06.2009 Сообщений: 14,164
	02.01.2010, 08:37	14
	1. максимальное значение uint64 есть 2^64 Ерунда. Максимальное значение uint64 есть 2^64-1 0

@pigah 12 / 12 / 5 Регистрация: 05.07.2009 Сообщений: 147 Записей в блоге: 1
	06.01.2010, 14:21	15
	А если сделать возведение в шестнадцатиричной системе? 0

@Somebody 2835 / 1644 / 254 Регистрация: 03.12.2007 Сообщений: 4,222
	07.01.2010, 13:57	16
	Сообщение от pigah А если сделать возведение в шестнадцатиричной системе? Тогда будут лишние проблемы - ответ же нужен в десятичной. При более-менее объёмных вычислениях можно считать в системе по основанию 10^n, например 10000, чтобы произодить меньше операций. 0

@LeBron23 10 / 10 / 4 Регистрация: 18.11.2009 Сообщений: 47
	10.01.2010, 18:31	17
	Посмотрел на задачу - сама тема не имеет практической ценности, так как автор решил задачу неверно. У квадратов есть общие стороны - поэтому ответ будет намного меньше. Самое простое доказание этого - жадником найти ответы для маленьких чисел. Еще проще - посчитать длину ответа (6 в степени 2500000000), это будет 194... словом, почти 2 миллиарда, тоесть 2 гига. Такое не только в лимит памяти, но и в лимит вывода не лезет. Да и за секунду не посчитать, как не старайся. 0

@Sich_Taras 14 / 14 / 4 Регистрация: 08.10.2009 Сообщений: 114
	14.01.2010, 17:12 [ТС]	18
	Да, ты прав. Нечего сказать. Ответ, найден это невозможно. 0