Квадратный корень из числа ... Точная до н точности

Question

Я не мог понять, вышеупомянутый метод. Может кто-нибудь объяснить? Я сделал некоторый код, но его ограничивает некоторая жестко закодированная точность и, похоже, потребляет слишком много ресурсов компьютера.

R = 0.00001 
INPUT N 
WHILE R*R != N 
     R = R + 0.00001 
ENDWHILE 
PRINT R 

Что такое алгоритм или код C++ для квадратного корня из числа до n точности? n может быть взято у пользователя, если требуется.

Answer 1

Существуют алгоритмы, которые намного лучше подходят для компьютерной оценки. Я изучил этот вопрос в 1960-х годах как способ ручного вычисления квадратного корня по цифре, используя процесс, а не длинное разделение.

Целью при вычислении n-й цифры результата является найти самую большую префиксную строку, чтобы квадрат был меньше или равен первым 2n знакам ввода.

Основная идея заключается в том, что (a+b)^2 = a^2 + b^2 + 2ab. В алгоритме a является частичным результатом до сих пор, а b - это новая цифра. Он учитывает коэффициенты 100 в квадрате и 10 в корне, перемещая два места на входе для одной сгенерированной цифры в результате.

Позвольте p быть частичным результатом до добавления цифры d. Мы уже вычитали из ввода p^2. Нам нужно также вычесть d^2 + 2pd, чтобы сохранить вычитание квадрата нового частичного результата. Эквивалентно вычесть d(2p+d). Мы продолжаем p, добавим d и умножим на d. Прежде чем перейти к следующему шагу, нам нужно удвоить d.

Answer 2

Вот кусок кода на C++, хотя он не является произвольной точностью, он может быть вам полезен. Это немного ближе к полному решению, то ваш базовый код:

#include <iostream> 
#include <vector> 
#include <cstdlib> 
#include <cstring> 
#include <climits> 

const unsigned g_unPlaces = 8; 

int main(int argc, char** argv) 
{ 
    if (argc != 2) 
    { 
    std::cerr << "USAGE: " << *argv << " NUMBER" << std::endl; 
    return 1; 
    } 

    std::vector<unsigned> vecInteger; 
    std::vector<unsigned> vecDecimal; 
    char *pDecimal = strchr(argv[1], '.'); 

    // Read integer part of NUMBER 
    if (pDecimal == NULL) pDecimal = argv[1] + strlen(argv[1]); 
    if ((pDecimal - argv[1]) % 2) vecInteger.push_back(0); 
    for (char *pCurrent = argv[1]; pCurrent < pDecimal; ++pCurrent) 
    { 
    int nValue = *pCurrent - '0'; 
    if (nValue >= 10 || nValue < 0) 
    { 
     std::cerr << "Error: Invalid character in input!" << std::endl; 
     return 1; 
    } 
    vecInteger.push_back((unsigned) nValue); 
    } 

    // Read decimal part of NUMBER 
    if (*pDecimal != '\0') 
    { 
    for (++pDecimal; *pDecimal != '\0'; ++pDecimal) 
    { 
     if (*pDecimal == '.') 
     { 
     std::cerr << "Error: Multiple decimals in input!" << std::endl; 
     return 1; 
     } 

     int nValue = *pDecimal - '0'; 
     if (nValue >= 10 || nValue < 0) 
     { 
     std::cerr << "Error: Invalid character in input!" << std::endl; 
     return 1; 
     } 
     vecDecimal.push_back((unsigned) nValue); 
    } 
    if (vecDecimal.size() % 2) vecDecimal.push_back(0); 
    } 

    const unsigned unInteger = vecInteger.size(); 
    const unsigned unDecimal = vecDecimal.size(); 

    std::vector<unsigned> vecValues; 

    unsigned x, y = 0, c = 0, p = 0; 
    for (unsigned i = 0; i < g_unPlaces; ++i) 
    { 
    if (2*i < unInteger-1) 
    { 
     c = (c*100 - y*100) + vecInteger[i*2]*10 + vecInteger[i*2+1]; 
    } 
    else if (2*i < unInteger+unDecimal-1) 
    { 
     c = (c*100 - y*100) + vecDecimal[i*2-unInteger]*10 
      + vecDecimal[i*2+1-unInteger]; 
    } 
    else 
    { 
     c = c*100 - y*100; 
    } 

    if (c == 0) break; 

    y = 0; 
    for (x = 1; x < 10; ++x) 
    { 
     unsigned temp = x*(20*p + x); 
     if (temp > c) { --x; break; } 
     y = temp; 
    } 

    p = 10*p + x; 
    vecValues.push_back(x); 
    } 

    // Write the result 
    for (unsigned i = 0; i < unInteger/2; ++i) 
    { 
    std::cout << vecValues[i]; 
    } 
    std::cout << '.'; 
    for (unsigned i = unInteger/2; i < vecValues.size(); ++i) 
    { 
    std::cout << vecValues[i]; 
    } 
    std::cout << std::endl; 

    return 0; 
} 

Как помочь в понимании вашего алгоритма, лучший подход должен начаться в попрошайничество и работать через каждый шаг. Попробуйте с небольшими значениями, такими как 4, 16 и 64. Пройдите алгоритм шаг за шагом с листом бумаги и карандашом и запишите детали для каждого шага.

Если ваша цель состоит в том, чтобы вычислить число до точности N, то, вероятно, вам лучше использовать уже сделанное решение, изменить свою проблему, чтобы вам не нужна точность N или взглянуть на некоторые другие комментарии/ответы.