Как вынести число n из под квадратного корня, не используя математические функции?

Question

[Gleb Zubov]

Добрый день!
Нам в институте на предмете (Алгоритмика и структура данных) дали заданее.
Составить алгоритм который будет считать число из под квадратного корня без использования Мат. функции.
Смотрел в интернете там всегда используют (sqrt).
За любую помощь спасибо

Comments

[Dimonchik]

если вам не рассказывали, что процессор умеет делать только два действия - сложение и смену знака - можешь рисануться ;) , главное, на слове "мантисса" не засыпаться только

[Alexander Burov]

dimonchik2013, а как же FPU -- тоже не умеет?

[Денис Загаевский]

dimonchik2013, чего?

[Dimonchik]

Alexander Burov, а чем он отличается? ну, захардкожены там команды высшего порядка, они от этого по меньшему числу транзисторов стали бегать?
удобство, только и всего, но в основе всех операций лежит сложение и смена знака, это к вопросу, зачем учить Оо нотацию в алгоритмах, есть есть фнукция sqrt, да и к float в finance тоже

[Alexander Burov]

Отличается тем, что это несамостоятельное устройство -- 4 регистра и логика. Начиная с 80486 вообще перестал быть отдельным устройством, но дело не в этом.

они от этого по меньшему числу транзисторов стали бегать?

Большему! За меньшее число тактов, в чём, собственно, и смысл FPU.

в основе всех операций лежит сложение и смена знака

О, сколько нам открытий чудных преподнесёт в наш век ЕГЭ... Кто не прогуливал дискретку, то знает, что сложение с инверсией не составляют полного класса булевых функций. Поэтому ими принципиально невозможно реализовать все операции.

Answer 1

[illuzor]

Самое банальное, что приходит в голову - последовательно в цикле перебирать числа от одного до n. Каждое число умножать само на себя, пока не получится заданное число.

Comments

[Gleb Zubov]

Да я тоже так думал, вот что вышло

public static void main(String[] args) {
     double x = 0.1;
     double n = 4;
     int b = 0;
     if (n==x+x)
     {
         System.out.print("Lala"+x);
     }
     else{
         while(n>x+x)
         {
         x = x+x;
         b++;
         }
     }
     System.out.print(b+" "+x);
    }

в - просто проверяю сколько раз был цикл
Но проблема в том что он не правильно считает, он выводет что х =3.2

Answer 2

[dom1n1k]

Я не знаю, куда вы смотрели в интернете, потому что это гуглится в одно касание.
Хотя бы википедия: https://en.wikipedia.org/wiki/Methods_of_computing...

Answer 3

[Alexander Burov]

А какие функции не считаются «математическими»? Деление можно или нельзя?
Найдём сначала все делители и запихнём в массив d.

целое i=0, k=2, l=n, массив целое d[n/2];
пока k<l/2 {
 если k*(l/k)==l { l=l/k; d[i]=k } иначе { k=k+1 }
 i=i+1
}
d[i]=l

Потом перебираем по очереди все элементы полученного массива, в котором будут делители n. Если текущий элемент равен следующему, то берём его как делитель выносимой части и следующий элемент в массиве пропускаем. Если нет, то берём его как делитель невыносимой из-под корня части, и следующий элемент не пропускаем. Если он вообще равен нулю, то значит, что массив закончился, и нужно вернуть результат -- вынесенное число и подкорневой остаток.

P.S. Конечно, можно сделать красиво -- всё в одном цикле, сразу вычисляя выносимое и подкорневой остаток. Приведённый неоптимальный алгоритм -- первое что в голову пришло. Дальнейшую оптимизацию, думаю, осилите сами.