03.04.2020, 06:52 [+3 UTC]
в нашей команде: 4 325 чел. | участники онлайн: 3 (рекорд: 21)

:: РЕГИСТРАЦИЯ

задать вопрос

все разделы

правила

новости

участники

доска почёта

форум

блоги

поиск

статистика

наш журнал

наши встречи

наша галерея

отзывы о нас

поддержка

руководство

Версия системы:
7.83 (12.03.2020)
JS-v.1.35 | CSS-v.3.37

Общие новости:
28.03.2020, 20:29

Форум:
28.03.2020, 21:05

Последний вопрос:
02.04.2020, 20:19
Всего: 151914

Последний ответ:
03.04.2020, 05:08
Всего: 259919

Последняя рассылка:
02.04.2020, 21:45

Писем в очереди:
0

Мы в соцсетях:

Наша кнопка:

RFpro.ru - здесь вам помогут!

Отзывы о нас:
18.04.2017, 09:53 »
svrvsvrv
Большое спасибо за консультацию и ссылку на фильм. [вопрос № 190896, ответ № 274918]
31.03.2011, 13:45 »
Данилов Евгений
Спасибо за информацию, но суть вопроса не в нахождении бесплатного хостинга, а именно в посторойке своего веб сервера. я щас пользуюсь услугами хостера, в районе 140р в месяц - совсем не напряжно. Но как я объяснял, поднадоело и хотелось бы разобраться с созданием своего сервера. [вопрос № 182680, ответ № 266490]

РАЗДЕЛ • С / С++

Создание программ на языках C и C++.

[администратор рассылки: Андрей Кузнецов aka Dr_Andrew (Старший модератор)]

Лучшие эксперты в этом разделе

Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 849
CradleA
Статус: Профессор
Рейтинг: 561
solowey
Статус: Специалист
Рейтинг: 517

Перейти к консультации №:
 

Консультация онлайн # 72791
Раздел: • С / С++
Автор вопроса: Mystic
Отправлена: 26.01.2007, 20:49
Поступило ответов: 3

Как вычислить корень квадратный из 2 с точностью до 1000000 знака? Точнее как это число вывести (т.е. не обязательно хранить в памяти). И как вообще хранить числа с большой степенью точности и производить над ними стандартные опреации сложение, деление и тд. С помощью разложения ряда (1+z)^a в ряд Тейлора получаю бесконечную сумму, в которой нету бесконечно длинных членов (таких как 1/3 = 0.3333333). Однако как это использовать не знаю smile Или может есть другие способы? помогите плиз)

Приложение:

Состояние: Консультация закрыта

Ответ # 139387 от Рязанов Максим Валерьевич

Здравствуйте, Mystic!
Для хранения и работы с дробными числами используются типы float и double.
В переменной типа float могут храниться положительные и отрицательные числа с плавающей точкой, абсолютные значения которых лежат в интервале от 3.14^-38 до 3.14^38, а для double интервал от от 1.7^-308 до 1.7^308. Над этими типами можно проводить стандартные арифметические операции.
Удачи.


Консультировал: Рязанов Максим Валерьевич
Дата отправки: 26.01.2007, 21:07

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Здравствуйте, Mystic!

Интересная задачка smile Давайте размышлять.

Очевидно, хранить число в готовых типах не получится. Скорее всего нужно хранить его по цифрам (например, массив char-ов для экономии памяти), и реализовывать "вручную" операции сложения, умножения, возведения в степень между массивами char-ов (Вы ж это знаете, сложение и умножение в столбик smile При желании в Кнуте можно найти более мощные алгоритмы). При желании можно ещё лучше экономить память по аналогии с хранением двух цифр в 1 байте (аналог ассемблеровского упакованного BCD (тут и намёк на то, что в Ассемблере есть готовые операции для работы с таким представлением чисел smile )), но это достаточно жестокое усложнение программы.

Кроме того, ряд Тейлора плохо позволяет оценить точность (хотя можно утверждать, что когда очередной член ряда становится меньше погрешности в некое число n раз, то точность достигнута).

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

Если A[0] - первое приближение (взятое произвольно), N - число, из которого требуется взять корень, то каждое следующее приближение A[i+1] вычисляется как:
A[i+1] = (N/A[i] + A[i])/2
Тут получается штука следующего рода. Мы избавляемся от реализации умножения, но остаёмся при делении и сложении. Погрешность конечного приближения не превосходит разности двух последних вычисленных приближений. (т.е. в Вашем случае считаем до тех пор, пока разность больше 10^(-7)).

По всей видимости, от раздельного хранения цифр и ручного вычисления Вам никуда не уйти. Ещё есть различные библиотеки ( http://www.swox.com/gmp/ ), где это уже сделано за Вас. Однако, если это, например, задание в институте, то вряд ли покатит..


Консультировал: Neil
Дата отправки: 26.01.2007, 23:09

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Ответ # 139412 от Bob Johnson

Здравствуйте, Mystic!
дада, ни float, ни double, ни даже extended тебе тут не помогут :)

придется реализовывать свою арифметику (это по-любому). Я хочу предложить тебе другой вариант вычисления корня. Дело в том, что деление реализовывать весьма трудно (намного труднее умножения!) в то время как умножение при умелом подходе можно заменить сложением. Короче, двоичный алгоритм вычисления квадратного корня такой:

пусть есть число А = 2^n, удовлетворяющее следующим условиям:
1. A*A < 2 (т.е. А не превосходит корня из двух)
2. (А*2)*(А*2) > 2 (т.е. если мы возьмем А = 2^(n + 1), то это число уже будет превосходить корень из двух).
Тогда можно смело сказать, что А – это первое двоичное приближение корня из двух. Очевидно, что А = 1, т.к. 1*1 = 1, а 2*2 = 4. Т.е. первое двоичное приближение корня из двух – это единица. Теперь непосредственно алгоритм.

Пусть n – это номер шага, а s – приблизительное значение корня из 2 на этом шаге. Тогда на нулевом (начальном шаге) n = 0, s [0] = 1 = 2^0. На каждом следующем шаге алгоритма мы будем определять один следующий бит результата. Т.е. на первом шаге мы определим бит 2^(-1), на втором – 2^(-2) и т.п. Правило определения бита такое: если (s [n – 1] + 2^(-n) )^2 > 2) то s [n] = s [n – 1], иначе s [n] = s [n – 1] + 2^(-n). Т.е. мы временно присваиваем тестируемому биту единицу, возводим получившееся число в квадрат и сравниваем с двойкой. Если результат оказался больше 2, то тестируемый бит никак не может быть единицей, т.к. результат уже превосходит 2. Если же результат оказывается меньше 2, то тестируемый бит должен быть единицей, т.к. его еще не хватает до получения 2. Таким образом, нам всего лишь нужна одна операция умножения на один бит результата.

Но даже это много, когда мы говорим о числе с миллионом разрядов! Значит, от операции умножения придется уйти. В данной ситуации это достаточно просто. Пусть у нас есть s [n - 1] – это приблизительное значение корня из 2-х на (n - 1)-м шаге. Значит на n-м шаге мы определяем бит 2^(-n). Т.е. нам надо посчитать (s [n - 1] + 2^(-n))^2 и сравнить его с двумя. Разложим квадрат:
(s [n - 1] + 2^(-n))^2 = (s [n - 1])^2 + 2*(s [n - 1])*2^(-n) + 2^(-2*n) = (s [n - 1])^2 + (s [n - 1])*2^(-n + 1) + 2^(-2*n)

А теперь допустим, что значение (s [n - 1])^2 у нас тоже есть (обозначим его S [n – 1]). Тогда что остается? Взять s [n – 1], сдвинуть его на (n – 1) разрядов вправо (умножение на 2^m эквивалентно сдвигу на m разрядов вправо), добавить к нему S [n – 1] (это операция сложения) и установить бит 2^(-2*n) (этот бит будет находиться далеко «вправо» от общего результата, поэтому можно смело быть уверенным, что его значение всегда изначально равно нулю, поэтому его можно просто устанавливать). Полученное число и будет (s [n - 1] + 2^(-n))^2.

Теперь его необходимо сравнить с 2-й – ну это очень просто – проверяем бит 2^1 = 2, если его значение равно единице, значит установка бита 2^(-n) искомого корня приводит к превышению произведением двух, т.е. его значение должно быть нулем. Это означает, что s [n] = s [n – 1], а S [n] = S [n – 1] соответственно. В противном же случае, s [n] = s [n – 1] + 2^(-n + 1), а S [n] равняется только что полученному произведению. Это дает возможность без дополнительных вычислений перейти к следующему шагу.

Пример вычисления по шагам.
0. n = 0, s [0] = 1.0000, S [0] = 1.0000 – начальные значения
1. n = 1, тестируемый бит 2^(-1), тестовое произведение равно S [0] + s [0]*2^(-1+1) + 2^(-2) = 1.0000 + 1.0000*1.0000 + 0.0100 = 1.0000 + 1.0000 + 0.0100 = 10.0100. Результат больше двух, значит s [1] = 1.0000, S [1] = 1.0000
2. n = 2, тестируемый бит 2^(-2), тестовое значение S [1] + s [1]*2^(-2 + 1) + 2^(-4) = 1.0000 + 1.0000*0.1000 + 0.0001 = 1.0000 + 0.1000 + 0.0001 = 1.1001. Результат меньше двух, значит s [2] = 1.0100, S [2] = 1.1001
3. n = 3, бит 2^(-3), тестовое значение S [2] + s [2]*2^(-3 + 1) + 2^(-6) = 1.1001 + 1.0100*0.0100 + 0.000001 = 1.1001 + 0.0101 + 0.000001 = 1.111001, меньше двух, s [3] = 1.0110, S [3] = 1.111001
4. n = 4, бит 2^(-4), тестовое значение S [3] + s [3]*2^(-4 + 1) + 2^(-8) = 1.111001 + 1.0110*0.0010 + 0.00000001 = 1.111001 + 0.001011 + 0.00000001 = 10.00010001, больше двух, s [4] = 1.0110, S [4] = 1.111001
5. И так далее…

Какой результат мы получили? Значение корня больше 1.0110 = 1 + 0.25 + 0.125 = 1.375, но меньше 1.0111 (это показал 4-й шаг) = 1.4375 что верно, т.к. значение корня из двух ~ 1.41.

Таким образом, остается реализовать полученный алгоритм :)
Для реализации алгоритма прежде всего необходимо посчитать, сколько двоичных цифр необходимо для представления миллиона десятичных. Это будет 1 000 000/log (2) = 3 321 929 или 415 242 байт. А в процессе работы нам понадобится 3 таких числа – одно для хранения s [n], второе – для хранения S [n] и третье для хранения промежуточного тестового результата. Размерность всех трех чисел может быть одинаковой. Но если ты внимательно фтыкал алгоритм, то мог бы заметить, что бит 2^(-2*n) увеличивает разрядность S [n] вдвое, почему же я сказал, что S [n] может быть такой же разрядности как и s [n]? Да просто потому, что как только значение бита 2^(-2*n) перестанет укладываться в разрядность s [n], его можно не учитывать (все равно не попадает в результат), т.е. все три числа могут иметь одинаковую разрядность. Но разрядность следует взять с запасом – хотя бы сотню дополнительных разрядов, чтобы случайно не потерять из-за них точность (при сдвиге s [n - 1] на (n – 1) разрядов вправо будет теряться точность). А можно взять все числа удвоенной разрядности, тогда точность не будет теряться вообще, но упадет скорость алгоритма.
Продолжение в приложени... не влазит блин

Приложение:


Консультировал: Bob Johnson
Дата отправки: 27.01.2007, 02:44

Рейтинг ответа:

0

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

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

Яндекс Rambler's Top100

главная страница | поддержка | задать вопрос

Время генерирования страницы: 0.16575 сек.

© 2001-2020, Портал RFPRO.RU, Россия
Калашников О.А.  |  Гладенюк А.Г.
Версия системы: 7.83 от 12.03.2020
Версия JS: 1.35 | Версия CSS: 3.37