Поиск квадратного корня с использованием целых чисел

Question

Недавно я столкнулся с проблемой в чьем-то классе программирования. Он попросил их вычислить квадратный корень, используя только целые числа; они должны были использовать одно целое число для представления части перед десятичной точкой и другое целое число для представления части после десятичной точки. Проблема заключалась в том, что использование чисел с плавающей запятой не допускалось.

Однако, подумав об этом в течение некоторого времени, я не могу придумать способ сделать это без использования плавающей запятой. У меня Googled высокий и низкий, и я не могу найти ответ.

Я в шутку предположил, что мой друг реализует FPU для этого, но он не был так удивлен.

Есть ли у кого-нибудь идеи о том, как это решить?

Answer 1

Скажем, ваш первоначальный номер x.

1. Нахождение части до десятичной точки легко - просто найдите максимальное число, квадрат которого меньше или равен исходному номеру.

2. Умножьте исходный номер на 100 и целочисленную часть sqrt на 10. Добавьте 1 к ней, пока она не станет равной или равна 100x. Сделайте это n раз и делите на 10^n в конце, чтобы получить окончательный ответ усеченным до n десятичных знаков.

Answer 2

Предположим, у вас есть алгоритм, который создает два целых числа A и B, так что отношение A/B дает нужную приближение к квадратному корню до соответствующего числа десятичных знаков. Затем два нужных номера будут следующими:

• Целая часть (A - (A % B))/B.
• Дробная часть: Да X be A % B. Затем рацион X/B представляет дробную часть. Затем вычисленная дробная часть выполняется путем построения последовательных цифр путем вычисления (10*X - (10*X % B))/B и установки снова и снова, пока вы не получите нужное количество десятичных знаков.

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

Answer 3

В псевдокоде это будет что-то вроде этого:

int whole_ans = sqrt(num); //stores final answer integer part 
int dec_ans; //stores final answer decimal part 

int num_of_decimals = x //x is equal to the number of decimal places you want the answer to be 
int targetNum = (num - (whole_ans^2)) * 100; //initialize target to residual * 100 
int currAns = whole_ans; //initialize target to residual of num - the answer so far 

for(int i=0;i<x;i++) 
{ 
    x = get_next_digit(targetNum,currAns)); 
    dec_ans = append(dec_ans, x); //append the new found digit to the right of the current decimal answer 
    targetNum = (targetNum - (currAns * 20 + x) * x) * 100; //update target number to be residual + 2 zero digits 
    currAns = append(currAns,dec_ans) //append the decimal part of the answer to the current total answer so far 

} 

func get_next_digit(targetNum,currAns) 
{ 
int attempt=0; 
int i=0; 
    while(attempt <= targetNum) 
    { 
     i++; 
     attempt = (20 * currAns + i) * i; 
    } 
i--; 
return i; 
} 

Этот ответ следует шаги на вычисление квадратного корня вручную: http://www.wikihow.com/Calculate-a-Square-Root-by-Hand

Answer 4

Предположим, вы хотите, чтобы вычислить квадратный корень из 123.4567 ,

Тогда все, что вам нужно сделать, это сдвинуть десятичную точку достаточно далеко вправо, чтобы получить целое подкоренное - в этом примере, четыре места - и так, верно следующее:

sqrt(123.4567) = (1/100) * sqrt(1234567)

То есть все, что вам нужно знать, это найти квадратный корень из целого числа.Для этого рассмотрим следующий код (в C):

unsigned int int_sqrt (unsigned int n) { 

    unsigned int result = 0; 
    unsigned int count = 1; 

    for (; count*count <= n; count += 1) { 

     result = result + 1; 

    } 

    return result; 

} 

Если вы хотите избавиться от умножения, вы можете также сделать это:

unsigned int int_sqrt (unsigned int n) { 

    unsigned int result = 0; 
    unsigned int odd = 1; 
    unsigned int oddsum = 1; 

    while (oddsum <= n) { 

     result = result + 1; 
     odd = odd + 2; 
     oddsum = oddsum + odd; 

    } 

    return result; 

} 

Это явно не самые быстрые способы сделайте это, но они используют только целые числа, и они не полагаются на характеристики конкретных процессоров, таких как длина слова.

Answer 5

Я считаю, что измененная форма двоичного двоичного поиска - это то, что поможет вам в этом. Позвольте мне уточнить, что в псевдокоде.

int square_number = findSquareRootFloor (GivenValue);

findSquareRootFloor(int number) 
{ 
    int low = 0; 
    int high = number; 
    while (low <=high) 
    { 
     int mid = number /2; // note use integer division 
     target = searchedValue * searchedValue`enter code here`; 
     if (target > number) 
      high = mid-1; 
     else if (target < number) 
      low = mid +1; 
     else 
     { // exact match 
      return mid; 
     } 
    } 

    // if we have come here mid stores the floor of the square root 
}