Целочисленное умножение и обратный элемент

Декабрь 16, 2015 — Шарахов А.П.

Рассмотрим простые примеры алгоритмов, использующих обратный элемент.

Как утверждают математики, знакомые с теорией групп, для любого нечетного целого в арифметике по модулю 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;

Позже я обязательно вернусь к этой теме, есть еще кое-что интересное, о чем обязательно надо написать.

на главную