Возвести число в (7) семизначную степень

@Anadrion · Регистрация: 20.11.2012

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

Подскажите пожалуйста, как можно реализовать данную функцию? К примеру необходимо число 2 возвести в 1234567 степень. Проблема заключается в выводе такого большого числа. Зарание благодарен.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cmath>
#include <iostream>
 
    using namespace std;
 
    int main()
        
{
    
setlocale (LC_ALL,"Russian");
 
int long A,B;
 
    cout << "Введите число необходимое возвести в степень\n\t";      
 
    cin >> A;
 
    cout << "Введите необходимую степень\n\t";
 
    cin >>B;
 
    cout << "Равно\n\t" << pow(A,B) << "\n";
 
            cin.get();
 
}

@IrineK · 28.12.2014, 17:52

Если задача в том, чтобы вывести точное значение - то нужна длинная арифметика.

Если задача в том, чтобы просто возвести в степень и получить приблизительное значение мантиссы и порядок - то используйте double.

@zss · 28.12.2014, 18:10

С double можно возвести только в 308 степень.
Только длинная арифметика!

@D_in_practice · 28.12.2014, 18:12

Думаю задача не на длинную арифметику.

Для 5-ти значной степени программа уже работает долго.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <iomanip>
 
const int BASIS = 1000000;
const int N = 10000;
 
using namespace std;
 
void  Transform(int n, int a[], int &n_a);
void Print(int a[], int n_a);
int Max(int a, int b);
void Sum(int a[], int n_a, int b[], int n_b, int c[], int &n_c);
void Product(int a[], int n_a, int b[], int n_b, int c[], int &n_c);
 
int main(){
    
    int in1, n;
    do{
        cout << "in = ";
        cin >> in1;
    }while(in1 < 1 || 100 < in1);
    do{
        cout << "n = ";
        cin >> n;
    }while(n < 1);
    
    int in[N] = {};
    int n_in;
    Transform(in1, in, n_in);
    
    int out[N] = {};
    int n_out;
    Transform(in1, out, n_out);
    
    for (int i = 1; i < n; ++i){
        
        int buf[N] = {};
        int n_buf = n_out;
        for (int j = 0; j < n_out; ++j)
            buf[j] = out[j];
        
        Product(buf, n_buf, in, n_in, out, n_out);
    }
    
    Print(out, n_out);
}
 
void  Transform(int n, int a[], int &n_a){
    
    n_a = 0;
    while (n > 0){
        
        a[n_a] = n%BASIS;
        ++n_a;
        n /= BASIS;
    }
}
 
void Print(int a[], int n_a){
    
    int h = 0;
    int buf = BASIS - 1;
    while(buf > 0){
        buf /= 10;
        ++h;
    }
    
    for (int i = n_a - 1; i >= 0; --i){
        cout << setfill('0') << setw(h) << a[i];
    }
    cout << endl;
}
 
int Max(int a, int b){
    return a > b ? a : b;
}
 
void Sum(int a[], int n_a, int b[], int n_b, int c[], int &n_c){
    
    int p = 0;
    for (int i = 0; i < Max(n_a, n_b); ++i){
        
        c[i] = (a[i] + b[i] + p)%BASIS;
        p = (a[i] + b[i] + p)/BASIS;
    }
    if (p == 0)
        n_c = Max(n_a, n_b);
    else{
        n_c = Max(n_a, n_b);
        c[n_c] = p;
        ++n_c;
    }
}
 
void Product(int a[], int n_a, int b[], int n_b, int c[], int &n_c){
    
    c[0] = 0;
    n_c = 1;
    
    for (int i = 0; i < n_a; ++i){
        
        int buf[N] = {};
        int p = 0;
        for (int j = 0; j < n_b; ++j){
            buf[j] = (a[i]*b[j] + p)%BASIS;
            p = (a[i]*b[j] + p)/BASIS;
        }
        int n_buf = n_b;
        if (p > 0){
            buf[n_buf] = p;
            ++n_buf;
        }
        
        int buf2[N] = {};
        for (int j = 0; j < n_c; ++j)
            buf2[j] = c[j]; 
        int n_buf2 = n_c;
        
        int buf1[N] = {};
        for (int j = i; j < n_buf + i; ++j)
            buf1[j] = buf[j - i];
        int n_buf1 = n_buf + i;
        
        Sum(buf1, n_buf1, buf2, n_buf2, c, n_c);
    }
}

IrineK, думаю Вы правы Спасибо.

@IrineK · 28.12.2014, 18:25

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

К примеру необходимо число 2 возвести в 1234567 степень

А если ответ нужно записать в бинарном виде - задача очень упрощается )
Но это - только с двойками.

Добавлено через 4 минуты

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

С double можно возвести только в 308 степень.

Так степень можно периодически "снимать" и хранить отдельно.
А мантиссу считать дальше.

@Anadrion · 28.12.2014, 18:45 **[ТС]**

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

Если задача в том, чтобы вывести точное значение

Да, задача состоит именно в том, что бы вывести точное значение.

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

А если ответ нужно записать в бинарном виде - задача очень упрощается )

Нет, необходимо получить десятичное значение.

@IrineK · 28.12.2014, 19:14

Тогда:
1) Научитесь умножать строку на число (от 2 до 9)
2) Научитесь складывать строки
3) На основании (1) и (2) постройте умножение строки на любое число

@Anadrion · 28.12.2014, 19:18 **[ТС]**

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

Думаю задача не на длинную арифметику.
Для 5-ти значной степени программа уже работает долго.

Как сделать то-же самое, но для 7-ми значной степени, время отработки программы, не столь важны в данной задаче.

Добавлено через 3 минуты
Что вы имели в виду под:

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

умножать строку

@D_in_practice · 28.12.2014, 19:18

Anadrion, Программа работает для 7-ми значной степени!
Только Вы никогда не дождетесь что она досчитает, и я понятия не имею как написать программу с длинной арифметикой способной посчитать такое за нормальное время.
Со строками еще медленнее.

@volvo · 28.12.2014, 19:23

Что считается "нормальным" временем? Программа с длинной арифметикой вычисляет все 371642 символа числа 2^1234567меньше чем за 5 секунд. Включая вывод на экран. Вполне приемлемое время для таких вычислений...

@IrineK · 28.12.2014, 19:24

Умножать строку:
"797979797979797979797979797979" х 3 =
и умножаем "в столбик": 7 пишем - 2 на ум пошло.

@D_in_practice · 28.12.2014, 20:04

volvo, ну для 2 может и легко посчитать но надо не только для 2 -ки.
Нормальное время 10 секунд.
10^5 умножений длинных чисел за 10 секунд не посчиталось, больше ждать я не смог.

Добавлено через 31 минуту
371642 символа уже не влезает в мои числа,
1^1234567 программа считала 10 секунд
2^12345 около 30 секунд

@Dani · 28.12.2014, 20:16

Можно использовать бинарное возведение в степень - a^b за O(log b)

@IrineK · 28.12.2014, 21:21

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

2^12345 около 30 секунд

Где-то также

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//------------------------------------------------------возведение в степень чисел от 2 до 9
#include <iostream>
#include <vector>
 
void Multiplication (std::vector <int> &base, int multiplicator)
{
    int rest = 0;
    for (int i = base.size()-1 ; i>-1; i--)
    {
        base.at(i) *= multiplicator;
        if (rest)
            base.at(i) += rest;
        rest = base.at(i) / 10;
        base.at(i) %= 10;
    }
 
    if (rest)
        base.insert(base.begin(), rest);
}
 
void Print (std::vector <int> &v)
{
    for (std::vector<int>::iterator it = v.begin(); it != v.end(); it++)
        std::cout << *it;
    std::cout << "\n";
}
 
 
//----------------------------------------------------------------------------
int main()
{   
    int base, power; 
 
    std::cout << "Base b = ";
    std::cin >> base;
    std::cout << "Power p = ";
    std::cin >> power;
 
    std::vector <int> result;
    result.push_back(base);
 
    while(--power)
        Multiplication (result, base);
 
    std::cout << "\n\nResult = ";
    Print (result);
    
    std::cin.sync(); std::cin.get();
    return 0;
}
//-----------------------------------------------------------------------------

Сейчас попробую быстрый алгоритм. Но он - неточный.

@Dani · 28.12.2014, 21:30

IrineK, и почему же он неточный?

Добавлено через 5 минут
Другое дело, что при реализации бинарного возведения в степень потребуется возводить длинное число в квадрат, что накладно по времени - простейшая реализация будет работать за O(n^2), где n - длина числа. В таком случае можно написать алгоритм Карацубы или какой-нибудь из этой области.

@IrineK · 29.12.2014, 02:35

Dani, ну тогда карацубьте )

Добавлено через 5 часов 3 минуты

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

Где-то также

Теперь уже 2^12345 - сразу

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//------------------------------------------------------возведение в степень чисел от 2 до 9
#include <iostream>
#include <vector>
 
typedef unsigned long long ULL; 
const ULL denom = 1000000000000000000; 
 
void Multiplication (std::vector <ULL> &base, ULL multiplicator)
{
    int rest = 0;
    for (int i = base.size()-1 ; i>-1; i--)
    {
        base.at(i) *= multiplicator;
        if (rest)
            base.at(i) += rest;
        
        if (base.at(i) > denom)
        {
            rest = base.at(i) / denom;
            base.at(i) %= denom;
        }
        else
            rest = 0;
    }
 
    if (rest)
        base.insert(base.begin(), rest);
}
 
void Print (std::vector <ULL> &v)
{
    for (std::vector<ULL>::iterator it = v.begin(); it != v.end(); it++)
        std::cout << *it;
    std::cout << "\n";
}
 
 
//----------------------------------------------------------------------------
int main()
{   
    ULL base; 
    int power; 
 
    std::cout << "Base b = ";
    std::cin >> base;
    std::cout << "Power p = ";
    std::cin >> power;
 
    std::vector <ULL> result;
    result.push_back(base);
 
    while(--power)
        Multiplication (result, base);
 
    std::cout << "\n\nResult = ";
    Print (result);
    
    std::cin.sync(); std::cin.get();
    return 0;
}
//-----------------------------------------------------------------------------

@nonedark2008 · 29.12.2014, 02:58

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

Сейчас попробую быстрый алгоритм. Но он - неточный.

Можешь попробовать еще и алгоритм быстрого умножения. Например, алгоритм Карацубы...

@D_in_practice · 29.12.2014, 08:13

Мысль появилась после этого поста:

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

Можно использовать бинарное возведение в степень - a^b за O(log b)

Придумал простой алгоритм:
3^6 = 0*3^1 * 1*3^2 * 1*3^4 (6 = 2 + 4)

6 | 0 (6%2 = 0) 6/2 = 3
3 | 1 (3%2 = 1) 3/2 = 1
1 | 1 (1%2 = 1) 1/2 = 0

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//out = in^n
LONG in;
int n;
LONG out = 1;
LONG p = in;
while (n > 0){
    
    if (n%2 == 1)
        out *= p;
    n /= 2;
    p *= p;
}
 
Print(out);

2^24 = 16 777 216 > 9 999 999 (итого не более 2*24 = 48 умножений больших чисел)
(моя программа не тянет, запутался пытаясь переписать на динамические массивы (в обычные число не влезает))
PS позже допишу обязательно.

Добавлено через 23 минуты
было

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

Сейчас попробую быстрый алгоритм. Но он - неточный.

Добавлено через 4 минуты
Хотя нет, где деление степени на 2

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

C++
1
2
while(--power)
* * * * Multiplication (result, base);

@IrineK · 29.12.2014, 11:39

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

Можешь попробовать еще и алгоритм быстрого умножения.

Хорошо бы кто-то еще попробовал.

Добавлено через 2 минуты

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

Хотя нет, где деление степени на 2

Пост 16 - это просто улучшение поста 14. Умножение происходит in chunks по 18 позиций.
Что ускоряет процесс.
Не более того.

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	28.12.2014, 17:52
	Если задача в том, чтобы вывести точное значение - то нужна длинная арифметика. Если задача в том, чтобы просто возвести в степень и получить приблизительное значение мантиссы и порядок - то используйте double. 2

@zss Модератор 13773 / 10966 / 6491 Регистрация: 18.12.2011 Сообщений: 29,245
	28.12.2014, 18:10
	С double можно возвести только в 308 степень. Только длинная арифметика! 1

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	28.12.2014, 19:14
	Тогда: 1) Научитесь умножать строку на число (от 2 до 9) 2) Научитесь складывать строки 3) На основании (1) и (2) постройте умножение строки на любое число 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	28.12.2014, 19:18
	Anadrion, Программа работает для 7-ми значной степени! Только Вы никогда не дождетесь что она досчитает, и я понятия не имею как написать программу с длинной арифметикой способной посчитать такое за нормальное время. Со строками еще медленнее. 0

@volvo Супер-модератор 33399 / 21509 / 8236 Регистрация: 22.10.2011 Сообщений: 36,907 Записей в блоге: 12
	28.12.2014, 19:23
	Что считается "нормальным" временем? Программа с длинной арифметикой вычисляет все 371642 символа числа 2^1234567меньше чем за 5 секунд. Включая вывод на экран. Вполне приемлемое время для таких вычислений... 1

@IrineK 2023 / 1641 / 425 Регистрация: 23.02.2011 Сообщений: 6,002 Записей в блоге: 25
	28.12.2014, 19:24
	Умножать строку: "797979797979797979797979797979" х 3 = и умножаем "в столбик": 7 пишем - 2 на ум пошло. 0

@D_in_practice 343 / 343 / 331 Регистрация: 02.10.2014 Сообщений: 666
	28.12.2014, 20:04
	volvo, ну для 2 может и легко посчитать но надо не только для 2 -ки. Нормальное время 10 секунд. 10^5 умножений длинных чисел за 10 секунд не посчиталось, больше ждать я не смог. Добавлено через 31 минуту 371642 символа уже не влезает в мои числа, 1^1234567 программа считала 10 секунд 2^12345 около 30 секунд 0

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	28.12.2014, 20:16
	Можно использовать бинарное возведение в степень - a^b за O(log b) 1

@Dani 1406 / 648 / 135 Регистрация: 11.08.2011 Сообщений: 2,299 Записей в блоге: 2
	28.12.2014, 21:30
	IrineK, и почему же он неточный? Добавлено через 5 минут Другое дело, что при реализации бинарного возведения в степень потребуется возводить длинное число в квадрат, что накладно по времени - простейшая реализация будет работать за O(n^2), где n - длина числа. В таком случае можно написать алгоритм Карацубы или какой-нибудь из этой области. 0