Рассмотрим простые примеры алгоритмов, использующих обратный элемент.
Как утверждают математики, знакомые с теорией групп, для любого нечетного целого в арифметике по модулю 2^N существует обратный по умножению элемент. Его довольно просто найти последовательными умножениями. Иногда это позволяет решать интересные задачи.
Задача 1
В массиве неотрицательных целых чисел заменить каждый элемент на произведение остальных элементов.
С одной стороны, можно воспользоваться вспомогательным массивом, в котором вычислить последовательные произведения элементов. Но это как-то неспортивно.
С другой стороны, можно сначала вычислить произведение всех элементов массива, а затем - частные от деления этого произведения на каждый элемент массива. Конечно, при умножении может произойти переполнение, чего можно избежать использованием более широкого типа, а это тоже не совсем спортивно.
Наконец, вместо деления можно использовать умножение на обратный элемент. При этом потеря старших битов произведения из-за переполнения не имеет значения, результат все равно будет верным. Остается только одна проблема - четные числа не имеют обратного элемента. Поэтому нам придется заменять их нечетными, сдвигая вправо до тех пор пока в младшем бите не окажется единица, а величину сдвига суммировать в экспоненте произведения:
type TMyArray= array of cardinal; procedure Multiply(var x, e: cardinal; y: cardinal); var m, d: cardinal; begin; m:=1; d:=0; while y and m=0 do begin; m:=m+m; d:=d+1; end; x:=x*(y shr d); e:=e+d; end; function Divide(x, e, y: cardinal): cardinal; var m, d: cardinal; begin; m:=1; d:=0; while y and m=0 do begin; m:=m+m; d:=d+1; end; y:=y shr d; e:=e-d; if e<8*SizeOf(x) then begin; while y<>1 do begin; x:=x*y; y:=y*y; end; Result:=x shl e; end else Result:=0; end; procedure Calculate(a: TMyArray); var x, e: cardinal; i, j, len: integer; begin; len:=Length(a); x:=1; e:=0; j:=-1; for i:=0 to len-1 do begin; if a[i]=0 then begin; if j>=0 then begin; j:=len; break; end; j:=i; end else Multiply(x, e, a[i]); end; if j>=0 then begin; for i:=0 to len-1 do a[i]:=0; if j<len then a[j]:=Divide(x, e, 1); end else for i:=0 to len-1 do a[i]:=Divide(x, e, a[i]); end; procedure TForm1.Button1Click(Sender: TObject); var a: TMyArray; begin; SetLength(a, 4); a[0]:=1; a[1]:=7; a[2]:=3; a[3]:=4; Memo1.Lines.Add(Format('%d %d %d %d', [a[1]*a[2]*a[3], a[0]*a[2]*a[3], a[0]*a[1]*a[3], a[0]*a[1]*a[2]])); Calculate(a); Memo1.Lines.Add(Format('%d %d %d %d', [a[0], a[1], a[2], a[3]])); end;
Задача 2
Длинные числа A и B заданы своими короткими множителями a[i], i=1..N и b[j], j=1..M.
Множители никак не упорядочены и не обязательно просты. Известно, что B=A*х, где x - короткое.
Найти x, без использования деления и длинных чисел.
Конечно, можно разложить каждый множитель на простые, отсортировать, привести разложения чисел A и B к канонической форме, вычесть множества и перемножить оставшиеся элементы, но как-то это муторно.
А можно, используя то же представление данных, что и в предыдущей задаче, написать свою версию функции MulDiv, в которой в качестве аргументов выступают массивы:
function MyArrayMulDiv(a, b: TMyArray): cardinal; var x, e, y, d: cardinal; i: integer; begin; Result:=0; y:=1; d:=0; for i:=0 to Length(b)-1 do if b[i]<>0 then Multiply(y, d, b[i]) else exit; x:=1; e:=0; for i:=0 to Length(a)-1 do if a[i]<>0 then Multiply(x, e, a[i]) else exit; e:=e-d; if e<8*SizeOf(x) then begin; while y<>1 do begin; x:=x*y; y:=y*y; end; Result:=x shl e; end else Result:=0; end; procedure TForm1.Button2Click(Sender: TObject); var a, b: TMyArray; begin; SetLength(a, 5); a[0]:=MaxInt; a[1]:=155555; a[2]:=3; a[3]:=20; a[4]:=6; b:=copy(a,0,3); Memo1.Lines.Add(Format('%d', [a[3]*a[4]])); Memo1.Lines.Add(Format('%d', [MyArrayMulDiv(a,b)])); end;
Позже я обязательно вернусь к этой теме, есть еще кое-что интересное, о чем обязательно надо написать.