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

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

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

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

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 цифр не впишется в стандартные типа, только если симулировать операции сдвига на векторе.

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

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

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

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

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

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

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