Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 13
Помимо оптимизации постоянных копирований памяти:
— в extend_vec можно использовать метод vector::resize
— нужно оптимизировать заглавную картинку (сейчас она размером 1920 на 1920)
— в extend_vec можно использовать метод vector::resize
— нужно оптимизировать заглавную картинку (сейчас она размером 1920 на 1920)
Раз уж вы написали статью о больших числах, то делать, например, вот так:
int n = max(first.size(), second.size());
как-то некорректно. У вас будет переполнение при длине чисел более чем в 2^31 (на x86 и x86-64 в современных компиляторах).
Правильно:
size_t n = max(first.size(), second.size()
Или, если вы уж упомянули C++11, то:
auto n = max(first.size(), second.size());
Ну и во многих других местах тоже.
int n = max(first.size(), second.size());
как-то некорректно. У вас будет переполнение при длине чисел более чем в 2^31 (на x86 и x86-64 в современных компиляторах).
Правильно:
size_t n = max(first.size(), second.size()
Или, если вы уж упомянули C++11, то:
auto n = max(first.size(), second.size());
Ну и во многих других местах тоже.
1. Статья содержит реализацию, значит нужно было вместо основания выбрать не 10 или 100, а 2^k.
И к выбирается обычно таким, чтобы 2^k умещалось в точности в машинное слово.
2. Нужно было привести другие формулы разложения чисел для перемножения для A=A_1 + 2^k A_2, B=B_1 + 2^k B_2
Ваше
A B= A_1 B_1 + 2^k ((A_1 + A_2)(B_1 + B_2) — (A_1 B_1 + A_2 B_2)) + 2^(2k) A_2 B_2
Используется в gmplib.org
A B= A_1 B_1 — 2^k ((A_1 — A_2)(B_1 — B_2) — (A_1 B_1 + A_2 B_2)) + 2^(2k) A_2 B_2
Еще умножение можно заменить возведением в квадрат с той же сложностью.
3. Метод Карацубы начинает выигрывать у обычного умножения на современных компьютерах при размере чисел равных 8 машинным словам. Но это зависит от реализации и конкретного компа.
4. Если разбивать число сразу на r — частей (метод умножения Toom–Cook), то сложность можно довести до O(n^(1+eps)).
5. Самый быстрый метод умножения Шёнхаге — Штрассена основанный на быстром преобразование Фурье имеет сложность O(n log(n) log(log(n))). Фактически его асимптотическая сложность совпадает со сложением и вычитанием.
6. Деление можно заменить умножением на обратный (его для точной арифметики получают алгоритмом основанным на методе Ньютона для приближенного решения нелинейных уравнений) и тогда асимптотическая сложность деления равна сложности умножения.
И к выбирается обычно таким, чтобы 2^k умещалось в точности в машинное слово.
2. Нужно было привести другие формулы разложения чисел для перемножения для A=A_1 + 2^k A_2, B=B_1 + 2^k B_2
Ваше
A B= A_1 B_1 + 2^k ((A_1 + A_2)(B_1 + B_2) — (A_1 B_1 + A_2 B_2)) + 2^(2k) A_2 B_2
Используется в gmplib.org
A B= A_1 B_1 — 2^k ((A_1 — A_2)(B_1 — B_2) — (A_1 B_1 + A_2 B_2)) + 2^(2k) A_2 B_2
Еще умножение можно заменить возведением в квадрат с той же сложностью.
3. Метод Карацубы начинает выигрывать у обычного умножения на современных компьютерах при размере чисел равных 8 машинным словам. Но это зависит от реализации и конкретного компа.
4. Если разбивать число сразу на r — частей (метод умножения Toom–Cook), то сложность можно довести до O(n^(1+eps)).
5. Самый быстрый метод умножения Шёнхаге — Штрассена основанный на быстром преобразование Фурье имеет сложность O(n log(n) log(log(n))). Фактически его асимптотическая сложность совпадает со сложением и вычитанием.
6. Деление можно заменить умножением на обратный (его для точной арифметики получают алгоритмом основанным на методе Ньютона для приближенного решения нелинейных уравнений) и тогда асимптотическая сложность деления равна сложности умножения.
Шёнхаге — Штрассена продержался в лидерах до 2007-го. Алгоритм Фюрера быстрее. Есть еще один, не помню его названия, аналогичный АФ по быстродействию.
- Идея такой реализации, которая приведена здесь, чтобы все переносы делались в конце. И нам необходимо, чтобы все промежуточные результаты умещались в стандартный тип, который может хранить числа до
(причем тип должен быть знаковым, так как в алгоритме Карацубы используется вычитание. Если использовать систему 
, умещая в машинное слово, то где Вы будете хранить результат произведения? Поправьте меня, если я не прав. - Можно добавить, но идея от этого не изменится
- Безусловно. На моей машине до определенной длины числа оба алгоритма работали мгновенно и только после перехода через определенный порог наивный алгоритм стал существенно замедляться.
- Можно, но алгоритм Тома-Кука и делает больше промежуточной работы по разбиению числа на r–частей, поэтому и существенный выигрыш будет при ещё бóльших длинах чисел.
Когда-то, примерно в 1998 году у меня была реализация длинной арифметики на C++. По скорости она в 2-3 раза делала на тот момент GMP. Сейчас я пользуюсь GMP и не заморачиваюсь с ассемблером под конкретный процессор.
И так, идея реализации с минимальным использованием ассемблера. Цифра везде машинное слово, а типы C++ зависят от конкретной архитектуры. Кстати для организации всяких сдвигов нужно знать где расположен значащий бит в начале или в конце машинного слова
struct LongInt {
int mAlloc; \\ размер выделенной памяти
int mSize; \\ abs(mSize) текущий размер числа и sign(mSize) его знак
unsigned int* mLimb; \\ массив цифр
};
unsgned int a, b;
если a+b < a, то произошло переполнение и единичку должны перенести, a+b при этом правильный результат для младшей цифры
если a-b > a, то произошло переполнение и единичку должны занять, a-b при этом правильный результат для младшей цифры
Ассемблер нужен для двузначного умножения и деления. Поскольку с 60-х архитектура большинства процессоров поддерживала создание длинной арифметики (вспомните хотя бы lisp)
при перемножении двух цифр возникает двузначное число, т.е. два машинных слова, просто в обычных языках старшая часть откидывается или выдается переполнение если она не равна нулю
при делении задается две цифры делимого и цифра делителя, в результате цифра частного и цифра остатка
Как выглядит все на разных ассемблерах можно посмотреть в gmplib.org в исходниках в папке mpn. В ней mpn\generic без ассемблера.
И так, идея реализации с минимальным использованием ассемблера. Цифра везде машинное слово, а типы C++ зависят от конкретной архитектуры. Кстати для организации всяких сдвигов нужно знать где расположен значащий бит в начале или в конце машинного слова
struct LongInt {
int mAlloc; \\ размер выделенной памяти
int mSize; \\ abs(mSize) текущий размер числа и sign(mSize) его знак
unsigned int* mLimb; \\ массив цифр
};
unsgned int a, b;
если a+b < a, то произошло переполнение и единичку должны перенести, a+b при этом правильный результат для младшей цифры
если a-b > a, то произошло переполнение и единичку должны занять, a-b при этом правильный результат для младшей цифры
Ассемблер нужен для двузначного умножения и деления. Поскольку с 60-х архитектура большинства процессоров поддерживала создание длинной арифметики (вспомните хотя бы lisp)
при перемножении двух цифр возникает двузначное число, т.е. два машинных слова, просто в обычных языках старшая часть откидывается или выдается переполнение если она не равна нулю
при делении задается две цифры делимого и цифра делителя, в результате цифра частного и цифра остатка
Как выглядит все на разных ассемблерах можно посмотреть в gmplib.org в исходниках в папке mpn. В ней mpn\generic без ассемблера.
Через FT умножение описывалось на хабре?
А, вижу, выше упомянули. FFT алгоритм хорош.
А, вижу, выше упомянули. FFT алгоритм хорош.
Да, вот здесь.
мне кажется или в naive_mul ошибка?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Умножение Карацубы и C++ 11