четверг, 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

11 комментариев:

  1. Большое спасибо! У вас самая лаконичная и понятная реализация из всех, что я видел.

    ОтветитьУдалить
  2. Как вы понимаете многое придумал не я. Очень много было взято из реализации Виталия Гольдштейна. А изначальный импульс шел из ранних реализаций длинной арифметики Романа Джабарова. Так что в первую очередь им большое спасибо!

    ОтветитьУдалить
  3. Ребята, а помогите написать всю программу, где ты вводишь два числа (до 40 ЦИФР) и он считает (+,-,*,/).
    По сути все дано, но хочу все вместе одной программой.

    ОтветитьУдалить
    Ответы
    1. Не хочется вам делать медвежью услугу с учетом того, что все составные кирпичики есть. Не очень понимаю, что мешает взять и скопировать все составные функции в один файл исходного кода. Покажите текущую версию вашей программы и задайте конкретный вопрос, что не получается или что не понятно.

      Удалить
  4. Вопрос: Почему для хранения цифр вы используете тип 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];
    }
    }

    ОтветитьУдалить
  5. Извините, глупая ошибка
    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;
    }

    ОтветитьУдалить
    Ответы
    1. 4 байта для одной цифры используются для того, чтобы можно было быстро изменить OSN скажем до 1e4 и все операции работали без изменений.
      По поводу универсального алгоритма, извините, не понял мысли.

      Удалить
  6. Ну да, но в таких случаях я предпочитаю увеличивать размер цифры только когда это необходимо для решения задачи, поэтому написал универсальный алгоритм, работающий для типа 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 ).

    ОтветитьУдалить
  7. Кстати, 1e4 = 10000, а вместимость типа short int от -32678 до 32677, так что и его должно хватить :). Сейчас я решаю задачу, в которой предполагается матрица из очень большого количества длинных чисел, так что лично для меня критично, один байт на число или 4. На ваш сайт вышел в поисках путей оптимизации моего быдлокода (мой класс длинной арифметики, написанный ещё на 2-м курсе, был малёк ужасен), за что вам спасибо

    ОтветитьУдалить
  8. С основанием 1e4 и типом short нужно быть осторожным, потому что если у вас есть операция умножение, то точно будет переполнение и тогда спасет только int.
    Возможно задача на матрицу из очень большого количества длинных чисел похожа на задачу "Черепашка", где нужно дойти из левого верхнего в правый нижний угол минимальным/максимальным способом. Обычно в таких задачах не хранят всю матрицу. Вместо этого хранят только несколько последних строк(в задаче черепашка - одну), которые необходимы для вычисления ответа для текущей строки. Если есть возможность - дайте ссылочку на вашу задачу.

    ОтветитьУдалить