Напишем выражение для произведения двух чисел в несколько изменённом виде, а именно:
[Z]пк = [X]пк*[Y]пк = = sign Z.(|X|*y1*2-1 + |X|*y2*2-2 +... + |X|*yn*2-n ) = = sign Z.( |X|*2-1*y1 + 2-1 (|X|*2-1*y2 + 2-1 (|X|*2-1*y3 + (...)))) = = sign Z. ((...(( |X|*yn*2-1 + |X|*yn-1 )2-1 + |X|*yn-2 )2-1 + ... + + |X|*y2 )2-1 + |X|*y1 )*2-1
Это выражение называется преобразованием по схеме Горнера и задаёт алгоритм умножения с младших разрядов множителя.
Таким образом, для умножения должна выполняться следующая последовательность действий:
Пример:
signZ= 1