Привет.
Вообщем такая задача:
Дано число X в двоичной системе из N цифр (0,1) , найти число Y=sqrt(x);
для первой задачи:
1<=N<=250 так что тут варинаты типа перевести в 10 и обратно не принимаются.
Вот я решил для противоположной задачи:
Y=x^2 где 1<=N<=120. Только достаточно медлено идет ( из за процедуры Optimze), решил число в векторе поставить и уже умножить два вектора:
Вот есть известнй алгоритм. Умножений нету. Только вычитания, ну и побитовые операции.
Переписать его нетрудно. Понять намного сложнее. Я вот смог весьма смутно.
Сишный синтаксис знаешь? Если что не ясно - переспроси.
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;
}
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;
}
Дословно переписываю (только заменил знаковый на беззнаковый).
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;
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;
Кстати, на будущее.
Процедура убирания двоек из числа (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;
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;