Понимаю ваши опасения, но и по-русски, и по-английски (coproduct) это слово пишется слитно. Терминологию я перевожу в соответствии с русским изданием «Категорий для работающего математика» Маклейна.
> Допустим, мы определяем класс Incable инкрементальных типов:
Вдогонку: зачем нам еще один класс инкрементальных типов? Уже есть class Enum с функцией succ из коробки.
> Очень удивительно (я бы даже сказал — внезапно!), но кортеж-пара в GHC является функтором.
Ничего удивительного в этом нет. Все по аналогии с тем, что функтором является левое сечение стрелки (e ->). Поскольку запятая — тип с двумя параметрами (,) :: a -> b -> (a,b), то ее левое сечение (a,) имеет однопараметрический по b тип (a,) :: b -> (a,b) и становится функтором. Теперь должно стать понятно, почему fmap (+1) (2,3) вернет (2, 4).
Там нет скачка. У указанного рекуррентного соотношения есть три неподвижных точки: 3, 5 и 100.
Из них первая и третья — устойчивы, а вторая — неустойчива. Это как в механике: вершина холма — точка неустойчивого равновесия, низ лунки — устойчивого.
Начальные значения подобраны специальным образом, чтобы при точных вычислениях сходиться к 5. Однако малейшее отклонение (неизбежное при вычислениях с плавающей точкой) приведет к раскачке последовательности к 3 или 100.
Например, как только результат вычислений выскочит за 5 (даже на одну гугольную), процесс пойдет в раскачку: если z и y больше 5, то 815-1500/z будет меньше 515 и после деления на y (который чуть-чуть больше 5) будет меньше 103. Эрго, 108-(815-1500/z)/y будет уже больше 5 уже почти на десять гугольных. На следующей итерации отклонение в положительную сторону от 5 вырастет еще в 10 раз и так далее, пока не достигнет следующей точки сгущения 100.
Для любителей матана приведу грубое обоснование пассажа про десять гугольных. Пусть d — бесконечно малая величина и y = z = 5 + d + O(d^2). Тогда f(y, z) = 5 + 43/5 d + O(d^2). Вот этот множитель 43/5 (округленный до 10 в предыдущем абзаце) и раскачивает лодку. В то же время 3 и 100 — устойчивы, поскольку, например, при y = z = 100 + d + O(d^2) имеем f(y, z) = 100 + 157/2000 d + O(d^2), т. е. отклонение уменьшилось в 2000/157 раз.
Существование специальных начальных значений, которые все же ведут к положению неустойчивого равновесия, объясняется тем фактом, что для k = sqrt(283/5)-6 = 1.52 и y = 5 + d + O(d^2), z = 5 + k*d + O(d^2) мы получим f(y, z) = 5 + d/k + O(d^2) — т. е. отклонение от 5 уменьшится в полтора раза и это явление будет рекурсивно повторяться.
Факт «отбрасывание теней» (он же метод решета) в различных ипостасях является очень популярным в любительских исследованиях по теории чисел. Я регулярно встречаю эссе, претендующие на открытие нового алгоритма факторизации, основанные на его применении. Вашу статью от них выгодно отличает неплохой стиль и отсутствие завышенного ЧСВ. Однако фактический уровень математического содержания — такой же.
Читайте книжки по теории чисел и развивайтесь. Когда одолеете стандартный учебник для первого курса (лучше забугорный Hardy & Wright), можете переходить к литературе по методу решета, раз уж оно вам интересно. Например, «Распределение простых чисел» Прахара будет неплохим стартом.
Построение вашего последнего предложения завело меня в тупик.
На уровне идей: справедливость гипотезы Римана означает, что простые числа распределены в некотором смысле наиболее регулярным способом, т. е. в асимптотическом законе простых чисел остаточный член мажорируется корневой оценкой. Это может повлиять на оценки сложности алгоритмов проверки на простоту (и влияет), но у нас они и так полиномиальны. Связь же гипотезы Римана именно с алгоритмами факторизации идейно ничем не обусловлена.
Но, пожалуй, наибольший интерес вызывает возможность уточнения оценки вероятности нахождения простых чисел все дальше и дальше. Если рассматривать матрицы, то мы видим, как вероятность падает, начиная с 4/6, далее до 7/24 (или усредненно 11/30), потом 36/180 (или 47/210), и т.д.
Не понял, о какой вероятности идет речь. Насколько я понял, выше в таком же смысле упоминалась вероятности 2/6 и 8/30.
Вероятность того, что число не делится на последовательные простые p1, ..., pn, есть (1-1/p1)...(1-1/pn), что по теореме Мертенса равно e-γ / ln pn, где γ — константа Эйлера-Маскерони.
Есть множество способов оптимизации, которые намного быстрее простого перебора, однако даже если оптимизация ускорит поиск в 10 раз, достаточно увеличить число на 2-3 десятичных знака (например, в 100 раз), чтобы замедлить поиск в 10^100 раз. Это и значит, что сложность алгоритма является экспоненциальный...
Это ложное утверждение: если умножить число на 100, то поиск замедлится не более, чем в 100 раз. У вас неверные представления об экспоненциальный сложности: она экспоненциальная относительно битовой длины числа, а не относительно самого числа.
К слову, математики не нашли ни доказательства, ни опровержения того, что нельзя найти алгоритм факторизации, сложность которого не была бы экспоненциально зависящей от длины числа. А доказав или опровергнув это, можно, заодно, решить математическую проблему, известную как гипотеза Римана.
Можно ссылку на то, что гипотеза Римана следует из указанного вами утверждения?
Про остальные сферы — не специалист, но с сайтами никаких проблем нет. Есть, например, Yesod — фреймворк на Haskell, сравнимый по уровню с Ruby on Rails. Для сайтов попроще есть тоже масса решений. Я сейчас перевожу backend нескольких проектов, написанных на PHP, на Haskell (Happstack) — сплошное удовольствие от надежности и скорости.
Спасибо, познавательно, но я спрашивал про сравнение именно на Си. Там могут возникать хардверные эффекты (кэш процессора, конвейеризация и т. п.), благодаря которым более просто устроенные алгоритмы будут в реальности работать лучше более сложных. Виртуальная машина такие штуки, наверняка, сглаживает.
Раз dual pivot включен в Java вместо Bentley-McIlroy, то вопросов по производительности в Java нет.
Вот очень интересная статья о том, как оптимизировали алгоритм быстрой сортировки на Си:
Вообще можно придумать бесконечное количество модификаций квиксорта, которые будут предпочтительны в зависимости от языка программирования и железа. Потому что там надо не только считать количество сравнений и перемещений (dual pivot делает меньше сравнений, но больше перемещений, чем классический квиксорт), но и учитывать выпадения за кэш процессора и тому подобные эффекты.
Я не нашел сравнения сишного dual pivot quicksort c хорошо вылизанным one pivot quicksort из первой статьи. Буду благодарен за ссылку.
Поддерживаю. С Makefile на мой вкус получается более unixway: нет привязки к специфическому расширению LaTeX, можно подвязать любой внешний генератор графиков или преобразование входных данных, явно видны все зависимости между файлами в проекте.
Если нужна именно документация, а не учебник, обратите внимание на мануалы Сюткина: «Справочник по командам LaTeX2», «Набор математических формул в LaTeX2», «Русский язык в LaTeX», «Цвет в LaTeX», «Включение рисунков в LaTeX2», «Гипертекст в LaTeX».
Я не передергиваю, а пытаюсь переписать по-человечески ваши определения и обозначения, в которых черт ногу сломит. Засим умываю руки; если вы хотите оставить их своим «ноу-хау» — дело ваше.
Аналогия с числами все же неполная: из произведения чисел тоже не всегда можно восстановить множители. Например, 4 — были ли это 2 и 2 или 4 и 1?
hackage.haskell.org/package/genifunctors-0.3/docs/Data-Generics-Genifunctors.html
Вдогонку: зачем нам еще один класс инкрементальных типов? Уже есть class Enum с функцией succ из коробки.
Ничего удивительного в этом нет. Все по аналогии с тем, что функтором является левое сечение стрелки (e ->). Поскольку запятая — тип с двумя параметрами (,) :: a -> b -> (a,b), то ее левое сечение (a,) имеет однопараметрический по b тип (a,) :: b -> (a,b) и становится функтором. Теперь должно стать понятно, почему fmap (+1) (2,3) вернет (2, 4).
Из них первая и третья — устойчивы, а вторая — неустойчива. Это как в механике: вершина холма — точка неустойчивого равновесия, низ лунки — устойчивого.
Начальные значения подобраны специальным образом, чтобы при точных вычислениях сходиться к 5. Однако малейшее отклонение (неизбежное при вычислениях с плавающей точкой) приведет к раскачке последовательности к 3 или 100.
Например, как только результат вычислений выскочит за 5 (даже на одну гугольную), процесс пойдет в раскачку: если z и y больше 5, то 815-1500/z будет меньше 515 и после деления на y (который чуть-чуть больше 5) будет меньше 103. Эрго, 108-(815-1500/z)/y будет уже больше 5 уже почти на десять гугольных. На следующей итерации отклонение в положительную сторону от 5 вырастет еще в 10 раз и так далее, пока не достигнет следующей точки сгущения 100.
Для любителей матана приведу грубое обоснование пассажа про десять гугольных. Пусть d — бесконечно малая величина и y = z = 5 + d + O(d^2). Тогда f(y, z) = 5 + 43/5 d + O(d^2). Вот этот множитель 43/5 (округленный до 10 в предыдущем абзаце) и раскачивает лодку. В то же время 3 и 100 — устойчивы, поскольку, например, при y = z = 100 + d + O(d^2) имеем f(y, z) = 100 + 157/2000 d + O(d^2), т. е. отклонение уменьшилось в 2000/157 раз.
Существование специальных начальных значений, которые все же ведут к положению неустойчивого равновесия, объясняется тем фактом, что для k = sqrt(283/5)-6 = 1.52 и y = 5 + d + O(d^2), z = 5 + k*d + O(d^2) мы получим f(y, z) = 5 + d/k + O(d^2) — т. е. отклонение от 5 уменьшится в полтора раза и это явление будет рекурсивно повторяться.
Факт «отбрасывание теней» (он же метод решета) в различных ипостасях является очень популярным в любительских исследованиях по теории чисел. Я регулярно встречаю эссе, претендующие на открытие нового алгоритма факторизации, основанные на его применении. Вашу статью от них выгодно отличает неплохой стиль и отсутствие завышенного ЧСВ. Однако фактический уровень математического содержания — такой же.
Читайте книжки по теории чисел и развивайтесь. Когда одолеете стандартный учебник для первого курса (лучше забугорный Hardy & Wright), можете переходить к литературе по методу решета, раз уж оно вам интересно. Например, «Распределение простых чисел» Прахара будет неплохим стартом.
На уровне идей: справедливость гипотезы Римана означает, что простые числа распределены в некотором смысле наиболее регулярным способом, т. е. в асимптотическом законе простых чисел остаточный член мажорируется корневой оценкой. Это может повлиять на оценки сложности алгоритмов проверки на простоту (и влияет), но у нас они и так полиномиальны. Связь же гипотезы Римана именно с алгоритмами факторизации идейно ничем не обусловлена.
Не понял, о какой вероятности идет речь. Насколько я понял, выше в таком же смысле упоминалась вероятности 2/6 и 8/30.
Вероятность того, что число не делится на последовательные простые p1, ..., pn, есть (1-1/p1)...(1-1/pn), что по теореме Мертенса равно e-γ / ln pn, где γ — константа Эйлера-Маскерони.
Это ложное утверждение: если умножить число на 100, то поиск замедлится не более, чем в 100 раз. У вас неверные представления об экспоненциальный сложности: она экспоненциальная относительно битовой длины числа, а не относительно самого числа.
Можно ссылку на то, что гипотеза Римана следует из указанного вами утверждения?
Раз dual pivot включен в Java вместо Bentley-McIlroy, то вопросов по производительности в Java нет.
Вообще можно придумать бесконечное количество модификаций квиксорта, которые будут предпочтительны в зависимости от языка программирования и железа. Потому что там надо не только считать количество сравнений и перемещений (dual pivot делает меньше сравнений, но больше перемещений, чем классический квиксорт), но и учитывать выпадения за кэш процессора и тому подобные эффекты.
Я не нашел сравнения сишного dual pivot quicksort c хорошо вылизанным one pivot quicksort из первой статьи. Буду благодарен за ссылку.