Квадратный корень двоичного числа и число в степени 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-]

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

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 системе?

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

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