Мне тут один товарищ сказал, что встречал функцию, которая считает целочисленный корень (т.е. результат без дробной части) от целого числа, причем не содержит циклов, состоит всего из нескольких строчек (что в его понимании "несколько", я не уточнял), и содержит операцию xor (т.e. ^).
Я знаю, что есть очень простые алгоритмы для сей задачи, но во всех них есть цикл.
Что вы можете сказать по этому поводу? (С кодом, пожалйста! С кодом! =) )

Здравствуйте, ЫфВ, Вы писали:

ЫфВ>Мне тут один товарищ сказал, что встречал функцию, которая считает целочисленный корень (т.е. результат без дробной части) от целого числа, причем не содержит циклов, состоит всего из нескольких строчек (что в его понимании "несколько", я не уточнял), и содержит операцию xor (т.e. ^).
ЫфВ>Я знаю, что есть очень простые алгоритмы для сей задачи, но во всех них есть цикл.
ЫфВ>Что вы можете сказать по этому поводу? (С кодом, пожалйста! С кодом! =) )

Наверное имелось ввиду вот это: http://www.math.purdue.edu/~clomont/Math/Papers/2003/InvSqrt.pdf Без ксора, но и без циклов.

Здравствуйте, ЫфВ, Вы писали:

ЫфВ>Мне тут один товарищ сказал, что встречал функцию, которая считает целочисленный корень (т.е. результат без дробной части) от целого числа, причем не содержит циклов, состоит всего из нескольких строчек (что в его понимании "несколько", я не уточнял), и содержит операцию xor (т.e. ^).

Xor не содержит, но содержит BSR (определение номера старшего бита)
http://antigrain.com/__code/include/agg_math.h.html#fast_sqrt
Таблицы:
http://antigrain.com/__code/src/agg_sqrt_tables.cpp.html

Забавные решения. Спасибо. А может быть, еще оптимальнее есть? (А то, один метод использует "много" =) памяти под таблицы, а второй содержит четыре умножения с числом с плавающей точкой (хоть это и не деление =) ) )

Здравствуйте, Аноним, Вы писали:

А>Забавные решения. Спасибо. А может быть, еще оптимальнее есть? (А то, один метод использует "много" =) памяти под таблицы, а второй содержит четыре умножения с числом с плавающей точкой (хоть это и не деление =) ) )

Не знаю, автор данного решения теряется в глубинах FIDO Net. Я то же был бы не против поискать что-то более оптимальное. А особенно был бы не против найти решение для int64. Так что если что-то попадется, сообщи.

Здравствуйте, Аноним, Вы писали:

А>Забавные решения. Спасибо.

Забыл добавить, что этот метод дает некоторую погрешность. Она, например, проявляется как легкий муар в некоторых частях радиального градиента:
http://antigrain.com/stuff/radial_gradient_moire.png