Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | | | |
ну тады ой 24.08.05 14:58 Число просмотров: 3968
Автор: dl <Dmitry Leonov>
|
|
Хотя статья тоже веселая. То Петр Капица что-то там в своей передаче три года назад сказал (при том, что передачу ведет Сергей, а П.Л. умер почти 20 лет назад. То Гаусс доказал теорему для n=4,3 а Эйлер для 5, хотя для n=4 есть доказательство самого Ферма, Эйлер доказал для 3, а Гаусс вообще ничего связанного с ней не доказывал.
|
|
<theory>
|
Кто че знает о доказательстве теоремы Ферма Александром Ильиным из Омска? 24.08.05 04:53
Автор: Zef <Alloo Zef> Статус: Elderman
|
|
По сообщениям оно значительно проще, чем доказательство через теорему Таниямы-Шимуры и, по-видимому близко к доказательству самого Ферма.
|
|
На сайте http://tsurkov-ferma.narod.ru представлено... 18.09.05 21:41
Автор: И. С. Цурков Статус: Незарегистрированный пользователь
|
|
На сайте http://tsurkov-ferma.narod.ru представлено опровержение Доказательства теоремы Ферма, сделанного Ильиным.
|
|
Есть ли алгоритм вычисления Пи с конечной рекурсией? 26.08.05 13:30
Автор: Zef <Alloo Zef> Статус: Elderman
|
Немного оффтоп, но к теме.
Я интересовался вопросами получения бесконечных неповторяющихся последовательностей на основе конечных с использованием конечных алгоритмов в бесконечном цикле. Можно ли такое сделать и на основе какой самой короткой последовательности?
Ответ можно. На основе последовательности 1 0. Корень из 2, например.
Алгоритм, естессно, конечен, в бесконечном цикле, но:
Имеет место бесконечная рекурсия. Т.е. для получения последующих знаков нужно использовать, если не все, то все равно, бесконечно возрастающее количество знаков из предыдущего результата.
А можно ли получить бесконечную последовательность с использованием конечной рекурсии? Т.е. используя ограниченное количество последних знаков предыдущего результата? Я предполагаю, что - нет. Доказательство (не строгое): поскольку количество разрядов ограничено, то неизбежно повторение, максимум через 2^n циклов, где n - ширина фрейма, т.е. число используемых двоичных разрядов. Па-амоему я прав? Тада наличие бесконечной рекурсии в алгоритме вычисления будет необходимым (но не достаточным) условием ирациональности.
И тут вкрались сомнения... Где-то здесь, похоже проскакивал алгоритм вычисления Пи с конечной рекурсией. Или, все-таки с бесконечной? Я их не смотрел - некогда. Кто с ними имел дело - ответте, плз.
И еще:
А что является достаточным доказательством ирациональности? Невозможность выразить в виде дроби m/n, где m и n - целые? А кАк ето доказать?! Невырождение цифровой последовательности в циклически-повторяющуюся? А как Ето доказать?! Вот, доказать вырождение в цикл на основе алгоритма вычисления, это можно... Так, уже теплее!
|
| |
Есть такой алгоритм, но только для систем счисления с... 26.08.05 14:59
Автор: RElf <M> Статус: Member
|
> И тут вкрались сомнения... Где-то здесь, похоже проскакивал
> алгоритм вычисления Пи с конечной рекурсией. Или, все-таки
> с бесконечной? Я их не смотрел - некогда. Кто с ними имел
> дело - ответте, плз.
Есть такой алгоритм, но только для систем счисления с основанием степень двойки.
Вот статья: http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.ps
А вот программа вычисляющая шестнадцатиричные цифры Pi с любого места:
http://www.geocities.com/hjsmithh/Pi/PiQPCpp.html
> И еще:
> А что является достаточным доказательством ирациональности?
> Невозможность выразить в виде дроби m/n, где m и n - целые?
Даже больше, это является определением иррациональности.
> А кАк ето доказать?!
Обычно доказывают через приближение дробями. Дело в том, что рациональное число имеет только конечное число хороших приближений. Поэтому если существует, например, бесконечная последовательность хороших приближений, то число обязано быть иррациональным.
Подробности см. тут: http://mathworld.wolfram.com/IrrationalityMeasure.html
|
| |
Пример (не про пи, но по про e) 26.08.05 13:51
Автор: Heller <Heller> Статус: Elderman
|
Число "e" вычисляется по известному разложению Тейлора. То что оно иррационально - доказано (то что сумма ряда стремится к этому "e" тоже доказано). Это вычисление можно представить как рекурсивную последовательность:
Sn+1=Sn+((n+1)!)-1
Такая последовательность приводит нас к иррациональному числу, однако каждый её элемент зависит только от предыдущего. Вообще если приглядется, то тут идёт сразу три рекурсии - ещё факториал и множитель для факториала, но и то и другое зависит только от одного предыдущего элемента.
Так что получается что всё же можно, но с использованием нескольких рекурсий. Критично ли это самое "НО" не ясно.
|
| | |
Ряд Тейлора - бесконечная рекурсия! 27.08.05 11:34
Автор: Zef <Alloo Zef> Статус: Elderman
|
Конечной она была бы, если бы мы вычисляли результат рекуррентно, используя в каждом цикле несколько последних знаков предыдущего. А тут мы суммируем все члены, начиная с нулевого. Причем, количество значащих цифр в каждом последующем члене растет до бесконечности (это же степень!).
Так, что ряд Тейлора не рекуррентен, но бесконечно-рекурсивен. И использовать его, кстати, для вычисления длинных значений невыгодно - в каждом цикле разрядность растет!
|
| |
Нет, и быть не может. 26.08.05 13:50
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 26.08.05 14:23 Количество правок: 1
|
> А можно ли получить бесконечную последовательность с
> использованием конечной рекурсии? Т.е. используя
> ограниченное количество последних знаков предыдущего
> результата? Я предполагаю, что - нет. Доказательство (не
> строгое): поскольку количество разрядов ограничено, то
> неизбежно повторение, максимум через 2^n циклов, где n -
> ширина фрейма, т.е. число используемых двоичных разрядов.
> Па-амоему я прав? Тада наличие бесконечной рекурсии в
> алгоритме вычисления будет необходимым (но не достаточным)
> условием ирациональности.
>
> И тут вкрались сомнения... Где-то здесь, похоже проскакивал
> алгоритм вычисления Пи с конечной рекурсией. Или, все-таки
> с бесконечной? Я их не смотрел - некогда. Кто с ними имел
> дело - ответте, плз.
Нет, и быть не может.
Неповторяющаяся последовательность - это аналог иррационального числа записанного в дискретной системе счисления.
Алгоритм "вычисляющий" иррациональное число может быть только итеративным, иначе сам алгоритм будет тем-же числом, записанным в другой форме (что само-по-себе очень интересно).
Любой дискретный алгоритм можно представить как некую булеву функцию от множества переменных, которая даёт результат очередной итерации.
Так как результат этой функции зависит только от входящих значений, то для генерации неповторяющийся последовательности (иррациональности), количество входящих переменных должно становиться постепенно больше и больше. Иначе результат булевой функции, рано или поздно, пробежит по всему множеству значений и зациклится.
Увеличивающийся набор переменных можно выразить в виде рекурсии, либо как постепенное до-выделение памяти по ходу работы.
> И еще:
> А что является достаточным доказательством ирациональности?
> Невозможность выразить в виде дроби m/n, где m и n - целые?
> А кАк ето доказать?! Невырождение цифровой
> последовательности в циклически-повторяющуюся? А как Ето
> доказать?! Вот, доказать вырождение в цикл на основе
> алгоритма вычисления, это можно... Так, уже теплее!
В общем случае (насколько я знаю) это не просто, нет никакого "универсального" способа.
Один из вариантов - доказать, что искомое число раскладывается в бесконечный ряд, а потом доказать что в пределе образующий число интеграл не сходится в рациональной точке.
|
| | |
Т.е. значит, я прав! 27.08.05 11:44
Автор: Zef <Alloo Zef> Статус: Elderman
|
> Так как результат этой функции зависит только от входящих
> значений, то для генерации неповторяющийся
> последовательности (иррациональности), количество входящих
> переменных должно становиться постепенно больше и больше.
> Иначе результат булевой функции, рано или поздно, пробежит
> по всему множеству значений и зациклится.
>
> Увеличивающийся набор переменных можно выразить в виде
> рекурсии, либо как постепенное до-выделение памяти по ходу
> работы.
И наличие алгоритма вычисления числа с конечной рекурсией является доказательством его рациональности.
|
| | |
Иррациональное число не всегда вычисляется итеративно 26.08.05 16:42
Автор: amirul <Serge> Статус: The Elderman
|
> Неповторяющаяся последовательность - это аналог
> иррационального числа записанного в дискретной системе
> счисления.
> Алгоритм "вычисляющий" иррациональное число может быть
> только итеративным, иначе сам алгоритм будет тем-же числом,
Пример непериодичной десятичной дроби (иррационального числа): 0.1001000100001...
Формула k-го знака:
digit(k) = {1, если k == 2n - 1, иначе - 0}
> записанным в другой форме (что само-по-себе очень
> интересно).
Алгоритм, вычисляющий число pi рекурсивно тоже по сути является им.
|
| | | |
Или, не прав?! То, что ты предложил и не рекурсивно и не рекуррентно 27.08.05 12:01
Автор: Zef <Alloo Zef> Статус: Elderman
|
Нельзя же рассматривать приписывание в каждом N-ном цикле N нулей и одной единицы, как сумму. Предыдущий-то резульат мы не используем вообще, а не только ограниченное количество последних разрядов!
И разрядность вычислений не растет!
А, нет! Растет!!! Растет разрядность счетчика, а без счетчика - никак. Или, если использовать в качества "счетчика" предыдущий результат, "перебирая", как четки его назад, пока не наткнешься на единицу и каждый раз приписывая в хвост ноль - тогда растет рекурсия.
Другое дело, что рекурсия не бесконечная (т.е. мы не используем все разряды, начиная с 0-го, а просто, все возрастающее количество последних знаков), но бесконечно-возрастающая.
Так. Прием поправку: Необходимым условием ирациональности числа является неограниченное возрастание используемых при его вычислении в каждом цикле разрядов.
|
| | | |
2amirul & 2RElf - я имел в виду немного другое 26.08.05 18:15
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Подмеченное amirul-ом конечно верно, но я имел виду немного другое.
Алгоритм должен быть итеративный, в смысле что:
1) Он не может выдать всё число целиком в дискретной (рациональной) системе счисления;
2) Выдача произвольной цифры не возможна для произвольной системы счисления без итерационных вычислений;
Быстрое вычисление двоичных разрядов π и "позиционные непериодичности" показанные amirul-ом -- это прежде всего "игра" в системы счисления для определенных иррациональных констант.
--
Про память и рекурсию. Имелось в виду что для вычисления большего кол-ва цифробязательнопотребуется больше промежуточных данных (хоть в log() раз но больше), и в конечном счете нужно будет сделать больше вычислений. Алгоритмически, в терминах языка программирования или исполнительного автомата (CPU), это можно выразить в виде рекурсии. Рекурсия, в некотором смысле, так или иначе, будет обязательно. Либо в явном виде (с кадрами стека), либо в рекуррентно-итеративной зависимости в данных.
--
На сем предлагаю "треп" закрыть. Нового мы ничего не изобретем, лишь увязнем в пересказывании битых истин, и объяснениях кто и что именно хотел сказать...
|
| | | | |
Зря ты так: 27.08.05 12:16
Автор: Zef <Alloo Zef> Статус: Elderman
|
> На сем предлагаю "треп" закрыть. Нового мы ничего не
> изобретем, лишь увязнем в пересказывании битых истин, и
> объяснениях кто и что именно хотел сказать...
Дело в том, что я не математик и чтение первоисточников на Английском (те ссылы, которые здесь дали) для меня затруднительно ввиду незнания ихней терминологии.
С проблемами генерации бесконечных последовательностей на основе конечных сталкиваются все программеры (например генерация длинного ключа на основе короткого пароля). А кроме того, меня интересует клеточный автомат "жизнь" в плане вот этого: http://bugtraq.ru/cgi-bin/forum.mcgi?type=sb&b=8&m=77971.
|
| | |
Может. Читайте... 26.08.05 15:02
Автор: RElf <M> Статус: Member
|
> > И тут вкрались сомнения... Где-то здесь, похоже проскакивал
> > алгоритм вычисления Пи с конечной рекурсией. Или, все-таки
> > с бесконечной? Я их не смотрел - некогда. Кто с ними имел
> > дело - ответте, плз.
>
> Нет, и быть не может.
Может. Читайте http://www.cecm.sfu.ca/~pborwein/PAPERS/P123.ps
|
| | | |
А вот и нетушки, даже если бы в статье было написано, что... 26.08.05 15:48
Автор: leo <Леонид Юрьев> Статус: Elderman
Отредактировано 26.08.05 15:51 Количество правок: 1
|
А вот и нетушки, даже если бы в статье было написано, что это возможно и программа работала - я бы не поверил.
При вычислении очень далеких цифр потребуется большая точность вычислений и больше битов для хранения результатов (см. страницу 9).
Использование SC и модульных вычислений лишь позволяет очень эффективно хранить "промежуточные результаты" или говоря по-другому сильно сжать "контекст" вычислений.
Для примера -- какая точность вычислений понадобиться для вычисления цифры π с номером 21024.
|
| | | | |
По моему вопрос был не о том, какая вычислительная мощность понадобится для вычисления k-го знака пи 26.08.05 16:34
Автор: amirul <Serge> Статус: The Elderman
|
|
А возможно ли в принципе вычисление k-го знака без вычисления (k-1) предыдущих. Формула бейли дейтсвительно дает такую возможность. Хотя действительно для вычисления в окрестностях 2-1024 понадобится очень много памяти.
|
| | | | | |
Не совсем! 27.08.05 12:25
Автор: Zef <Alloo Zef> Статус: Elderman
|
> возможно ли в принципе вычисление k-го знака без
> вычисления (k-1) предыдущих.
Я сказал: "С использованием ограниченного количества предыдущих"
Хотя, по началу и предполагал, что обязательно использовать все, или часть, но с самого начала и бесконечно возрастающую. Ты привел пример, когда можно обойтись бесконечно возрастающим количеством последних знаков (см. мои предыдущие ответы). (т.е. в моем первоначальном предположении "червяк" не ползет, а бесконечно-удлинняется, в твоем ползет, но все равно бесконечно удлинняется).
|
| | | | | |
С точностью до наоборот. Памяти почти совсем не понадобится... 26.08.05 17:32
Автор: RElf <M> Статус: Member
|
> Хотя действительно для вычисления в окрестностях 2-1024 понадобится
> очень много памяти.
С точностью до наоборот. Памяти почти совсем не понадобится. А вот вычислять придется долго.
|
| | | | |
Количество дополнительных битов пропорционально логарифму от... 26.08.05 16:29
Автор: RElf <M> Статус: Member
|
> При вычислении очень далеких цифр потребуется большая
> точность вычислений и больше битов для хранения результатов
> (см. страницу 9).
Количество дополнительных битов пропорционально логарифму от номера цифры.
> Для примера -- какая точность вычислений понадобиться для
> вычисления цифры π с номером
> 21024.
Если пользоваться примерной оценкой log2(2n), то потребуется ~1025 дополнительных битов.
|
| | | | | |
Если все так просто, то зачем PiHex-овцам распределенные вычисления 26.08.05 16:46
Автор: amirul <Serge> Статус: The Elderman
|
> Если пользоваться примерной оценкой log2(2n), то
> потребуется ~1025 дополнительных битов.
А они вычисляют "всего лишь" квадрилионный разряд
|
| | | | | | |
А затем, что мы говорили про расход памяти и он тут... 26.08.05 17:21
Автор: RElf <M> Статус: Member
Отредактировано 26.08.05 17:28 Количество правок: 1
|
> > Если пользоваться примерной оценкой log2(2n), то
> > потребуется ~1025 дополнительных битов.
>
> А они вычисляют "всего лишь" квадрилионный разряд
А затем, что мы говорили про расход памяти и он тут ничтожный, но есть еще сложность вычислений - и она тут экспоненциальная, к сожалению. Для того, чтобы вычислить квадрилионный разряд, придется сложить примерно тот же квадрилион чисел с плавающей запятой.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
