Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 71, средняя оценка - 4.69
Win32
25 / 24 / 0
Регистрация: 18.08.2009
Сообщений: 126
#1

Алгоритмы возведения числа в большую степень. - C++

27.09.2009, 18:04. Просмотров 9481. Ответов 23
Метки нет (Все метки)

Здраствуйте ещё раз, уважаемые программисты!

Сразу извинюсь за столь надоедливость, но поймите меня правильно, помочь больше некому =(
Как только стану похожим на вас, обязательно буду помогать другим, так же как и вы!!! Огромное вам спасибо за то, что у меня есть возможность к вам обратиться со своими проблемами.

И так, ближе к делу...

Вот на данный момент меня интересует любой алгоритм возведения числа в большую степень, вот напроимер как у меня. Возвести 20 в 57ую степень.

Как с этим справиться? Зациклить то я могу, не вопрос, но есть какой то другой алгоритм с использованием массивов да не в int не в long int резудьтат не помещаеться.

В интернете нарыл только самопальную функцию power() - может алгоритм и лучше, однако результат вычесления такого числа всё равно в int не помещаеться =((((

Подскажите пожалуйста хоть в какую сторону копать! Заранее спасибо!
Ваш подражатель - Win32
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.09.2009, 18:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритмы возведения числа в большую степень. (C++):

Написать функцию возведения числа в степень - C++
нужна функция возведения в степень чтобы возвращала результат.... int involution(int a,int b) { cout<<pow(2,3); return ??? ...

Программа для возведения числа в степень - C++
Здравствуйте. Преподаватель остался недовольным, из-за того, что я это реализовал через готовый оператор, а надо через цикл(а как это...

Найти ошибку в программе возведения числа в степень - C++
#include <iostream> #include <conio.h> #include <cmath> using namespace std; int a; int b; int c; float r; int d; int...

Составить программу возведения числа n в целую степень - C++
Составить программу возведения числа n в целую степень. Правильно выбирайте раздел для размещения задачи

Программа возведения комплексного числа в вещественную степень !!! - C++
Программа возведения комплексного числа в вещественную степень : (a+Bi) в степени c (по формуле Муавра) Ввод вещественных значений...

Возведения числа в целую положительную и отрицательную степень - C++
Запрограммируйте алгоритм возведения числа в целую положительную и отрицательную степень. Пользователь вводит данные с клавиатуры....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,368
27.09.2009, 18:59 #2
Копай в сторону так называемых "библиотек для длинной арифметики", можешь для начала задать свой вопрос гуглу. Например, вот: http://gmplib.org/
Можешь использовать готовые, можешь попробовать написать свою реализацию....
Кстати, 20^57 = 144115188075855872000000000000000000000000000000000000000000000000000000000.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
27.09.2009, 19:05 #3
Очень рекомендую книгу "С++. Освой на примерах" М. Динман. Стр. 109, п. 4.6. Арифметика больших чисел.
Win32
25 / 24 / 0
Регистрация: 18.08.2009
Сообщений: 126
27.09.2009, 19:08  [ТС] #4
Да нельзя использовать какие либо свои типы или реализации типов для хранения такого числа в переменной... =(((
XuTPbIu_MuHTAu
Эксперт С++
2224 / 739 / 10
Регистрация: 27.05.2008
Сообщений: 1,508
27.09.2009, 19:46 #5
Цитата Сообщение от Win32 Посмотреть сообщение
Да нельзя использовать какие либо свои типы или реализации типов для хранения такого числа в переменной... =(((
К сожалению,это неправильный подход.Фактически,внутренняя реализация своего типа инкапсулирует в себе те же операции с массивом,к примеру.
Win32
25 / 24 / 0
Регистрация: 18.08.2009
Сообщений: 126
27.09.2009, 20:12  [ТС] #6
Может и не правельный, но таково задание мое :'(
Nick Alte
Эксперт С++
1636 / 1008 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
27.09.2009, 20:17 #7
А насколько нужно иметь именно само это число? Просто в таких случаях гораздо проще работать с логарифмом. Скажем, по основанию 10. Возведение в степень заменяется умножением логарифма на показатель степени, по целой части результата можно легко судить о порядке результата, по дробной - о мантиссе.
Win32
25 / 24 / 0
Регистрация: 18.08.2009
Сообщений: 126
27.09.2009, 20:31  [ТС] #8
Nick Alte, а можно по-подробнее??? Заранее спасибо!
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 20:41 #9
2Win32: Ты полностью задание скажи !!!

А вообще возведение в большую степень:
Разложим 57 на степени двойки: 57=32+16+8+1
Далее последовательно считаем 20^2, 20^4, 20^8, 20^16, 20^32 с помощью возведения 20 в квадрат много раз.
Потом перемножаем 20^57=20^1 * 20^8 * 20^16 * 20^32

Добавлено через 46 секунд
нельзя использовать какие либо свои типы или реализации типов для хранения такого числа в переменной
Не используй - сделай сам такую реализацию
Win32
25 / 24 / 0
Регистрация: 18.08.2009
Сообщений: 126
27.09.2009, 20:45  [ТС] #10
odip, а можно вот этот алгоритм каким нибудь кусочком кода? Не могу разобраться с динамикой )))
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 20:52 #11
Нету у меня кусочка кода.
Делай по частям - сначала разложить число на степени 2-ки.
Но только учти что если число большое, то все равно в long не войдет.
Так что без длинной арифметики не обойтись !
Nick Alte
Эксперт С++
1636 / 1008 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
27.09.2009, 21:12 #12
Обязательно ли иметь дело именно с целым числом? Может, и double сгодится? Тогда всё сведётся просто к вызову функции pow:
C++
1
2
#include <math.h>
double result = pow(20.0, 57.0);
А для совсем больших чисел можно пользоваться логарифмами. Например, возведение 25 в степень 154 можно сделать так:
C++
1
2
3
4
5
double lg25_10 = log10(25);    // Логарифм 25 по основанию 10
double lg_result = lg25_10 * 154;    // Логарифм от (25^154) получается умножением
int result_exp = static_cast<int>(floor(lg_result));  // Целая часть логарифма даёт десятичный порядок результата
double result_mantissa = lg_result - result_exp;  // Из дробной части можно получить мантиссу
printf("25 в степени 154 = %f * 10^%d", pow(10.0, result_mantissa), result_exp);
Если возможно в дальнейшем пользоваться логарифмом вместо самого результата, или возможно внести соответствующие изменения в вычисления, это может оказаться довольно удобно. Ну а при использовании обычных целых чисел надо помнить, что их предел - около 2 миллиардов для знаковых и 4 миллиарда для беззнаковых, что не так уж и много.
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
27.09.2009, 21:21 #13
Не совсем стандартный тип __int64 ( int64_t ) имеет 64 бита, в отличии от обычного int, который 32 бита.
Nick Alte
Эксперт С++
1636 / 1008 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
27.09.2009, 21:31 #14
В общем, всё зависит от того, чего надо добиться. 20^57 = (1.441 * 10^74), что не умещается и в int64 (предел беззнакового int64 составляет около 1.84 * 10^19).
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,368
27.09.2009, 21:31 #15
Идея с логарифмами может подойти, если требования к точности вычислений это позволят. Необходимо только помнить, что точно вычислить, например, 20^57 таким методом не удастся.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.09.2009, 21:31
Привет! Вот еще темы с ответами:

Как работает алгоритм возведения числа a в степень n ? - C++
Добрый день! Собственно, вопрос не по коду, а по алгоритму Почему после выполнения этой программы в res содержится значение an ? Как оно...

Возведение большого числа в большую степень - C++
Появился вопрос. Реализовую алгоритм Диффи — Хеллмана и не могу возвести 300-значное число в 100-значную степень). Делать циклом - вообще...

Возведение дробного числа в большую степень - C++
Есть закон биномиального распределения. Я смог разобраться с подсчетом числа сочетаний для больших n. Теперь проблема заключается в том,...

Составьте программу возведения данного натурального числа а в степень п - C++
Составьте программу возведения данного натурального числа а в степень p. с помошью while, repeat, for


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
27.09.2009, 21:31
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru