| |
|
  |
 Очень нужна помощь в оптимизации алгоритма извлечения квадратного корня |
|
|
|
|
 Dec 11 2012, 06:07
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(анатолий @ Dec 9 2012, 00:23)  Вот функция корня по алгоритму CORDIC Код ....
b:=x+x/2**m;
.... Анатолий, спасибо огромное! Изучаю алогоритмик. Только вот я не понял, что означает в программе '**'? Степень числа?
|
|
|
|
|
|
|
Guest_TSerg_*
|
Dec 11 2012, 11:41
|
Guests
|
Код function intSqrt_(Val : Longword) : Longword;
var bitSqr : Longword;
begin
bitSqr := $40000000;
Result := 0;
While bitSqr <> 0 do
begin
if (Val >= bitSqr + Result) then begin
Dec(Val, bitSqr + Result);
Result := (Result shr 1) or bitSqr;
end
else
Result := Result shr 1;
bitSqr := bitSqr shr 2;
end;
end; Если сравнивать с уже упомянутой медленной функцией: Код function Q(x: Longword): Longword;
var k: Longword;
begin
Result := 0;
k := 1;
while (k <= x) do begin
Dec(x,k);
Inc(k,2);
Inc(Result);
end;
end; то разница на писюках более чем в 20 раз лучше.
|
|
|
|
|
|
|
|
Dec 11 2012, 19:16
|
Местный
Группа: Свой
Сообщений: 221
Регистрация: 10-12-05
Из: Украина
Пользователь №: 12 052
|
Цитата(Rostislav @ Dec 11 2012, 08:07) что означает в программе '**'? Степень числа? Это степень числа, язык VHDL. Cинтезируется в логическую схему.
|
|
|
|
|
|
|
|
Dec 20 2012, 13:41
|
Группа: Новичок
Сообщений: 2
Регистрация: 29-12-09
Пользователь №: 54 559
|
|
|
|
|
|
|
|
|
Dec 20 2012, 20:46
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(ASN @ Dec 20 2012, 17:38) С какой практической точностью нужно вычислять выражение ? Уважаемый ASN! Мне придумалась еще одна идея. Более простого алгоритма я придумать не смог (кстати, не понятно, почему этот вариант мне раньше не пришел в голову). Но все же отвечу на Ваши вопросы)) Меня интересует целочисленный результат. Цитата(ASN @ Dec 20 2012, 17:38) На какой целевой платформе выполняется прикладная программа?
Если вычислительная система поддерживает вычисления с плавающей точкой , то лучше воспользоваться арифметическим сопроцессором (типа сопроцессора для i386) или специальными командами самого процессора (как в TMS320C55). Меня интересовал вариант, который мог бы выполнятся на микроконтроллерах с простой архитектурой (типа PIC12). Цитата(ASN @ Dec 20 2012, 17:38) Если требуется целочисленная арифметика, то проще и быстрее заранее вычисленной таблицы в памяти что-то предложить сложно. Таблицы сразу не понравились. Для них нужна память. ---- Итак, мое заднее)))) предложение: Код a : Word; // подкоренное выражение
b : Word; // результат
n : Byte;
a := 121;
b := 0;
// начало
for n := 15 downto 0 do // Счет от 15 до 0 // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1)
begin
if ((b + 1 shl n) * (b + 1 shl n) < a) or // shl - побитовый сдвиг влево на n бит
((b + 1 shl n) * (b + 1 shl n) = a) then
begin
b := b + 1 shl n;
end;
end;
// конец
Form1.Caption := IntToStr (b); // b = 11
Циклов для 16-ти разрядного числа 16!!!
для 32-х разрядного числа 32!!!!!! По-моему, получилось красиво))) Операции умножения можно заменить на бинарное сложение столбиком с предварительным смещением бит влево. Если более оптимального алгоритма наука)) еще не придумала, то тему можно закрывать. Теперь возьмусь за вычисление тригонометрических функций)))) Всем спасибо!!!!!
Сообщение отредактировал Rostislav - Dec 20 2012, 21:57
|
|
|
|
|
|
|
|
Dec 21 2012, 02:07
|
Местный
Группа: Участник
Сообщений: 211
Регистрация: 27-12-11
Из: Челябинск
Пользователь №: 69 111
|
Цитата(Rostislav @ Dec 21 2012, 00:46) [code] a : Word; // подкоренное выражение b : Word; // результат n : Byte; a := 121; b := 0; // начало for n := 15 downto 0 do // Счет от 15 до 0 // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1) begin if ((b + 1 shl n) * (b + 1 shl n) < a) or // shl - побитовый сдвиг влево на n бит ((b + 1 shl n) * (b + 1 shl n) = a) then begin b := b + 1 shl n; end; end; // конец Form1.Caption := IntToStr (  ; // b = 11 [code] По-моему, получилось красиво))) Может, я чего-то не понимаю... но в цикле for явно не красота красуется. Вы 5 раз вычисляете одно и тоже выражение b + 1 shl n !! Дык, зачем это делать?. один раз вычислите, присвойте результат какой-нибудь временной переменной и таскайте ее за собой везде. что-то типа: for n := 15 downto 0 do // Счет от 15 до 0 // 15 - разрядность подкоренного выражения (вернее N не 15, а N=15+1) begin temp := b + 1 shl n; if (temp * temp < a) or // А ТАК НЕЛЬЗЯ???? (temp * temp <= a ) (temp * temp = a) then begin b := temp end; end; // конец
Сообщение отредактировал beaRTS - Dec 21 2012, 02:10
--------------------
"Об уме человека вернее судить по его вопросам, нежели по его ответам" (с)
|
|
|
|
|
|
|
|
Dec 21 2012, 05:56
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(beaRTS @ Dec 21 2012, 05:07) temp := b + 1 shl n;
if (temp * temp < a) or //А ТАК НЕЛЬЗЯ???? Да нее, Вы все правильно понимаете)))))))) Просто я не стал делать очевидное, то, что лежит на поверхности. Ну конечно же, мне известны некоторые трюки программирования. Умножение на 2 (и деление), например, легко можно заменить на побитовый сдвиг и т.п. А Ваш вариант оптимизации сделает, скорее всего, компилятор. Меня (и не только меня, наверное) больше всего интересовала суть. Суть я и изложил. Поэтому, спасибо Вам за участие и с наступающим Новым Годом!!!!!!!)))))))))
Сообщение отредактировал Rostislav - Dec 21 2012, 05:58
|
|
|
|
|
|
|
|
Dec 21 2012, 06:16
|
Местный
Группа: Участник
Сообщений: 211
Регистрация: 27-12-11
Из: Челябинск
Пользователь №: 69 111
|
Цитата(Rostislav @ Dec 21 2012, 08:56) Да нее, Вы все правильно понимаете)))))))) Просто я не стал делать очевидное, то, что лежит на поверхности. Ну конечно же, мне известны некоторые трюки программирования. Умножение на 2 (и деление), например, легко можно заменить на побитовый сдвиг и т.п. А Ваш вариант оптимизации сделает, скорее всего, компилятор. Меня (и не только меня, наверное) больше всего интересовала суть. Суть я и изложил. Поэтому, спасибо Вам за участие и с наступающим Новым Годом!!!!!!!))))))))) а, ну тогда добро, добро. я тут тоже начал над своим вариантом извлечения корня биться. Ну как своим - комбинирую два метода. посмотрим что получится
--------------------
"Об уме человека вернее судить по его вопросам, нежели по его ответам" (с)
|
|
|
|
|
|
|
|
Dec 21 2012, 06:19
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(beaRTS @ Dec 21 2012, 09:16) а, ну тогда добро, добро. я тут тоже начал над своим вариантом извлечения корня биться. Ну как своим - комбинирую два метода. посмотрим что получится Здорово!!!))) Выкладывайте Ваши идеи!!!!!! Очень интересно!!!)))
Сообщение отредактировал Rostislav - Dec 21 2012, 06:19
|
|
|
|
|
|
|
|
Dec 21 2012, 06:24
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(blackfin @ Dec 21 2012, 09:19) Сто раз уже обсуждали: ReAl. Да, похоже, я не открыл Америку))))))))
|
|
|
|
|
|
|
|
Dec 21 2012, 06:27
|
Местный
Группа: Участник
Сообщений: 211
Регистрация: 27-12-11
Из: Челябинск
Пользователь №: 69 111
|
Цитата(blackfin @ Dec 21 2012, 09:19) Сто раз уже обсуждали: повторение - мать учения.. к тому же поиск хренова-то работает на форуме. я эту ссылку первый раз вижу. Так что спасибо за "пароли, явки, адреса").
--------------------
"Об уме человека вернее судить по его вопросам, нежели по его ответам" (с)
|
|
|
|
|
|
|
|
Dec 21 2012, 06:31
|
Частый гость
Группа: Участник
Сообщений: 127
Регистрация: 6-07-08
Из: Москва
Пользователь №: 38 765
|
Цитата(beaRTS @ Dec 21 2012, 09:27) ...я эту ссылку первый раз вижу... Присоединяюсь! К тому же, может быть "подует свежий ветер"!)))
|
|
|
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|
