Возведение в степень с показателем свыше 100

[rash]

Требуется возвести целое число, скажем, 17  в степень, например, 300.
Очевидно, что результат во встроенные типы double, long double не поместиться. Верным решением считаю присваивание типу string.  Но я не представляю, как это реализовать. Подскажите способ выполнения данной операции.

[ysv_]

Я считаю, что лучше использовать массив целых чисел. И выполнять умножение аналогично ручному умножению в столбик. Только вот хранить элементы числа в массиве удобнее в обратном порядке.
Например:

Код:

int n[300];
for (int i=0; i<300; ++i) n[i]=0;
n[0]=17;
for (i=2; i<=300; ++i)
{
  for (j=0; j<300 && n[j]!=0; ++j)
  {
    n[j]*=17;
    if(n[j]<0) 
    {
      n[j+1]&=0x7fffffff;
      ++n[j+1];
    }
  }
}

Код не тестирован. Каждый элемент массива представляет собой число от 0 до 2147483647 (то есть цифру в 2147483648 системе счисления).

[Dimka]

ysv, не рационально по памяти, когда не требуется точность представления. Лучше уж реализовать собственный тип вещественных с плавающей запятой, в которой порядок велик и описывается, например, числом типа int.

[ysv_]

Так это я предложил один из вариантов решения. Все же лучше чем string использовать.

[rash]

Код протестировал и немного поправил

Код:

int n[300];

на
 

Код:

long int n[300];

Но всё равно,

Каждый элемент массива представляет собой число от 0 до 2147483647

и может содержать значение не более, чем 17^7 т.е. 410338673 или не более, чем 32 бита. Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.

[rash]

Лучше уж реализовать собственный тип вещественных с плавающей запятой

Речь идёт о типе class?

[Dimka]

Речь идёт о типе class?

Если вы не совсем (или совсем не) знакомы с классами, то лучше поищите себе другие учебные задания. Поскольку классы - это отдельная большая тема для разговора, к представлению больших чисел имеющая косвенное отношение.

P.S. Не знаю точно, о каком языке программирования идёт речь. но в C++ для 32-хразрядных машин тип double поддерживает значения порядка до 308 с 15 цифрами мантисы (максимум 1.7E+308).

[RXL]

https://forum.shelek.ru/index.php/topic,7895.msg116270.html#msg116270

[rash]

C++ для 32-хразрядных машин тип double поддерживает значения порядка до 308 с 15 цифрами мантисы (максимум 1.7E+308).

Не могу с вами не согласиться.
Реализовал операцию возведения в степень на С++ 17^300 с помощью long double  и получил ответ
17^300 = 1.36357e+369, но представление результата в scientific format нежелательно.
Цель этого вычисления, получить, например, строку, в которой будет
std::string str = "136357..."  и ещё 369 цифровых символов.

[rash]

https://forum.shelek.ru/index.php/topic,7895.msg116270.html#msg116270

Просмотрел вашу ссылку и должен сказать, что использовать какие - то стандартные библиотеки, также, нежелательно. Этим и сложна данная задача.

[Dimka]

17^300

Для начала, вы видите разницу между 17^300 и 17E+300?

но представление результата в scientific format нежелательно.
Цель этого вычисления, получить, например, строку, в которой будет
std::string str = "136357..."  и ещё 369 цифровых символов.

Тогда только через последовательность целых чисел.

P.S. А зачем строка со столькими цифрами? Хотите поразить чьё-то воображение? А до вычислительной математики вы ещё не дошли?

[ysv_]

Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.

Уверен???

[rash]

Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.

Сделал пошаговое выполнение программы и вот что получил

при i = 16,
j = 3,
n:{2116147696, -1202418332, 17,0, 0,......0}

Первое значение массива, это то, что получилось, когда 17 возводится в 8 степень.

[rash]

...вы видите разницу между 17^300 и 17E+300?

разница заключается в том, что выполнив эти две операции, мы получим совершенно различные значения

Тогда только через последовательность целых чисел.

Я не представляю себе, как это реализовать

Хотите поразить чьё-то воображение?

Нет, ничего воображения я поражать этой задачей не хочу. Эта операция часть программы, целью которой является проверка полученных знаний по С\С++

[Dimka]

Эта операция часть программы, целью которой является проверка полученных знаний по С\С++

Если вы не знаете про классы, то не знаете C++. Я уже советовал подобрать другую задачу.

Я не представляю себе, как это реализовать

К C/C++ это не имеет ни малейшего отношения. Это обычное знание математики и структур данных.

разница заключается в том, что выполнив эти две операции, мы получим совершенно различные значения

Разница заключается в том, что 17E+300 - это не операция, а 17^300 - это не форма представления числа в языке программирования C/C++.

[RXL]

rash, см.:
Есть тип unsigned char, размером 8 бит. Если сложить два значения такого типа и результат выйдет за предел диапазона типа, то в результате получится (значение1 + значение2 - 256). 256 - это значение 9-го бита, для хранения которого не хватило места. Если использовать тип unsigned short, то 9-й бит будет сохранен, но не сохранится 17-й бит. Аналогично с 32-х битными величинами: не сохраняется 33-й бит. Ситуацию переноса бита можно съэмулировать. Для малоразмерных типов это бессмысленно, т.к. базовая арифметика процессора может это сделать быстрее. В ассемблере есть операции суммирования с учетом флага переноса, но в С возможности получить его значение нет. Справится с этим можно: использовать в его качестве один из битов.

Код:

#define SIZE 2

unsigned long x[SIZE] = { 0x6299ADA1, 0x000001D5 }; // 17^10 = 2015993900449 = 0x01D56299ADA1
unsigned long y[SIZE] = { 0x00000000, 0x10000000 }; // 2^60 = 1152921504606846976 = 0x1000000000000000

void add(unsigned long * dst, unsigned long * src)
{
	int i;
	int cf = 0;
	unsigned long x, y, z = 0;

	for (i = SIZE * 2 - 1; i >= 0; i--)
	{
		if (i & 1)
		{
			x = dst[i >> 1] & 0x0000ffff;
			y = src[i >> 1] & 0x0000ffff;
			z = 0;
		}
		else
		{
			x = (dst[i >> 1] & 0xffff0000) >> 16;
			y = (src[i >> 1] & 0xffff0000) >> 16;
		}

		x += y + cf;
		
		cf = (x & 0x00010000) >> 16;

		if (i & 1)
		{
			z = x & 0x0000ffff;
		}
		else
		{
			dst[i >> 1] = z | ((x &0x0000ffff) << 16);
		}
	}
}

add(x, y);

Пример из головы - не проверял.

[x77]

не знаю, как это будет в сях, но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины, в котором каждая ячейка принимает значения от 0 до 9 (это лдя любителей классики). а в принципе никто не мешает юзать уже готовый pchar - по сути, тот же динамический массив. решение задачи сводится к написанию функции для работы и отображения этого типа.

[Dimka]

но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины

Нет, паскалевский set - это всего лишь множество битов, где каждый бит соответствует одному элементу множества (в порядке перечисления этих элементов). Т.е. set of 0..9 есть 10 битов, каждый из которых определяет, включена ли цифра во множество или нет. Бит же, как известно, имеет лишь 2 значения.

[RXL]

В некотором плане рулят ассемблерные вставки, но это не переносимо.

Код:

  push esi
  push edi
  push eax
  push ebx
  mov esi, offset src
  mov edi, offset dst
  mov ebx, SIZE
  or eax,eax
  cld
loop:
  lodsd
  adc eax, [edi]
  stosd
  dec ebx
  jnz loop
  pop ebx
  pop eax
  pop edi
  pop esi

Кажись так.

[rash]

поясните, пожалуйста, код с переносом бита

[x77]

но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины

Нет, паскалевский set - это всего лишь множество битов, где каждый бит соответствует одному элементу множества (в порядке перечисления этих элементов). Т.е. set of 0..9 есть 10 битов, каждый из которых определяет, включена ли цифра во множество или нет. Бит же, как известно, имеет лишь 2 значения.

совершенно верно. т.е. имеется нечто типа TBits = (One, two, fre, four....), из которого и организуется динамический массив TArray = array of Bits. проще, конечно, объявить array of byte, но тогда и делать это всё имеет смысл в 256-ричной системе счисления, иначе для каждого знака каждого большого числа мы будем хранить избыточные данные.

[Dimka]

из которого и организуется динамический массив TArray = array of Bits.

Это уже Object Pascal из Delphi. В Borland Pascal 7.0 нет ни динамических массивов, ни типа Bit, не говоря уже о "каноническом" Паскале.

[x77]

тип Bit - это мой тип, букву пропустил одну. я ж писал - TBits = (..);

Код:

type
  TBits = set of 1..10;
  TArray = array of TBits;

вполне себе компилябельная конструкция.

динамических массивов как типа данных в классике действительно нет, но они там всю жизнь благополучно реализуются это несущественно, на самом деле. существенно то, что тут сет в принципе не нужен, каюсь, с этим - прогнал.

[tishka17]

Да ну вас. Развели болтовню. Это ж стандартная школьно-олимпиадная задачка. (я в своё время возводил 3 в 512 степегь). Стандартное решение через массивы, по принципу умножения столбиком.
Для скорости лучше ещё хранить длину заполненной части массива.

[npak]

Ответ: (вывод разбит в колонку по 50 символов)
13635667841726504833065006828934817891150425150972
69813202199325817990578496997872819196533548768205
71922220420991794336317758587605300310161244797419
21798939728519587803961688889648966229091648363412
61263024651655682746072802333755507881671441880797
44466834850500841628797596972234098268520648615251
55135442199676153965214034403450142060442356736474
96763429282184824001

Вычислено в стандартном юниксовом калькуляторе bc.

Эта задача состоит из трёх частей - представление больших целых чисел, перемножение больших чисел и возведение в степень.

Идея использовать массив десятичных цифр для представления больших чисел имеет одно (но зато какое!) преимущество перед шестнадцатиричным представлением - десятичное готово для вывода на печать.  Попробуйте преобразовать шестнадцатиричное число размером 300 шестнадцатиричных цифр в десятичное. Это фокус, сравнимый по сложности с возведением в степень 300.
Поборникам оптимизации затрат памяти стоит обратить внимание, что размер результата в десятичном представлении (370 байтов) всего в два с половиной раза превосходит по-байтное представление (154 байта).  Экономия незначительна, а усложнение отладки и ввода/вывода громадное.  Если всё-таки жаба душит, то вместо арифметики по основанию 10 можно вести вычисления по основанию 10^9 - хранить число как последовательность 32-х разрядных слов, но в каждом слове значение не более одного миллиарда.  В таком представлении результат занимает 164 байта, что всего на 9% хуже побайтного хранения.  Есть и дальнейшие пути оптимизации представления - например, не хранить длинные последовательности нулей, вместо этого разбивать число на набор чисел поменьше.

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

Третья часть - возведение в степень. Перемножение больших чисел - операция не дешёвая, поэтому в общем случае стараются уменьшить число перемножений.  Можно заметить, что 17^300 = (17^150)^2, то есть надо возвести 17 в степень 150, а потом результат в квадрат.  Экономия в два раза.  Дальше больше: 17^150 = (17^75)^2.  17^75 = 17*(17^37)^2, и так далее до 17^2.  Вместо 300 перемножений потребуется около 10. Вот вкратце идея алгоритма быстрого возведения в степень.

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