Здравствуйте, watchmaker, Вы писали:

W>Здравствуйте, Marty, Вы писали:

W>Вообще-то инструкция умножающая пару чисел и с результатом двойной длины была уже в самом первом 8086 процессоре. Соответственно, та же самая инструкция в x86-64 умножает пару 64-битных чисел с 128-битным результатом. То есть на 16-битном 8086 результатом будет 32-битное число, на 32-битном i386 результатом будет 64-битное число, и на современных x86-64 результатом умножения является 128-битное число.
Насчет 8086 уточнил — да, ты прав. Насчет 32 x86 — скорее всего тоже. Вот насчет 128х-разрядного результата не уверен, вроде совсем недавно где-то читал, что такого нет и только планируется.
А это собственно, и было нужно. Далее, если и есть — как это достать из C++? Писать на встроенном асме? Непереносимо. Писать две версии? Наверно, так. Или искать библиотеку, из которой можно быстренько дернуть кусочек кода? В пол-дня не уложился бы точно
В принципе, мне скорость тут абсолютно пофигу, я не криптографию ломать собрался Если приспичит, наверно подыщу замену.

M>>Алгоритм умножения, который я стырил у Уоррена, как раз на это и расчитан.
W>Ага. Поэтому если адаптировать его на x86, то нужно обрабатывать числа вдвое длиннее чем разрядность процессора — там как раз получается, что старшая/младшая половина помещается в регистр, а умножение пары регистров как раз с расширением и делается в процессоре.
Да, я подзабыл, что у x86 есть, виновен Но опять же, как переносимо написать?

W>>>В этом коде, кстати говоря, ещё один довольно сомнительный подход используется. Зачем нужно проводить вычисления над 8-,16-,32-х битными числами если длина машинного слова 64 бита (судя по наличию UINT64). Вместо этого просто сразу расширяешь все короткие числа до машинного слова, обрабатывать их как обычно, а потом, если нужно, при упаковке обратно проверять все переполнения.

W>Ну я не много не про это. Ладно, пусть на процессоре нет операции умножения 32x32 -> 64, а есть только 32x32 -> 32 (с отбрасыванием старшей части) — не суть. И из-за этого ты используешь алгоритм Уоррена для 32-битных чисел. Но зачем ты его же используешь для 8-битных? Тут-то точно уже известно, что произведение двух 8-битных чисел влезет в 32 бита.
Я на этой версии тестировал С большими числами тесты сложнее сочинять.

W>Ну то есть я понимаю, что он у тебя возник из-за того, что в шаблонах легко поменять параметр и получить реализацию для более коротких чисел. Но вот это-то как раз и плохо: вместо того чтобы умножать напрямую, у тебя используется менее эффективный алгоритм, созданный для совсем другой ситуации.
Можно и убрать специализации, или переделать поэффективнее.

W>А тесты-то написал? Мне вот кажется, что код не должен работать. Например, вот эта строка t = u[i]*v[j] + w[i+j] + k;. Тут у тебя t, k имеют двойную длину, а аргументы у произведения — одинарную. При этом в языках C/C++ есть такая особенность — Integral promotion называется. Если, скажем, это соответственно 32- и 16-битные числа, то ошибка не проявляется, так как перед вычислением произведения происходит расширение аргументов до длины машинного слова, т.е. на твоём комптьютере скорее всего до 32-битного числа. А вот если это 64- и 32-битные числа, то автоматического расширения может и не произойти — и часть битов результата будет отброшена. Собственно, multiply_num_mn_unsigned_impl<UINT32, UINT64> у тебя в коде используется и непонятно как ты эту ошибку в тестах не поймал.
Надо посмотреть. Действительно, на максимуме разрядности мало потестил. Спасибо, что обратил внимание. Думаю, будет достаточно явно преобразовать к более широкому типу перед умножением.