| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Извлечение квадратного корня |
| Автор: FoxyMia 31.8.2007, 19:24 |
| Добрый день! Мне необходимо реализовать извлечение квадратного корня из 5 с точностью 10 млн знаков. Посоветуйте , пожалуйста, как это сделать. Если раньше попадались такие фишки-кинть , пожалуйста, линки и т.д. К тому же здесь идет работа с большимми числами, ия не совсем понимаю как ее реализовать. Заранее благодарна. |
| Автор: bsa 31.8.2007, 19:57 |
| Метод реализации алгоритма работы с "большими" числами прост, как 2х2. Представляешь число в виде массива на 10 млн. элементов типа char, каждый из которых принимает значения от 0 до 9. Плюс к этому массиву экспонента (степень десятки) типа int и знак типа bool, например. Хотя, в случае корней знак необязателен. После этого работаешь с этими числами так, как на бумажке (т.е. сложение/вычитание, умножение/деление в столбик). |
| Автор: shara 31.8.2007, 20:01 |
| да, тут без текстовых переменных не обойтись. я делал деление двух чисел, только правда на QBasic, но алгоритм работы поидее тотже. если хочешь могу кинуть исходник. |
| Автор: jonie 31.8.2007, 20:46 | ||
| есть целые библиотеки для работы с длинной арифметикой... например известрейшая gmp... также есть GInt, openSSL.... -------- по поводу математики :
*TeX-а не нашел в кодах ) -------------------- не посмотрел что надо квадратный корень) с ним проще, его можно разложить в ряд тейлора... sqrt(x) = exp ^ {1/2ln(x)} а дальше тейлор .... например.... ЗЫ: по вышке были какие-то книги электронка, если надо - чиркните в приват куда-нить брошу.... аналогично по библиотекам |
| Автор: FoxyMia 31.8.2007, 20:55 |
| Большое спасибо за ответы. ща чего-нить попробую сделать |
| Автор: W4FhLF 3.9.2007, 10:19 |
| Пардон, чисто из любопытства. Зачем сие надо? |
| Автор: bsa 3.9.2007, 10:52 | ||
такие задания любят давать на олипиадах |
| Автор: BaD_SeCt0R 4.9.2007, 02:36 | ||
Помилуйте, как так можно раскидываться памятью? А если знаков 10 миллиардов, триллионов? К тому же из символов составлять слова - далеко не самый быстрый способ |
| Автор: bsa 4.9.2007, 06:41 |
| BaD_SeCt0R, знаешь, если представить число в оперативке в двоичном виде, то как потом его выводить на экран? Имхо, вывести на экран его будет на порядок сложней. |
| Автор: jonie 4.9.2007, 10:07 |
| 10 мегабайт мелочи. Даже 100-400 МБ приемлемо имхо. |
| Автор: -Kp0T- 4.9.2007, 10:14 |
Что то я не вижу что тебе надо хранить эти числа, может ну её сразу в STDOUT  ?Сhar говорите? Верно, но {0-9} прекрасно укладывается в 4-х битный диапазон, то есть получается что ты можешь в байте хранить 2 символа Двоичной ариметикой заморачиваться не стоит, можно к примеру для двух соседних чисел хранить их образуемый ASCII - эквавилент. Поясню на примере:Пусть есть множество 196784 (для краткости, что то оно умещается в 18 бит сейчас несущественно). Расточительно 6 байт расходовать на это число. Можно представить его в 3х байтах: char[3]={19,67,84}. P.S. Можно ещё дампить в файл, к примеру когда не удается выделить требуемую величину памяти, хотя ещё же есть PAGEFILE В свое время, я проект по терверу писал, там последовательность чисел доходила до 600 Мб в файле... |
| Автор: DjoNIK 4.9.2007, 10:16 | ||
Оно-то конечно можно, но на настольный PC(!). Этоуже работа для суперкомпьютеров, где 400 Мб только под один элемент (число). Да и выводит это число даже на ватмане не факт, что получится  Все вшесказанное IMHO. |
| Автор: bsa 4.9.2007, 12:57 |
| Скорее всего это число будет слито, а затем путем тупого сравнения с эталоном будет выяснено, правильно ли посчитано оно или нет. |
