Ты ж уже давно писал, что сделал Фюрера, зачем спрашиваешь?
А вообще смотри в GMP, например. Там чёткая иерархия по размеру входных данных: сначала столбик, потом идут варианты Тоома-Кука (Карацуба — его вариант для 2*2), потом Шёнхаге-Штрассен... Фюрера там вроде нет.
Здравствуйте, netch80, Вы писали:
N>Ты ж уже давно писал, что сделал Фюрера, зачем спрашиваешь?
Ну, у меня Фюрер был сделан для BCD чисел произвольного размера с плавающей точкой, а сейчас для полноты решил запилить BigInt с цифрами по основанию 2^N, решил попробовать Карацубу.
N>А вообще смотри в GMP, например. Там чёткая иерархия по размеру входных данных: сначала столбик, потом идут варианты Тоома-Кука (Карацуба — его вариант для 2*2), потом Шёнхаге-Штрассен... Фюрера там вроде нет.
У меня в итоге получилось для size<12 — столбиком быстрее, size<100 — Фюрер, а потом Фюрер резко деградирует, и Карацуба на порядки начинает его опережать.
Size — это суммарный размер двух векторов. Хз, может, правильнее сравнивать каждый размер и объединить по ИЛИ
Здравствуйте, netch80, Вы писали:
N>А вообще смотри в GMP, например. Там чёткая иерархия по размеру входных данных: сначала столбик, потом идут варианты Тоома-Кука (Карацуба — его вариант для 2*2), потом Шёнхаге-Штрассен... Фюрера там вроде нет.
Шёнхаге-Штрассен: Метод считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был изобретён алгоритм Фюрера с лучшей оценкой сложности[3].
Здравствуйте, Marty, Вы писали:
M>У меня в итоге получилось для size<12 — столбиком быстрее, size<100 — Фюрер, а потом Фюрер резко деградирует, и Карацуба на порядки начинает его опережать.
У тебя Фюрер, значит, как-то убойно неэффективно сделан.
M>Size — это суммарный размер двух векторов. Хз, может, правильнее сравнивать каждый размер и объединить по ИЛИ
Фактически для умножения меряют по меньшему. Потому что, например, умножение чего-то в 200000 цифр на что-то в 1000 цифр раскладывается в 200 умножений 1000*1000 с последующим сдвигом и сложением — то есть по большему размеру оно уже O(N).
M>Шёнхаге-Штрассен: Метод считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был изобретён алгоритм Фюрера с лучшей оценкой сложности[3].
M>GMP, похоже, сильно древний
Нет, не древний. Его поддерживают и постоянно развивают.
Ты посмотри, при каком размере числа Фюрер начинает выигрывать у Ш-Ш.
However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.
(википедия)
Я не знаю, что для них impractically large, но уверен, что это явно больше, чем, например, 100кбит
However, these latter algorithms are only faster than Schönhage–Strassen for impractically large inputs.
(википедия)
N>>Я не знаю, что для них impractically large, но уверен, что это явно больше, чем, например, 100кбит
S>Ну в первой ссылке на русскую вики: S>
S>Однако разница по времени между алгоритмами становится заметной при очень больших перемножаемых числах (больше 10 000 000 000 000[3] значащих цифр).
Ну у них ссылка ведёт куда-то, где реально этой цифры нет, в версиях по ссылкам. Так что точный источник этой цифры непонятен. А вот это говорит про 2^2^64... мнэээ... это должно быть ≈5.6*10^18 цифр, что на почти 9 порядков больше, чем вы привели. Так что всё ещё веселее, и нормально таки, что Ш-Ш сохраняется почти везде.
Как следует из описания метода Карацюбы, вместо четырех умножений потребуется три. Например, если нужно перемножить число из 4-х блоков, не принципиально в какой разрядности, на число из 3-х блоков, то на аппаратном уровне потребуется 12 команд mul при умножении столбиком, соответственно по Карацюбе — только 9. Я тут посчитал, по моему методу тоже потребуется 9 умножений, но это реально заумь.
Смотри, квадрат x отличается от квадрата соседнего числа x + 1 на 2x + 1, это школьники знают. Мы, в отличие от школьников, понимаем, что основание квадрата изменяется при добавлении 1 в 0-й бит. И можем построить формулу при инкрементировании любого бита:
2^(i + 1) * x + 2^(2i), где i — индекс инкрементируемого разряда. Подставь вместо i нолик, получишь "школьную" формулу.
А теперь представим, что добавляем не по одному биту, а целым блоком по смещению i (по границе блока) — как изменится формула? А вот так:
2^(i + 1) * x * y + 2^(2i) * y^2, где y — целый блок битов.
Известно, что любое произведение нечетных чисел можно представить в виде разницы квадратов (метод факторизации Ферма). У нас как бы обратная задача, нам не разложить число надо, а получить. Короче, вычисляем не произведение, а разность квадратов. У меня получается столько же умножений, сколько у Карацюбы. Есть один минус, по крайней мере для тебя: формула расчитана на двоичный формат, а ты, помнится, пилишь десятичный.
P.S. Прикинул еще раз — можно исхмтриться, и в исходном примере обойтись не 9, а 7 умножениями. Семью, Марти! Пошли на Абеля, а? На подсанкционного...
P.P.S. И все же 9... Квадрат у игрека забыл подставить... отбой с Абелем.
Здравствуйте, ravik, Вы писали:
R>Известно, что любое произведение нечетных чисел можно представить в виде разницы квадратов (метод факторизации Ферма). У нас как бы обратная задача, нам не разложить число надо, а получить. Короче, вычисляем не произведение, а разность квадратов. У меня получается столько же умножений, сколько у Карацюбы. Есть один минус, по крайней мере для тебя: формула расчитана на двоичный формат, а ты, помнится, пилишь десятичный.
Не, не десятичный. Десятичный запилил уже давно, худо бедно работает, сейчас запилил двоичный BigInt, ему на пару, но чтобы был пошустрее десятичного, и искал, что побыстрее будет, чем столбик.
R>P.S. Прикинул еще раз — можно исхмтриться, и в исходном примере обойтись не 9, а 7 умножениями. Семью, Марти! Пошли на Абеля, а? На подсанкционного... R>
На какого Абеля? Какой-то форум математиков? Из меня математик, как из говна пуля Я просто запилил алгоритмы
R>P.P.S. И все же 9... Квадрат у игрека забыл подставить... отбой с Абелем. R>
Здравствуйте, Marty, Вы писали:
M>Пинать можно это
Ну ты... монстр!
Если чего, умею генерить произведения множителей с разными знаками, не тратя время на дополнительный код. Но это только потому, что контролирую позицию старшего значащего разряда (ПСЗР), у тебя, как я понял, в BigInt'е такой штуки нет. А зря! Минимум выиграл бы на операторах сравнения.
Здравствуйте, ravik, Вы писали:
M>>Пинать можно это
R>Ну ты... монстр! R>
Да ладно, там ничего такого нет, ну, может, умножения только не совсем просты, но я ж просто готовые алгоритмы реализовал
R>Если чего, умею генерить произведения множителей с разными знаками, не тратя время на дополнительный код. Но это только потому, что контролирую позицию старшего значащего разряда (ПСЗР), у тебя, как я понял, в BigInt'е такой штуки нет. А зря! Минимум выиграл бы на операторах сравнения. R>
Да, у меня знак отдельно хранится, в целом знаковом, в виде значений -1, 0, 1. Не уверен, что так медленнее. Первичное сравнение идёт по знаку, и если знаки разные, дальше в память лазать не надо. Опять же, инверсия знака и проверка на ноль/не ноль производятся без обращения к значению, которое может лежать в отдельной памяти. А это довольно частые операции
Здравствуйте, Marty, Вы писали:
M>На какого Абеля? Какой-то форум математиков? Из меня математик, как из говна пуля Я просто запилил алгоритмы
Марти, чтобы ответить на этот твой пост, я думал... сегодня 9 июля... Больще 2-х недель, вот. Прикинь, люди бы столько репу чесали, прежде чем постить свою дурь в сеть?! К сожалению, исторически — кмк — процесс пошел в другом направлении...
И вот какая каша сварилась. Нет, сначала только что пришедшее на ум: в детстве книгу читал, думаю, ты тоже — там террористы стреляли ледяными пулями. Правда-правда! Типа, не магазин, а специальный охлаждающий контейнер для патронов, а пули, попав в тело, таяли, оставляя в дураках экспертов по баллистике. Ну а нам придется делать пули из той субстанции, которую ты предлагаешь. Ну, раз ничего больше не осталось — из чего делать-то!?
И вот после первой недели случился первый приход. Не подумай чего, Музы конечно.
x 0001
0001
----------
00000001
+1111
+1111
-11100001
----------
100000000
А ты думал, единицу на 1 умножить в 4-х разрядной архитектуре так просто, да?! А вот ошибаешься... Сверху — два множителя, с плюсиками — их дополнительные коды, с минусом — "произведение" допкодов. Внизу — баланс. "Произведение" упомянуто в кавычках потому, что на самом деле ничего умножать не надо — мы же не умножаем 1000 х 1000: просто нолики складываем. Для единичных разрядов — такая же история:
mov al, 1
sub al, 32 ; в AL "произведение" 15 * 15 для 4-х разрядной архитектуры
Я просто запилил алгоритмы 
