rash
Гость
|
|
« : 12-10-2006 16:48 » |
|
Требуется возвести целое число, скажем, 17 в степень, например, 300. Очевидно, что результат во встроенные типы double, long double не поместиться. Верным решением считаю присваивание типу string. Но я не представляю, как это реализовать. Подскажите способ выполнения данной операции.
|
|
|
Записан
|
|
|
|
ysv_
Помогающий
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
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #2 : 13-10-2006 05:10 » |
|
ysv, не рационально по памяти, когда не требуется точность представления. Лучше уж реализовать собственный тип вещественных с плавающей запятой, в которой порядок велик и описывается, например, числом типа int.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
ysv_
Помогающий
Offline
|
|
« Ответ #3 : 13-10-2006 15:00 » |
|
Так это я предложил один из вариантов решения. Все же лучше чем string использовать.
|
|
|
Записан
|
|
|
|
rash
Гость
|
|
« Ответ #4 : 15-10-2006 07:05 » |
|
Код протестировал и немного поправил на Но всё равно, Каждый элемент массива представляет собой число от 0 до 2147483647 и может содержать значение не более, чем 17^7 т.е. 410338673 или не более, чем 32 бита. Как только значение выходит за диапазон long int, элементы массива содержат случайные значения.
|
|
|
Записан
|
|
|
|
rash
Гость
|
|
« Ответ #5 : 15-10-2006 08:44 » |
|
Лучше уж реализовать собственный тип вещественных с плавающей запятой Речь идёт о типе class?
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #6 : 15-10-2006 09:05 » |
|
Речь идёт о типе class? Если вы не совсем (или совсем не) знакомы с классами, то лучше поищите себе другие учебные задания. Поскольку классы - это отдельная большая тема для разговора, к представлению больших чисел имеющая косвенное отношение. P.S. Не знаю точно, о каком языке программирования идёт речь. но в C++ для 32-хразрядных машин тип double поддерживает значения порядка до 308 с 15 цифрами мантисы (максимум 1.7E+308).
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
RXL
Технический
Администратор
Offline
Пол:
|
|
« Ответ #7 : 15-10-2006 09:34 » |
|
|
|
|
Записан
|
... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
|
|
|
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
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #10 : 15-10-2006 12:35 » |
|
17^300 Для начала, вы видите разницу между 17^300 и 17E+300? но представление результата в scientific format нежелательно. Цель этого вычисления, получить, например, строку, в которой будет std::string str = "136357..." и ещё 369 цифровых символов. Тогда только через последовательность целых чисел. P.S. А зачем строка со столькими цифрами? Хотите поразить чьё-то воображение? А до вычислительной математики вы ещё не дошли?
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
ysv_
Помогающий
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
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #14 : 15-10-2006 16:03 » |
|
Эта операция часть программы, целью которой является проверка полученных знаний по С\С++ Если вы не знаете про классы, то не знаете C++. Я уже советовал подобрать другую задачу. Я не представляю себе, как это реализовать К C/C++ это не имеет ни малейшего отношения. Это обычное знание математики и структур данных. разница заключается в том, что выполнив эти две операции, мы получим совершенно различные значения Разница заключается в том, что 17E+300 - это не операция, а 17^300 - это не форма представления числа в языке программирования C/C++.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
RXL
Технический
Администратор
Offline
Пол:
|
|
« Ответ #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
Команда клуба
Offline
Пол:
меняю стакан шмали на обратный билет с Марса.
|
|
« Ответ #16 : 16-10-2006 18:14 » |
|
не знаю, как это будет в сях, но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины, в котором каждая ячейка принимает значения от 0 до 9 (это лдя любителей классики). а в принципе никто не мешает юзать уже готовый pchar - по сути, тот же динамический массив. решение задачи сводится к написанию функции для работы и отображения этого типа.
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #17 : 16-10-2006 19:37 » |
|
но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины Нет, паскалевский set - это всего лишь множество битов, где каждый бит соответствует одному элементу множества (в порядке перечисления этих элементов). Т.е. set of 0..9 есть 10 битов, каждый из которых определяет, включена ли цифра во множество или нет. Бит же, как известно, имеет лишь 2 значения.
|
|
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
RXL
Технический
Администратор
Offline
Пол:
|
|
« Ответ #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
Команда клуба
Offline
Пол:
меняю стакан шмали на обратный билет с Марса.
|
|
« Ответ #20 : 03-11-2006 12:43 » |
|
но на паскале можно просто сделать динамически массив из сета. т.е. массив заранее неизвестной длины Нет, паскалевский set - это всего лишь множество битов, где каждый бит соответствует одному элементу множества (в порядке перечисления этих элементов). Т.е. set of 0..9 есть 10 битов, каждый из которых определяет, включена ли цифра во множество или нет. Бит же, как известно, имеет лишь 2 значения. совершенно верно. т.е. имеется нечто типа TBits = (One, two, fre, four....), из которого и организуется динамический массив TArray = array of Bits. проще, конечно, объявить array of byte, но тогда и делать это всё имеет смысл в 256-ричной системе счисления, иначе для каждого знака каждого большого числа мы будем хранить избыточные данные.
|
|
|
Записан
|
|
|
|
Dimka
Деятель
Команда клуба
Offline
Пол:
|
|
« Ответ #21 : 03-11-2006 15:36 » |
|
из которого и организуется динамический массив TArray = array of Bits. Это уже Object Pascal из Delphi. В Borland Pascal 7.0 нет ни динамических массивов, ни типа Bit, не говоря уже о "каноническом" Паскале.
|
|
« Последнее редактирование: 03-11-2006 15:39 от dimka »
|
Записан
|
Программировать - значит понимать (К. Нюгард) Невывернутое лучше, чем вправленное (М. Аврелий) Многие готовы скорее умереть, чем подумать (Б. Рассел)
|
|
|
x77
Команда клуба
Offline
Пол:
меняю стакан шмали на обратный билет с Марса.
|
|
« Ответ #22 : 03-11-2006 16:45 » |
|
тип Bit - это мой тип, букву пропустил одну. я ж писал - TBits = (..); type TBits = set of 1..10; TArray = array of TBits;
вполне себе компилябельная конструкция. динамических массивов как типа данных в классике действительно нет, но они там всю жизнь благополучно реализуются это несущественно, на самом деле. существенно то, что тут сет в принципе не нужен, каюсь, с этим - прогнал.
|
|
« Последнее редактирование: 03-11-2006 16:51 от x77 »
|
Записан
|
|
|
|
tishka17
Участник
Offline
Не разбрасывайте мусор
|
|
« Ответ #23 : 04-11-2006 17:25 » |
|
Да ну вас. Развели болтовню. Это ж стандартная школьно-олимпиадная задачка. (я в своё время возводил 3 в 512 степегь). Стандартное решение через массивы, по принципу умножения столбиком. Для скорости лучше ещё хранить длину заполненной части массива.
|
|
|
Записан
|
//1001101010110100010100110011101111000010110111010101110011
|
|
|
npak
|
|
« Ответ #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 »
|
Записан
|
|
|
|
|