Найти как можно больше цифр квадратного корня из 2
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
double a = sqrt(2);
cout << a << endl;
}
Привет это программа, чтобы найти sqrt из 2, она выводит только 1,41421 в выводе, как реализовать это таким образом, чтобы он напечатал 200000 цифр после десятичной точки
1.41421.......... до 200 000 цифр
Есть ли какой-нибудь подход к печати?
5 ответов
Вот код вашего вопроса, который использует библиотеку GNU GMP. Код напечатает 1000 цифр sqrt(2), увеличьте число в строках с комментариями, чтобы удовлетворить ваш запрос.
#include <stdio.h>
#include <gmp.h>
int main(int argc, char *argv[])
{
mpf_t res,two;
mpf_set_default_prec(1000000); // Increase this number.
mpf_init(res);
mpf_init(two);
mpf_set_str(two, "2", 10);
mpf_sqrt (res, two);
gmp_printf("%.1000Ff\n\n", res); // increase this number.
return 0;
}
Пожалуйста, скомпилируйте его с помощью следующей команды:
$gcc gmp.c -lgmp -lm -O0 -g3
Можно показать, что
sqrt(2) = (239/169)*1/sqrt(1-1/57122)
И 1/sqrt(1-1/57122) можно эффективно вычислить, используя расширение ряда Тейлора:
1/sqrt(1-x) = 1 + (1/2)x + (1.3)/(2.4)x^2 + (1.3.5)/(2.4.6)x^3 + ...
Также доступна программа на C, которая использует этот метод (я немного переформатировал и исправил его):
/*
** Pascal Sebah : July 1999
**
** Subject:
**
** A very easy program to compute sqrt(2) with many digits.
** No optimisations, no tricks, just a basic program to learn how
** to compute in multiprecision.
**
** Formula:
**
** sqrt(2) = (239/169)*1/sqrt(1-1/57122)
**
** Data:
**
** A big real (or multiprecision real) is defined in base B as:
** X = x(0) + x(1)/B^1 + ... + x(n-1)/B^(n-1)
** where 0<=x(i)<B
**
** Results: (PentiumII, 450Mhz)
**
** 1000 decimals : 0.02seconds
** 10000 decimals : 1.7s
** 100000 decimals : 176.0s
**
** With a little work it's possible to reduce those computation
** times by a factor of 3 and more.
*/
#include <stdio.h>
#include <stdlib.h>
long B = 10000; /* Working base */
long LB = 4; /* Log10(base) */
/*
** Set the big real x to the small integer Integer
*/
void SetToInteger(long n, long* x, long Integer)
{
long i;
for (i = 1; i < n; i++)
x[i] = 0;
x[0] = Integer;
}
/*
** Is the big real x equal to zero ?
*/
long IsZero(long n, long* x)
{
long i;
for (i = 0; i < n; i++)
if (x[i])
return 0;
return 1;
}
/*
** Addition of big reals : x += y
** Like school addition with carry management
*/
void Add(long n, long* x, long* y)
{
long carry = 0, i;
for (i = n - 1; i >= 0; i--)
{
x[i] += y[i] + carry;
if (x[i] < B)
carry = 0;
else
{
carry = 1;
x[i] -= B;
}
}
}
/*
** Multiplication of the big real x by the integer q
*/
void Mul(long n, long* x, long q)
{
long carry = 0, xi, i;
for (i = n - 1; i >= 0; i--)
{
xi = x[i] * q;
xi += carry;
if (xi >= B)
{
carry = xi / B;
xi -= carry * B;
}
else
carry = 0;
x[i] = xi;
}
}
/*
** Division of the big real x by the integer d
** Like school division with carry management
*/
void Div(long n, long* x, long d)
{
long carry = 0, xi, q, i;
for (i = 0; i < n; i++)
{
xi = x[i] + carry * B;
q = xi / d;
carry = xi - q * d;
x[i] = q;
}
}
/*
** Print the big real x
*/
void Print(long n, long* x)
{
long i;
printf("%ld.", x[0]);
for (i = 1; i < n; i++)
printf("%04ld", x[i]);
printf("\n");
}
/*
** Computation of the constant sqrt(2)
*/
int main(void)
{
long NbDigits = 200000, size = 1 + NbDigits / LB;
long* r2 = malloc(size * sizeof(long));
long* uk = malloc(size * sizeof(long));
long k = 1;
/*
** Formula used:
** sqrt(2) = (239/169)*1/sqrt(1-1/57122)
** and
** 1/sqrt(1-x) = 1+(1/2)x+(1.3)/(2.4)x^2+(1.3.5)/(2.4.6)x^3+...
*/
SetToInteger(size, r2, 1); /* r2 = 1 */
SetToInteger(size, uk, 1); /* uk = 1 */
while (!IsZero(size, uk))
{
Div(size, uk, 57122); /* uk = u(k-1)/57122 * (2k-1)/(2k) */
Div(size, uk, 2 * k);
Mul(size, uk, 2 * k - 1);
Add(size, r2, uk); /* r2 = r2+uk */
k++;
}
Mul(size, r2, 239);
Div(size, r2, 169); /* r2 = (239/169)*r2 */
Print(size, r2); /* Print out of sqrt(2) */
free(r2);
free(uk);
return 0;
}
Для расчета 200 000 цифр sqrt(2) требуется около минуты.
Однако обратите внимание, что при 200 000 цифр последние 11 произведенных цифр неверны из-за накопленных ошибок округления, и вам нужно запустить его для 200 012 цифр, если вы хотите 200 000 правильных цифр.
Вот решение, которое вычисляет 1 миллион цифр sqrt(2) менее чем за минуту на старом добром языке программирования Prolog. Он основан на решении уравнения Пелла, см. Также здесь:
p*p+1 = 2*q*q
Отношение рекурсивности p′=3p+4q и q′=2p+3q может быть приведено как матричное умножение. А именно, мы видим, что если мы умножим вектор [p,q] на матрицу коэффициентов, мы получим вектор [p',q']:
| p' | | 3 4 | | p |
| | = | | * | |
| q' | | 2 3 | | q |
Для матрицы A мы можем использовать двоичную рекурсию, чтобы мы могли вычислить A^n в O(log n) операциях. Нам понадобятся большие числа. Я использую этот экспериментальный код здесь, в результате чего основная программа тогда просто:
/**
* pell(N, R):
* Compute the N-the solution to p*p+1=2*q*q via matrices and return
* p/q in decimal format in R.
*/
pell(N, R) :-
X is [[3,4],[2,3]],
Y is X^N,
Z is Y*[[1],[1]],
R is Z[1,1]*10^N//Z[2,1].
Следующий скриншот показывает время и некоторые результаты. Я использовал 10 раз по миллиону итераций. Здесь можно сравнить результат с этой страницей.
Чего не хватает, так это четких критериев и вычислений, которые говорят о том, сколько цифр стабильно. Нам понадобится больше времени, чтобы сделать это.
Изменить 20.12.2016:
Мы немного улучшили код с помощью верхней границы относительной ошибки и дополнительно вычислили стабильные цифры, подтолкнув результат. Время вычисления для 1 миллиона цифр теперь меньше 2 секунд:
?- time(pell(653124, _, S)).
% Uptime 1,646 ms, GC Time 30 ms, Thread Cpu Time 1,640 ms
S = -1000000
Пример, который вы приводите, точен настолько, насколько точна двойная арифметика, это самая высокая точность, которую использует большинство компиляторов C++. Как правило, компьютеры не предназначены для более высокой точности вычислений. Если это какая-то домашняя работа, то я подозреваю, что вы должны выяснить алгоритм расчета - вам нужно каким-то образом сохранить собственный массив цифр, чтобы сохранить всю необходимую вам точность. Если у вас есть какое-то реальное приложение, вам определенно следует использовать высокоточную библиотеку, специально созданную для такого рода арифметики (GMP - хорошая возможность с открытым исходным кодом) - это сложное колесо, которое не нуждается в переизобретении.
Эта следующая функция Javascript будет принимать целое число и цифры /precision, необходимые после десятичной дроби, а затем возвращать строковый формат квадратного корня.