найти как можно больше цифр квадратного корня из 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 цифр
Есть ли какой-нибудь подход к печати?
Решение
Вот код вашего вопроса, который использует библиотеку 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 правильных цифр.
Пример, который вы приводите, точен настолько, насколько точна двойная арифметика, это самая высокая точность, которую использует большинство компиляторов C ++. Как правило, компьютеры не предназначены для более высокой точности вычислений.
Если это какая-то домашняя работа, то я подозреваю, что вы должны выяснить алгоритм расчета — вам нужно иметь собственный массив цифры каким-то образом сохранить всю точность, которая вам нужна.
Если у вас есть какое-то реальное приложение, вам определенно следует использовать высокоточную библиотеку, специально созданную для такого рода арифметики (GMP — хорошая возможность с открытым исходным кодом) — это сложное колесо, которое не нуждается в переизобретении.
Вот решение, которое вычисляет 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