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

Кстати, на будущее.
Процедура убирания двоек из числа (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;

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

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