Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Возведение в степень с показателем свыше 100  (Прочитано 38588 раз)
0 Пользователей и 2 Гостей смотрят эту тему.
rash
Гость
« : 12-10-2006 16:48 » 

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

ua
Offline Offline

« Ответ #1 : 12-10-2006 18:06 » 

Я считаю, что лучше использовать массив целых чисел. И выполнять умножение аналогично ручному умножению в столбик. Только вот хранить элементы числа в массиве удобнее в обратном порядке.
Например:
Код:
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
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 13-10-2006 05:10 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
ysv_
Помогающий

ua
Offline Offline

« Ответ #3 : 13-10-2006 15:00 » 

Так это я предложил один из вариантов решения. Все же лучше чем string использовать.
Записан
rash
Гость
« Ответ #4 : 15-10-2006 07:05 » 

Код протестировал и немного поправил
Код:
int n[300];
на
 
Код:
long int n[300];
Но всё равно,
Цитата
Каждый элемент массива представляет собой число от 0 до 2147483647
и может содержать значение не более, чем 17^7 т.е. 410338673 или не более, чем 32 бита. Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.
Записан
rash
Гость
« Ответ #5 : 15-10-2006 08:44 » 

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

Речь идёт о типе class?
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 15-10-2006 09:05 » 

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

Offline Offline
Пол: Мужской

WWW
« Ответ #7 : 15-10-2006 09:34 » 

https://forum.shelek.ru/index.php/topic,7895.msg116270.html#msg116270
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
rash
Гость
« Ответ #8 : 15-10-2006 11:55 » 

Цитата
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
Гость
« Ответ #9 : 15-10-2006 12:02 » 


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

ru
Offline Offline
Пол: Мужской

« Ответ #10 : 15-10-2006 12:35 » 

Цитата: rash
17^300
Для начала, вы видите разницу между 17^300 и 17E+300? Улыбаюсь

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

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
ysv_
Помогающий

ua
Offline Offline

« Ответ #11 : 15-10-2006 14:55 » 

Цитата
Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.
Уверен???
Записан
rash
Гость
« Ответ #12 : 15-10-2006 15:11 » 

Цитата
Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.
Сделал пошаговое выполнение программы и вот что получил
Цитата
при i = 16,
j = 3,
n:{2116147696, -1202418332, 17,0, 0,......0}
Первое значение массива, это то, что получилось, когда 17 возводится в 8 степень.
Записан
rash
Гость
« Ответ #13 : 15-10-2006 15:25 » 

Цитата
...вы видите разницу между 17^300 и 17E+300?
разница заключается в том, что выполнив эти две операции, мы получим совершенно различные значения

Цитата
Тогда только через последовательность целых чисел.
Я не представляю себе, как это реализовать

Цитата
Хотите поразить чьё-то воображение?
Нет, ничего воображения я поражать этой задачей не хочу. Эта операция часть программы, целью которой является проверка полученных знаний по С\С++
Записан
Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #14 : 15-10-2006 16:03 » 

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

Цитата: rush
Я не представляю себе, как это реализовать
К C/C++ это не имеет ни малейшего отношения. Это обычное знание математики и структур данных.

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 15-10-2006 16:27 » 

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);

Пример из головы - не проверял.
« Последнее редактирование: 15-10-2006 16:33 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
x77
Команда клуба

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #16 : 16-10-2006 18:14 » 

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

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #17 : 16-10-2006 19:37 » 

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

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
RXL
Технический
Администратор

Offline Offline
Пол: Мужской

WWW
« Ответ #18 : 17-10-2006 16:16 » 

В некотором плане рулят ассемблерные вставки, но это не переносимо.
Код:
  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
Гость
« Ответ #19 : 17-10-2006 20:11 » 


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

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #20 : 03-11-2006 12:43 » 

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

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

Dimka
Деятель
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 03-11-2006 15:36 » 

Цитата: x77
из которого и организуется динамический массив TArray = array of Bits.
Это уже Object Pascal из Delphi. В Borland Pascal 7.0 нет ни динамических массивов, ни типа Bit, не говоря уже о "каноническом" Паскале.
« Последнее редактирование: 03-11-2006 15:39 от dimka » Записан

Программировать - значит понимать (К. Нюгард)
Невывернутое лучше, чем вправленное (М. Аврелий)
Многие готовы скорее умереть, чем подумать (Б. Рассел)
x77
Команда клуба

ro
Offline Offline
Пол: Мужской
меняю стакан шмали на обратный билет с Марса.


« Ответ #22 : 03-11-2006 16:45 » new

тип Bit - это мой тип, букву пропустил одну. я ж писал - TBits = (..);
Код:
type
  TBits = set of 1..10;
  TArray = array of TBits;
вполне себе компилябельная конструкция.

динамических массивов как типа данных в классике действительно нет, но они там всю жизнь благополучно реализуются Ага это несущественно, на самом деле. существенно то, что тут сет в принципе не нужен, каюсь, с этим - прогнал.
« Последнее редактирование: 03-11-2006 16:51 от x77 » Записан

tishka17
Участник

ru
Offline Offline
Не разбрасывайте мусор


« Ответ #23 : 04-11-2006 17:25 » 

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

//1001101010110100010100110011101111000010110111010101110011
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #24 : 08-11-2006 10:06 » 

Ответ: (вывод разбит в колонку по 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. Вот вкратце идея алгоритма быстрого возведения в степень.

По-моему, для того, чтобы закодировать эти подзадачи на Си/Си++ и получить искомый результат, не требуется быть гигантом программирования.
« Последнее редактирование: 08-11-2006 10:09 от npak » Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines