Comments 12
Помимо оптимизации постоянных копирований памяти:
— в 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());
Ну и во многих других местах тоже.
UFO just landed and posted this here
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 алгоритм хорош.
Да, вот здесь.
Sign up to leave a comment.
Умножение Карацубы и C++ 11