W>>Это же дико (и медленно) умножать два числа через полубайты, если у тебя регистр 64 или 32 бита. Ещё более дико становится если вспомнить, что много где есть возможность умножить пару машинных слов и получить результат двойной длины.
M>Полубайты? M>Ты это уже к алгоритму умножения чисел произвольной длины ? M>Где есть возможность умножения с расширением результата? На x86 вроде нет даже сейчас (64-128). Не знаю, есть ли на x64 умножение mul64 со 128-битным результатом. Вроде тоже нет.
Вообще-то инструкция умножающая пару чисел и с результатом двойной длины была уже в самом первом 8086 процессоре. Соответственно, та же самая инструкция в x86-64 умножает пару 64-битных чисел с 128-битным результатом. То есть на 16-битном 8086 результатом будет 32-битное число, на 32-битном i386 результатом будет 64-битное число, и на современных x86-64 результатом умножения является 128-битное число.
Как раз наоборот, возможность перемножить пару чисел и получить результат такой же длины (то есть с отбрасыванием в случае переполнения) появилось в семействе x86 намного позже. А изначально все процессоры умножали с расширением (ну и продолжают это делать сейчас).
M>Алгоритм умножения, который я стырил у Уоррена, как раз на это и расчитан.
Ага. Поэтому если адаптировать его на x86, то нужно обрабатывать числа вдвое длиннее чем разрядность процессора — там как раз получается, что старшая/младшая половина помещается в регистр, а умножение пары регистров как раз с расширением и делается в процессоре.
W>>В этом коде, кстати говоря, ещё один довольно сомнительный подход используется. Зачем нужно проводить вычисления над 8-,16-,32-х битными числами если длина машинного слова 64 бита (судя по наличию UINT64). Вместо этого просто сразу расширяешь все короткие числа до машинного слова, обрабатывать их как обычно, а потом, если нужно, при упаковке обратно проверять все переполнения.
M>Для ассортимента ;) M>Иногда пишу на TurboC 1.0 для 186 ;) При нужде переделать под C можно без проблем, если все уже работает. M>И на x86 маш. слово все-таки 32 разряда, возможно есть mul32, который дает 64х-битный результат, но не уверен, пусть с этим компилятор разбирается ;) M>Вопрос в том, как умножать числа, которые дают результат шире маш. слова. И для которых нет (или есть, но сильно нестандартные) интегральные типы с большей разрядностью.
Ну я не много не про это. Ладно, пусть на процессоре нет операции умножения 32x32 -> 64, а есть только 32x32 -> 32 (с отбрасыванием старшей части) — не суть. И из-за этого ты используешь алгоритм Уоррена для 32-битных чисел. Но зачем ты его же используешь для 8-битных? Тут-то точно уже известно, что произведение двух 8-битных чисел влезет в 32 бита.
Ну то есть я понимаю, что он у тебя возник из-за того, что в шаблонах легко поменять параметр и получить реализацию для более коротких чисел. Но вот это-то как раз и плохо: вместо того чтобы умножать напрямую, у тебя используется менее эффективный алгоритм, созданный для совсем другой ситуации.
M>Я то что нужно было, сделал с большим внимание, а часть про запас накопипастил ;)
А тесты-то написал? Мне вот кажется, что код не должен работать. Например, вот эта строка 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> у тебя в коде используется и непонятно как ты эту ошибку в тестах не поймал.
