Как написать собственную функцию извлечения кв. корня из целого числа?

Question

[nikitosssguy]

Попробовал написать аналог функции sqrt(), но для целых чисел. Что можно сделать лучше, быстрее? Я просто начинающий, не хотелось бы "говнокодить" с самого начала изучения языка. Знаю, что register средой visual c++ не воспринимается, но судя по литературе, в других компайлерах скорость работы ускорить должно. Заранее спасибо за ответы.

int my_sqr(int number){
	register unsigned int temp = 0, x = 1;
	if (number < 0) number = -number;
	while (temp != x){
	temp = number / x;
	if (temp == x) return x;
	x++;
	}
};

Answer 1

[jcmvbkbc]

Что можно сделать лучше, быстрее?

Поменять алгоритм на метод деления пополам или побитовый поиск, с уменьшением сложности по количеству бит в int с экспоненциальной до линейной.

Например так:

int my_sqr(int number){
	register unsigned int temp, x;
	if (number < 0)
		number = -number;
	for (temp = 0, x = 1u << (sizeof(unsigned int) * 4 - 1); x; x >>= 1) {
		if ((temp | x) * (temp | x) <= number)
			temp |= x;
	}
	return temp;
}

Не проверять на равенство if (temp == x), потому что равенства может не быть, например для number = 6.
Убедиться, что функция всегда что-то возвращает. Так, например, при number = 6 ваша функция зацикливается или падает с делением на 0, а при number = 0 завершается с неопределённым значением.

Comments

[nikitosssguy]

Такой вариант будет намного быстрее в случае с большими числами?

[jcmvbkbc]

Такой вариант гарантированно находит корень за 16 итераций для любого 32-битного инта.

[nikitosssguy]

@jcmvbkbc, спасибо, надо будет разобраться.

[nikitosssguy]

Не могли бы вы немного разжевать вашу функцию? Никак не могу вникнуть в происходящее.

[jcmvbkbc]

@nikitosssguy мы поразрядно подбираем максимальное число, квадрат которого не превосходит заданного. Начинаем с максимального разряда, квадрат которого всё ещё укладывается в unsigned int, и на каждой итерации проверяем, сохраняется ли неравенство temp ^ 2 <= number при прибавлении очередного двоичного разряда к temp.

[nikitosssguy]

@jcmvbkbc, что-ж, спасибо. Когда изучал битовые операции никак не мог въехать, буду копать, раз уж это настолько полезная особенность c++

Answer 2

[svd71]

ну наверное вспомнить математику и включить голову. логарифм от числа, деленный на логарифм основания дает нам степень:

a^b=c
b=ln(c)/ln(a)
a=exp(b * ln(c))

для квадратного корня b = 1/2

Comments

[jcmvbkbc]

@svd71 а как, вы говорите, это делается в целых числах?

[svd71]

просто подставляем в формулу значения:

exp(0.5 * ln(16))=exp(ln(16)/2)=4

это аналогично квадратному корню из 16и https://www.google.de/?gfe_rd=cr&ei=RF9qU87_GaLe8g...

[jcmvbkbc]

@svd71 вы, похоже, не поняли. Как используя только целочисленную математику вычислить части вашего выражения, такие как log и exp для произвольных значений?

[svd71]

нда. Этот момент я точно не понял.

Answer 3

[AxisPod]

А использовать более оптимальные алгоритмы? Для целого числа очень подойдет разложение в ряд.
1 = 1^2
1 + 3 = 2^2
1 + 3 + 5 = 3^2
1 + 3 + 5 + 7 = 4^2
Замечаете?

Просто вычитаете все нечетные числа начиная с 1. Если остаток меньше следующего нечетного числа, то берете порядковый номер предыдущего нечетного числа. Но это подойдет, если числа не очень большие, хотя ваш алгоритм не лучше в этом отношении.

Ну и как обычно на тостере, поискать видимо лень, поэтому вопросов интересных нет, а вот такая вот фигня.

2 минуты поиска: algolist.manual.ru/maths/count_fast/intsqrt.php

Answer 4

[dmitry2001]

Существует такой алгоритм как бинпоиск

int sqrt (int v){
int L = 0, R = v;
int M = (L + R) /2;
while(R - L > 1){
    if(M * M <= v){
        L = M;
    }
    else{
        R = M;
    }
    M = (L + R)/2;
}
}