четверг, 27 мая 2010 г.
Длинная арифметика
Теория:
* Первая глава книги Окулова “Программирование в алгоритмах”.
* Раздел 4 Дистанционная подготовка по информатике
* e-maxx
Практика: Дистанционная подготовка
Условные обозначения:
* osn – основание системы счисления
* A,B – “длинные” числа
* n – “короткое”, 0 <= n < osn
Предисловие
Основные операции:
* Ввод
* Вывод
* A + n
* Сравнение
* A + B
* A – B (A >= B)
* A – B (со знаком)
* A * n
* A * B
* A / n, A % n
* A / B, A % B
Дополнительные операции:
* A^n
* n!
* sqrt(A)
* N^N mod 10^P
Экзотика:
* A – n
Подписаться на:
Комментарии к сообщению (Atom)
Большое спасибо! У вас самая лаконичная и понятная реализация из всех, что я видел.
ОтветитьУдалитьКак вы понимаете многое придумал не я. Очень много было взято из реализации Виталия Гольдштейна. А изначальный импульс шел из ранних реализаций длинной арифметики Романа Джабарова. Так что в первую очередь им большое спасибо!
ОтветитьУдалитьРебята, а помогите написать всю программу, где ты вводишь два числа (до 40 ЦИФР) и он считает (+,-,*,/).
ОтветитьУдалитьПо сути все дано, но хочу все вместе одной программой.
Не хочется вам делать медвежью услугу с учетом того, что все составные кирпичики есть. Не очень понимаю, что мешает взять и скопировать все составные функции в один файл исходного кода. Покажите текущую версию вашей программы и задайте конкретный вопрос, что не получается или что не понятно.
УдалитьВопрос: Почему для хранения цифр вы используете тип int? Для арифметики по основанию 10 (наиболее распространённый случай) более чем достаточно хранить цифры в одном байте, и из всех алгоритмов у вас только для A+n необходимо 4 байта, и то, этот алгоритм элементарно делается универсальным:
ОтветитьУдалитьint i=0;
while(b){
digits[i]+=b%osn;
b/=osn;
++i;
}
j=0;
while(j<i || digits[j]>osn){
if(digits[j]>=osn){
digits[j]-=osn;
++digits[++j];
}
}
Извините, глупая ошибка
ОтветитьУдалитьint i=0;
while(b){
digits[i]+=b%osn;
b/=osn;
++i;
}
int j=0;
while(j<i || digits[j]>osn){
if(digits[j]>=osn){
digits[j]-=osn;
++digits[j];
}
++j;
}
4 байта для одной цифры используются для того, чтобы можно было быстро изменить OSN скажем до 1e4 и все операции работали без изменений.
УдалитьПо поводу универсального алгоритма, извините, не понял мысли.
Ну да, но в таких случаях я предпочитаю увеличивать размер цифры только когда это необходимо для решения задачи, поэтому написал универсальный алгоритм, работающий для типа char. Т.к. у меня другие обозначения в классе, я менял их перед постом и допустил ошибки.
ОтветитьУдалитьwhile(b){
digits[i]+=b%osn;
b/=osn;
++i;
}
Число в цикле делится на основание системы, остаток прибавляется к текущей цифре, и переходим к следующей.
int j=0;
while(j<i || digits[j]>osn){
if(digits[j]>=osn){
digits[j]-=osn;
++digits[j];
}
++j;
}
Дабы не просеивать всё число в поисках переполнения, я веду поиск лишь до изменённых цифр, число которых сохранено в переменной i. В теле цикла происходит проверка, не выше ли цифра основания, и если да, следующее число увеличивается на единицу, из текущего вычитается основание. Да, не ++digits[j]; а ++digits[j+1];, опечатка. Цикл происходит до числа i, а дальше только при наличии переполнения (т.е. || digits[j]>osn ).
Кстати, 1e4 = 10000, а вместимость типа short int от -32678 до 32677, так что и его должно хватить :). Сейчас я решаю задачу, в которой предполагается матрица из очень большого количества длинных чисел, так что лично для меня критично, один байт на число или 4. На ваш сайт вышел в поисках путей оптимизации моего быдлокода (мой класс длинной арифметики, написанный ещё на 2-м курсе, был малёк ужасен), за что вам спасибо
ОтветитьУдалитьС основанием 1e4 и типом short нужно быть осторожным, потому что если у вас есть операция умножение, то точно будет переполнение и тогда спасет только int.
ОтветитьУдалитьВозможно задача на матрицу из очень большого количества длинных чисел похожа на задачу "Черепашка", где нужно дойти из левого верхнего в правый нижний угол минимальным/максимальным способом. Обычно в таких задачах не хранят всю матрицу. Вместо этого хранят только несколько последних строк(в задаче черепашка - одну), которые необходимы для вычисления ответа для текущей строки. Если есть возможность - дайте ссылочку на вашу задачу.
Большое СПАСИБО!!!
ОтветитьУдалитьКак скачать готовый код скиньте ссылку
ОтветитьУдалить