Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Если не будешь читать, что тебе отвечают, то тебе перестанут отвечать 22.10.04 10:44 Число просмотров: 5787
Автор: amirul <Serge> Статус: The Elderman
|
> Я понял что MSDN это такая справка типа стандартной... ))) > Понял что её можно найти в среде разрадотеки.... > > А теперь честно ... мне бы хотелось точно знать как решить > задачи такого рода: > 1. Умножние двух 100 разрядных числа = 200 разрядов Здесь http://www.bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=2&m=113509 тебе уже давали ссылку на алгоритмы сюда: http://algolist.manual.ru/maths/longnum.php
За более быстрыми (и более изощренными и непонятными алгоритмами) тебе уже надо обращаться к серьезным источникам типа того же Кнута (во 2-м томе есть целый раздел посвященный работе с числами произвольной точности) или к библиотекам в исходниках типа того же gmp, но сильно сомневаюсь что начинающему (каким бы гениальным он ни был) это под силу.
> 2. как запомнить все простые числа от 2 до любого 200 > разрядного числа. Давай немного повычисляем. Раз уж ты взялся за простые числа, то должен знать асимптотическую формулу распределения простых чисел: n = N / ln(N), где n - ПРИМЕРНОЕ количество простых чисел, меньших N, ну а N - любое натуральное число (чем больше N, тем точнее эта формула).
10^200 / ln (10 / 200) ~= 10^200 / 460 ~= 2 * 10^197
Ну а длина среднего простого числа на этом диапазоне будет равна средней длине натурального числа на диапазоне. То есть среднее простое число примерно равно
p == sum(n = 1..N, n * P(n)), если учесть, что P(n) для равномерно распределенных натуральных чисел будет равна P(n) = 1 / N, то p == sum(n = 1..N, n / N) == sum(n = 1..N, n) / N == (N * (N - 1) / 2) / N == (N - 1) / 2
При N == 1 * 10^200, среднее число будет равно 5 * 10^199
То есть для его хранения нужно 199 десятичных знаков, если умножить это число на двоичный логарифм десяти (количество двоичных знаков в одном десятичном), то получим 661 бит (или 83 байта) на каждое число.
Теперь умножаем количество простых чисел, которые необходимо сохранить на длину среднего простого числа:
2 * 10^197 * 83 == 1.66 * 10^199
Это количество байт которые тебе понадобятся просто для хранения. Можешь поиграться с порядком, типа
Нужно 10^196 килобайт или 10^193 мегабайт или 10^190 гигабайт. Ну а теперь подумай как ты заработаешь на такое количество памяти
|
|
|