Квадратный корень двоичного числа и число в степени 2 Опции

[DarkWishmaster]

Привет.
Вообщем такая задача:
Дано число X в двоичной системе из N цифр (0,1) , найти число Y=sqrt(x);
для первой задачи:
1<=N<=250 так что тут варинаты типа перевести в 10 и обратно не принимаются.
Вот я решил для противоположной задачи:
Y=x^2 где 1<=N<=120. Только достаточно медлено идет ( из за процедуры Optimze), решил число в векторе поставить и уже умножить два вектора:

Спойлер (Показать/Скрыть)

  Uses Crt;
type number=array[1..255] of integer;
var  i,n:integer; a,s:number; x:string;
procedure Optimize;
var k,j:byte;
  begin
      for k:=1 to 2*N do     
      for j:=1 to 2*N do   //тут время порядка N^2 поэтому проигрываю во времени, зато точнее      
         if s[j]=2 then                                                                        результат выдает
           begin
            s[j]:=0;
            s[j-1]:=s[j-1]+1;
    end;
 end;
procedure Multiply(var a:number);
 var i,j:byte;
 begin
   for j:=1 to N do
   for i:=1 to N do
    begin
      s[i+j-1]:=s[i+j-1]+a[i]*a[j];  //умножаем 
    Optimize; //оптимизируем что бы небыло чисел 2 
   end;
end;
Begin ClrScr;
readln(x);
n:=length(X);
for i:=1 to N do
a[i]:=ord(x[i])-48;
Multiply(a);
for i:=0 to 2*N-1 do
write(s[i]);
readln;
end.  

Квадратный корень думаю можно получить путем перебора всех двоичных чисел из (N div 2)+1 бинарных цифр потом вывести в степень и сравнивать, но если исп. мою програму для степени то время выполнения значительно превысит разрешимое.

Сообщение отредактировано: DarkWishmaster - 27.05.2011 20:58

[-TarasBer-]

Вот есть известнй алгоритм. Умножений нету. Только вычитания, ну и побитовые операции.
Переписать его нетрудно. Понять намного сложнее. Я вот смог весьма смутно.

Сишный синтаксис знаешь? Если что не ясно - переспроси.

int isqrt4(unsigned x) { 
   // unsigned - это аналог cardinal, но это неважно
   unsigned m, y, b;// объявляем внутренние переменные

   m = 0x40000000; // тут любая чётная степень двойки, но заведомо превосходящая икс
   y = 0;
   while(m != 0) {              // Do 16 times.
      b = y | m;     // битовое or
      y = y >> 1;   // битовый сдвиг вправо
      if (x >= b) {  x = x - b; y = y | m; }
      m = m >> 2; 
   }
   return y;
}

[DarkWishmaster]

Вот есть известнй алгоритм. Умножений нету. Только вычитания, ну и побитовые операции.
Переписать его нетрудно. Понять намного сложнее. Я вот смог весьма смутно.

Сишный синтаксис знаешь? Если что не ясно - переспроси.

int isqrt4(unsigned x) { 
   // unsigned - это аналог cardinal, но это неважно
   unsigned m, y, b;// объявляем внутренние переменные

   m = 0x40000000; // тут любая чётная степень двойки, но заведомо превосходящая икс
   y = 0;
   while(m != 0) {              // Do 16 times.
      b = y | m;     // битовое or
      y = y >> 1;   // битовый сдвиг вправо
      if (x >= b) {  x = x - b; y = y | m; }
      m = m >> 2; 
   }
   return y;
}

Си пока не знаю, если не трудно перепеши пожалуйста для Паскаля, постараюсь понять. Я пока пойду почитаю про битовые сдвиги.
Как я понимаю этот алгоритм предназначен для чисел в 10 системе? потому что число длиной в 250 цифр не впишется в стандартные типа, только если симулировать операции сдвига на векторе.

Сообщение отредактировано: DarkWishmaster - 27.05.2011 23:25

[-TarasBer-]

Дословно переписываю (только заменил знаковый на беззнаковый).

function isqrt4(x: longint): longint;
var  m,y,b: longint;
begin
  m := $40000000;
  y := 0;
  while m <> 0 do begin
    b := y or m;
    y := y shr 1;
    if x >= b then begin x := x - b; y := y or m; end;
    m := m shr 2;
  end;
  isqrt4 := y;
end;

> Как я понимаю этот алгоритм предназначен для чисел в 10 системе?

Судя по обилию битовых операций, нетрудно догадаться, что этот алгоритм подогнан именно под представление в двоичной системе.

[DarkWishmaster]

Дословно переписываю (только заменил знаковый на беззнаковый).

function isqrt4(x: longint): longint;
var  m,y,b: longint;
begin
  m := $40000000;
  y := 0;
  while m <> 0 do begin
    b := y or m;
    y := y shr 1;
    if x >= b then begin x := x - b; y := y or m; end;
    m := m shr 2;
  end;
  isqrt4 := y;
end;

> Как я понимаю этот алгоритм предназначен для чисел в 10 системе?

Судя по обилию битовых операций, нетрудно догадаться, что этот алгоритм подогнан именно под представление в двоичной системе.

Спасибо. Пойду разбираться, надеюсь пойму хоть каплю в этих операциях.

[-TarasBer-]

Кстати, на будущее.
Процедура убирания двоек из числа (Optimize) пишется не так.

p := 0; // перенос
for k := 255 downto 1 do begin  // идём от младших разрядов к старшим
  a[k] := a[k] + p; // учитываем перенос, оставшийся с предыдущих разрядов
  p := a[k] div 2;   // если число получилось больше 1, то запоминаем новый перенос
  a[k] := a[k] mod 2; // остаток сохраняем
end;

И в процедуре умножения не надо делать убирание двоек после КАЖДОЙ итерации.

[DarkWishmaster]

Кстати, на будущее.
Процедура убирания двоек из числа (Optimize) пишется не так.

p := 0; // перенос
for k := 255 downto 1 do begin  // идём от младших разрядов к старшим
  a[k] := a[k] + p; // учитываем перенос, оставшийся с предыдущих разрядов
  p := a[k] div 2;   // если число получилось больше 1, то запоминаем новый перенос
  a[k] := a[k] mod 2; // остаток сохраняем
end;

И в процедуре умножения не надо делать убирание двоек после КАЖДОЙ итерации.

О! Спасибо огромное!