Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 18.02.2010, 16:25
Новичок

Отправить личное сообщение для Алексей1981 Посмотреть профиль Найти все сообщения от Алексей1981
 
Регистрация: 18.02.2010
Сообщений: 3

Самый быстрый алгоритм вычисления корня из суммы квадратов
Помогите с реализацией алгоритма нахождения квадратного корня из суммы квадратов? Т.е. нужно найти гипотенузу... Сначала решал в лоб, находил квадраты, потом суммировал и находил квадратный корень.. Но в этом случае получается очень долго. В том числе нашел достаточно быстрый алгоритм вычисления квадратного корня... Но как оказалось есть еще более быстрый, нашел только упоминания о нем и пару исходников, но въехать не смог... Единственное что понял используется загадочная константа 0x5f375a86...
Собственно задача:
В худшем случае разобраться с извлечением квадратного корня с загадочной константой 0x5f375a86.
В лучшем случае найти еще более быстрый алгоритм нахождения корня из суммы квадратов.
Для обеспечения максимального быстродействия необходимо: Т.к. умножения и деления занимают много времени, необходимо их минимум, причем желательно без делений, кроме как на степень двойки, т.к. на любое другое число деление выполняется еще медленнее умножения...
  #2  
Старый 20.02.2010, 15:25
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

http://en.wikipedia.org/wiki/Fast_inverse_square_root
Алгоритм был придуман Silicon Graphics, его боевое крещение произошло в Q3. А константа была подобрана перебором.
P.S. В русской википедии тоже есть эта статья, но она вельми короче.

Последний раз редактировалось lordKelvin, 20.02.2010 в 16:35.
  #3  
Старый 20.02.2010, 16:43
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Хм, вы не уточнили в какой задаче хотите применять. Вычисления предполагаются с целыми числами или нет?
  #4  
Старый 21.02.2010, 12:42
Новичок

Отправить личное сообщение для Алексей1981 Посмотреть профиль Найти все сообщения от Алексей1981
 
Регистрация: 18.02.2010
Сообщений: 3

Именно на эту статью и натыкался в википедии... Но как водится так ничего не понял ... Пытаюсь разобраться. Можете слегка помочь объяснением? Нужно для БПФ. Все вычисления округляю до целых и масштабирую конечный результат. В результате получается точность +-1 от точных значений, что считаю вполне приемлемым пока. В конце БПФ получаются целые двухбайтные числа для вещественной и мнимой части вектора (каждая часть двухбайтная целая). после вычисления корня из суммы квадратов достаточно уже одного байта будет, поэтому результат отмасштабирую... Дело еще в том, что мало что понимаю в языках высокого уровня, работаю в чистом ассемблере, конечное устройство реализовано на контроллере. Правда не DSP, до которых я пока еще добираюсь и только только начинаю потихоньку осваивать. Данная программа предназначена в основном для изучения алгоритма БПФ, когда освою DSP написанный мной алгоритм будет перенесен на DSP. Ну и чтобы все было не зря, для вывода спектра звукового сигнала на графических индикатор. Задумано ради спортивного интереса выяснить способен ли на это выбранный контроллер... Оказалось способен. В нем есть модуль аппаратного умножения 8х8 и их я знаю довольно хорошо, что и стало критерием выбора именно его... Плюс еще и возможность работать на тактовой частоте 40 Мгц.
Я так понимаю, что это магическое число является шестнадцатиричной записью числа с плавающей запятой в формате IEEE 754? Также дан исходник с вычислением Но вот никак не могу догнать, это просто вычисляется корень из числа, или все же вычисляется сразу корень из суммы квадратов, да и в начале статьи и в конце даны формулы, никак не согласующиеся с исходником, Да и что за переменные f, tmp, tmp.x, tmp.i, xhalf...

Последний раз редактировалось Алексей1981, 21.02.2010 в 12:56.
  #5  
Старый 22.02.2010, 02:30
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Реализована ли в контроллере поддержка плавающих чисел?
tmp.x - число типа float, а tmp.i - тот же dword, но к нему уже мы обращаемся, как к int, что позволяет работать с битовым представлением числа с плавающей точкой. При сдвиге его вправо на 1 бит, мы делим мантиссу на два, если показатель степени нечетный прибавляем 0.5, показатель степени тоже делится на два, если число отрицательно, то знак меняется, а старший бит степени сстановится 1. Для чисел больше нуля это преобразование ведет себя, на удивление плавно. Советую посмотреть про формат хранения float и построить этот график.
Эта функция приближенно считает квадратный корень своего параметра.
0x5f375a86 не число float, а константа подобранная перебором так, что результат функции в среднем наиболее близок к истинному значению.
  #6  
Старый 22.02.2010, 16:48
Новичок

Отправить личное сообщение для Алексей1981 Посмотреть профиль Найти все сообщения от Алексей1981
 
Регистрация: 18.02.2010
Сообщений: 3

К сожалению нет аппаратной поддержки флоат, но программно конечно можно перейти на этот тип, но это тоже дополнительная потеря времени... Хотя думаю и значительно меньше, чем вычислять корень по другим алгоритмам...
Насчет tmp как я понял из вашего сообщения, это тупо переход на битовой представление, то есть если я работаю в ассемблере, все регистры выделенные под число с плавающей запятой и есть то самое обращение к tmp.i. то есть надо тупо брать все эти регистры и сразу сдвигать? Ладно, со сдвигами в асме полный порядок...
Формат флоат знаю, я так понимаю используется IEEE 754? просто я знаю еще один микрочиповский, он более оптимизирован для 8 разрядных контроллеров... Они отличаются только расположением бита знака мантиссы.
Алгоритм выглядит так:
Маниссу пополам...
Если показатель степени нечетный, то к мантиссе +0,5...
Показатель тоже пополам
Если отрицательный показатель степени был, то знаковый бит снова в 1...
Я правильно понял?
Но пока все равное не допонимаю исходник... Хотя кое что и прояснилось.
float InvSqrt(float x) ; Здесь объявляем функцию...
{
float xhalf = 0.5f * x; Здесь я так понимаю присваиваем какой то локальной константе значение 0.5f * x. С х понятно, это число из которого извлекаем корень. а вот 0.5f это что? арифметичских знаков нет, хотя по смыслу напоминает деление мантисы числа х пополам... Я прав?
union {
float x; Тут вроде понятно, тип переменных...
int i;
} tmp;
tmp.x = x; Здесь временному регистру присваиваем значение х и в последующем работаем с ним, как с регистрами асма...
tmp.i = 0x5f3759df - (tmp.i >> 1); Здесь из константы вычитаем деленный пополам tmp.i. По логике вроде здесь должно находится число х с мантиссой и порядком... Не совсем понимаю еще.
x = tmp.x; здесь обратно переходим к плавающей запятой...
return x * (1.5f - xhalf * x * x); А вот это совсем не понятно что к чему... Ладно с арифметикой понятно, но что такое 1.5f - xhalf я до сих пор не понял.
}

Получается что с константой работаем как с целым беззнаковым числом?
А есть возможность адаптировать этот алгоритм к целым безнаковым двухбайтным числам?
Все, все пошел пытаться строить график )...
  #7  
Старый 23.02.2010, 02:54
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

float xhalf - объявить переменную (в памяти, а если быть еще точнее, то для x86 в стеке)
0.5f - это ноль целых точка пять десятых типа float.
tmp.x и tmp.i - одна и та же область памяти, но в первом с.лучае представляется программисту числом с плавающей точкой, а в другом интеджером.
У меня есть стойкое подозрение, что эмулировать на восьмибитном процессоре число с плавающей точкой ускорения в вычислении корня не даст.
Есть другая идея, но сегодня уже не успеваю додумать / проверить. В той статье говорилось, что для вычисления корня достаточно удачно угадать начальное значения для метода Ньютона - тогда даже одной итерации будет достаточно. Так вот, в битово представлении "длина" числа (количество бит числа минус старшие нулевые биты 00100110 - всего восемь, но старшие 2 нулевые, длина - 6) пропорциональна половине "длинны" его корня, в половине случаев на пол бита меньше. Думаю, отсюда можно выудить весьма точное предсказание.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Агоритм выделение суммы полных квадратов Jim Математические алгоритмы 4 19.10.2009 00:09
Корень из суммы квадратов Michael_K Математические алгоритмы (другое) 19 15.04.2008 01:07
Самый быстрый алгоритм сканнера портов LMZ Оффтопик 0 04.01.2008 19:42
Самый быстрый способ закрасить треугольник Riasoft Обработка изображений, звук, графика 1 01.08.2007 02:40
вычисления квадратного корня из числа(целого) win_perec Математические алгоритмы 6 05.01.2007 12:32