Как извлечь корень из числа?

Сообщение №5899 от april 03 декабря 2002 г. 03:56
Тема: Как извлечь корень из числа?

Кто-нибудь знает, как извлечь корень из числа без калькулятора? Заранее благодарен


Отклики на это сообщение:

Тут поможет последовательность:
Допустим а - число из которго нужно извлечь корень. Берем х[1] - начальное приближение (лучше взять x[1]=а/2). И строим последовательность
x[2]=(x[1]+a/x[1])/2
x[3]=(x[2]+a/x[2])/2
и т. д.

Для чисел <100 уже на 5-6 шаге выдается результат с погрешностью <1%

Оговорка - это для извлечения квадратного(!) корня.


> Тут поможет последовательность:
> Допустим а - число из которго нужно извлечь корень. Берем х[1] - начальное приближение (лучше взять x[1]=а/2). И строим последовательность
> x[2]=(x[1]+a/x[1])/2
> x[3]=(x[2]+a/x[2])/2
> и т. д.

> Для чисел <100 уже на 5-6 шаге выдается результат с погрешностью <1%

> Оговорка - это для извлечения квадратного(!) корня.


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


> Кто-нибудь знает, как извлечь корень из числа без калькулятора? Заранее благодарен

Общий - метод Ньютона
f(x)=x^n-a=0
x(k+1)=x(k)-f(x(k))/f'(x(k))=x(k)-(x(k)^n-a)/(n*x(k)^(n-1))


> Кто-нибудь знает, как извлечь корень из числа без калькулятора? Заранее благодарен

Ну если надо извлекать квадратный корень
то до недавнего времени его брали в столбик таким образом
например корень из 625
разбивали все цифры по паре справа налево то-есть 6|25
подбирали чило 2 потому что 2^2 наибольшее из меньших от 6
отнимаем 6-4=2
дописывали пару цифр справа то-есть получали 225
кроме того мы получили 2 умножим его снова на 2 (но не потому что имеем 2 а всегда на 2 множим) получим 4х где вместо хнедостающая цифра
такая что (а лучше скажем 5) так что 45*5<=225
Но у нас 45*5=225 -> мі получили целочисленное решение

Если у Вас хвости остался дописываете 2 дробных нуля и т.д.


> Тут поможет последовательность:
> Допустим а - число из которго нужно извлечь корень. Берем х[1] - начальное приближение (лучше взять x[1]=а/2). И строим последовательность
> x[2]=(x[1]+a/x[1])/2
> x[3]=(x[2]+a/x[2])/2
> и т. д.

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

А где здесь "подбор"? И что такое вообще "универсальный метод извлечения корня из числа"? При извлечении корня даже из целого числа "очень часто" будут попадаться иррациональные числа, которые, как известно, нельзя записать даже в виде бесконечной периодической дроби. А предложенный Вашему вниманию метод сходится всегда и очень быстро (это давно доказанный факт).


Дело в том, что, если существует рациональное решение, предложенный Вами метод его никогда не найдет. Он вовсе не плох для компьютеров, и мало пригоден для карандаша и бумаги, ИМХО


Спасибо, отлично, работает и для вещественных.
Источник не назовете?

> > Тут поможет последовательность:
> > Допустим а - число из которго нужно извлечь корень. Берем х[1] - начальное приближение (лучше взять x[1]=а/2). И строим последовательность
> > x[2]=(x[1]+a/x[1])/2
> > x[3]=(x[2]+a/x[2])/2
> > и т. д.

> > Для чисел <100 уже на 5-6 шаге выдается результат с погрешностью <1%

> > Оговорка - это для извлечения квадратного(!) корня.

>


> Кто-нибудь знает, как извлечь корень из числа без калькулятора? Заранее благодарен

путем разложить функцию f(x)=(x+1)^(1/n) - корень n'ной степени из (x+1) в ряд маклорена, далее появляется еще две проблемы: ряд имеет чрезвычайно медленную сходимость это раз, а два то что полчившиеся в результате разложения дроби без калькулятора не посчитать :)

можно разложить в аналогичный ряд функцию f(x)=a^x, или другими словами e^ln(a)x, получается быстро сдодящийся ряд, с участием иррациональных чисел (в данном случае степени натуральных логарифмов) = summ(0,infinity,n,(x*ln(a))^n)/n!) - a число из которого необходимо извлечь корень, а x - степень корня.

в калькуляторе же непосредственно используется метод итерации, тоесть правое и левое приближения к результату с точностью до E (вместительность дисплея).


Уважаемые участники форума! Какие способы позволяют с максимальной скоростью получать целую часть корня квадратного с целого числа? Меня интересуют числа с количеством знаков около 1000. Буду весьма признателен.


Отклики на это сообщение (покзывать только заголовки - добавить ответ):

--------------------------------------------------------------------------------
Re: Целая часть квадратного корня Анатолий 15 февраля 10:58
> Уважаемые участники форума! Какие способы позволяют с максимальной скоростью получать целую часть корня квадратного с целого числа? Меня интересуют числа с количеством знаков около 1000. Буду весьма признателен.
Наверное Вам надо повторить подвиг по модификации одного из стандартных методов вычисления квадратного корня из числа. Модификация будет заключаться лишь в установке точности результата до целого. Наверное, более быстрых алгоритмов трудно отыскать


о квадратном корне

Можно ли представить целые числа, из которых извлекается квадратный корень нацело, в виде последовательности? Существуют такие работы?


------------------------------------------------
Сообщение от aka , 21 февраля 2003 г. 03:24:
В ответ на : о квадратном корне от TOSHAK , 21 февраля 2003 г.:
> Можно ли представить целые числа, из которых извлекается квадратный корень нацело, в виде последовательности? Существуют такие работы?
> N2
РазныеРазности:

http://hotmix.narod.ru/
http://hotmix.narod.ru/russian/default_rus.html


это я и сам знаю, а припомощи рекурсивной последовательности


> Можно ли представить целые числа, из которых извлекается квадратный корень нацело, в виде последовательности? Существуют такие работы?

Берешь натуральный ряд чисел: 1, 2, 3,….
Возводишь их в квадрат: 1, 4, 9, ……..
Вот это и есть искомая тобой последовательность чисел.
В чем проблема то?


> о квадратном корне

> Можно ли представить целые числа, из которых извлекается квадратный корень нацело, в виде последовательности? Существуют такие работы?

если N - число, принадлежащее целому множеству, и корень квадратныйц из N также принадлежит целому множеству, то N представляется в виде суммы ряда из
sqrt(n) элементов.
Каждый n-ный элемент равен n-ному нечетному числу из натурального ряда.
Тоесть (5^2) равен сумме первых 5 нечетных чисел натурального ряда (1+3+5+7+9).

Следует из формулы суммы арифметической прогрессии: (a(1)+a(n))*n/2.
Где a(1) и a(n) крайние члены последовательности между которыми нужно найти сумму (школьная формула еще).


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


> Проблема в том как, зная, допустим, два последовательных числа, из которых можно извлечь корень, найти следующее. Я в принципе нашёл способ. Интересно о других.

Теперь понятно о чем вы говорите. Но в сообщении №7048 вы буквально написали следующее:
«….это я и сам знаю, а при помощи рекурсивной последовательности?»

Но рекуррентное соотношение достаточно простое
N(i+1) = N(i) +2* i +1;

i - номер элемента в последовательности чисел, являющихся квадратами.
Или я опять чего – то путаю. Приведите свою «рекурсивную последовательность».


> Проблема в том как, зная допустим два последовательных числа, из которых можно извлечь корень, найти следующее. Я в принципе нашёл способ. Интересно о других.
1. с праздником
2. если известны два последовательных числа, из которых извлекается корень принадлежащимй целому множеству (назовем их c1 и с2) то следующее очевидно находится: (4*c2+c1)-(4*sqrt(c2*c1))


N(i+1)=2+2*N(i)-N(i-1)


Есть ли алгоритм вычисления квадратного корня из длинного числа, если учесть что остаток отбрасывается?


--------------------------------------------------------------------------------
Re: длинные числа RElf 18 октября 15:43
> Есть ли алгоритм вычисления квадратного корня из длинного числа, если учесть что остаток отбрасывается?
Как я понял, речь идет о челочисленном корне. Тогда алгоритм такой:

Int isqroot(const Int& x)
{
Int a, b = x;
do {
a = b;
b = ( a + x/a ) / 2;
} while (a>b);
return a;
}

Здесь Int - длинно-целочисленный тип, деления целочисленные с отбрасыванием остатка.



такого алгоритма не существует, кроме полного перебора, именно на этом свойстве основан стандарт цифровой подписи DSA и нек. др. стандарты шифрования


> такого алгоритма не существует, кроме полного перебора, именно на этом свойстве основан стандарт цифровой подписи DSA и нек. др. стандарты шифрования

Вы путаете. DSA делается в некотором конечном поле. Исходный же вопрос был про обычные большие ("длинные") числа.


Господа математики!
вопрос может показаться странным для вас, но как бы не было стыдно мне необходимо спросить!
подскажите пожалуйста метод извлечения корня из простых чисел?
например каким способом нужно извлекать корень 4-й степени из 81 чтобы получилось 3? интересует сам принцип действий...
заранее благодарен!
01 октября 2004 г. 18:00

--------------------------------------------------------------------------------
прологарифмируйте
Xроноп
01 октября 18:13 нов
В ответ на №12837: извлечения корня от Army , 01 октября 2004 г.:
потом поделите на 4, а затем проэкспонируйте. Ж:-))ж
--------------------------------------------------------------------------------
Re: извлечения корня
Volody
01 октября 20:48 нов
В ответ на: извлечения корня от Army ,01 октября 2004 г.:
> Господа математики!
> вопрос может показаться странным для вас, но как бы не было стыдно мне необходимо спросить!
> подскажите пожалуйста метод извлечения корня из простых чисел?
> например каким способом нужно извлекать корень 4-й степени из 81 чтобы получилось 3? интересует сам принцип действий...
> заранее благодарен!
Метод Ньютона я точно его не помню но что то вроде этого
x_{n+1}=x_n - (f(x_n)-a)/f'(x_n)

в данном случае f(x)=x^4
естественно точного значения не получится но точность можно выбрать любую


Большое спасибо!
выходит нет простого метода, чтобы посчитать это значение не теряя времени (ну скажем на калькуляторе)??


> Большое спасибо!
> выходит нет простого метода, чтобы посчитать это значение не теряя времени (ну скажем на калькуляторе)??

Что значит "простой"?
В вычислительной технике для вычисления корней используется метод Ньютона, обладающий квадратичной сходимостью. Для машины - это просто.


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

Т. е. речь о том, что может потребоваться извлечь корень
степени N из числа R, причем с точностью до Z знаков после запятой.
Не критично, если алгоритм сложен...

Обратите внимание, что речь идет о АЛГОРИТМЕ, в то время как
корни при помощи уже готовых функций компьютера нельзя.

У самого идеи две:

1) Членить на простые числа, а потом?..
2) Использовать метод приближений: взять P, где приблизительно
P = R^N. Если с требуемой точностью расчетов P^N < R, то довавить
к P некоторое k, если P^N > R, то отнять от P некоторое k, так пос-
тепенно циклично уменьшая k до тех пор, пока P=R^N в рамках требуемой
точности расчетов.

Какие соображения?
02 декабря 2004 г. 17:23:


> Т. е. речь о том, что может потребоваться извлечь корень
> степени N из числа R, причем с точностью до Z знаков после запятой.

Метод Ньютона:

выбираем начальное приближение X
итерируем формулу X = X + (R - X^N)/(N*X^(N-1))
пока погрешность |R - X^N| не станет меньше заданной.

Для N=2 подробной описание по ссылке:

Вычисления квадратного корня методом Ньютона


А как насчет методом деления отрезка пополам.
Надо сравнивать число с квадратом середины отрезка.
Количестов шагов алгоритма - логарифм числа + логарифм погрешности.
Мне кажется что это самый простой способ.


Мне за вас стыдно, ребята.
Есть отличный способ извлечения квадратного корня столбиком.


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама: Продающих, посмотреть на промышленные полы чита.
Rambler's Top100