Я побоялся, что если начну спамить формулами, то потеряю читателя. Поэтому спрятал все промежуточные вычисления под спойлер. Кто хочет, может заглянуть. Но если вы не знакомы с внутренней логикой работы КТО, вам будет трудно понять, откуда берутся промежуточные многочлены. Всё-таки, обратный по модулю многочлен — это довольно хардкорная вещь.
Поэтому я просто сразу привёл результат. В конце концов, основная моя мысль состоит в том, что быстрое умножение — это алгебраический алгоритм, основанный на многочленах и КТО. А то, что он иногда совпадает с БПФ — это почти случайность.
Подробности довольно громоздки, их можно найти в моём трактате, на который я дал ссылку в конце. И я спрятал вычисления с китайской теоремой под спойлер.
Идея в том, что если у нас есть значения многочлена в двух точках, допустим 4 и 5: P(4) = 3500, P(5) = 7667, то мы можем с помощью китайской теоремы об остатках (КТО) восстановить многочлен P(x) mod (x - 4)(x - 5).
На каждом таком шаге длина многочлена увеличивается в два раза, пока степень не сравняется со степенью результата. И это получается быстрое умножение в натуральных точках, без использования комплексных чисел.
С корнями из единицы этот алгоритм становится чуть быстрее. Обратные многочлены для (x^n ± r) оказываются равны ±1/(2r), и применение КТО превращается в (a + b)/2 + (a - b)/(2r) x^n. Что идентично БПФ.
И жил он в России, и похоронен в России, и его потомки лет сто рулили Российской академией наук, и в конце концов их признали дворянским родом Российской Империи. https://ru.wikipedia.org/wiki/Эйлеры
Я бы сказал, что очень странно не считать Эйлера российским математиком.
Для меня лично демонстрация быстрого умножения через китайскую теорему об остатках оказалась весьма наглядной и убедительной. На каждом шаге длина многочлена увеличивается в два раза. Тут становится совершенно понятно, почему оказывается быстро, и откуда берётся логарифм.
Разумеется, эта статья не претендует на глубокое и точное описание всех особенностей БПФ. Это огромная тема, в которой очень многое сделано. Я лишь привёл небольшой обзор основных моментов. Более того, как я показал в конце, для решения задач умножения больших чисел фокусироваться на одном БПФ не стоит.
Что касается хранения данных, то можно вспомнить, что БПФ обладает свойством эрмитовой симметричности. Это значит, что половина результата является комплексно-сопряжённой, а значит её можно не хранить. Хранить нужно (N -2)/2 комплексных чисел, а также два действительных. Если эти два действительных упаковать в одно комплексное, то получится N/2 пар, или же всего N чисел. Это очень удобно — у нас на входе N чисел и на выходе N чисел. Преобразование можно делать прямо в том же куске памяти, что даёт дополнительное ускорение из-за использования кеша процессора.
Или же можно сказать, что они простые с равной вероятностью. Которая для случайных чисел равна 1/ln x. Вы можете генерировать случайные числа, и именно с такой вероятностью вам будут попадаться простые.
Хорошо, соглашусь, что в пределе к бесконечности простых чисел становится исчезающе мало, что в первой половине бесконечности, что во второй.
Но это не имеет никакого отношения к весам последовательностей. В этой статье я хотел рассказать вам о просеивании и его эффектах на практике. И мне кажется, вы слишком увлеклись теоремой о распределении простых чисел и проглядели основную мысль статьи.
Если вас зацепила эта тема, предлагаю написать простейший просеиватель, это буквально несколько строк в любом языке программирования. После того, как вы увидите, как ведут себя числа на практике, понять это с теоретической стороны будет легче.
Вы приравняли log 2x к log x. Это принципиально неверно — в каждом следующем отрезке длины n простых чисел всё меньше, и меньше, и меньше.
Другое дело — просеивание. Оно всегда даёт примерно одно и то же число кандидатов в диапазоне. Если совместить эти два факта, получится, что вероятность простоты кандидатов неуклонно снижается. То есть мы получили теорему.о распределении простых чисел.
То, что вы написали, неверно. Количество простых чисел уменьшается с ростом n. А вот количество "выживших" чисел после просеивания остаётся примерно одинаковым для любого отрезка n при фиксированной глубине просеивания. Думаю, именно этот момент вызывает сложности. Просеивание не зависит от теоремы.о распределении простых чисел, оно зависит от произведения вероятностей.
Если мы возьмём нечётные числа, то из этого произведения можно удалить первую 1/2, что приводит к увеличению количества "выживших" в два раза.
Я побоялся, что если начну спамить формулами, то потеряю читателя. Поэтому спрятал все промежуточные вычисления под спойлер. Кто хочет, может заглянуть. Но если вы не знакомы с внутренней логикой работы КТО, вам будет трудно понять, откуда берутся промежуточные многочлены. Всё-таки, обратный по модулю многочлен — это довольно хардкорная вещь.
Поэтому я просто сразу привёл результат. В конце концов, основная моя мысль состоит в том, что быстрое умножение — это алгебраический алгоритм, основанный на многочленах и КТО. А то, что он иногда совпадает с БПФ — это почти случайность.
И да, технически, я вывожу БПФ из КТО.
Подробности довольно громоздки, их можно найти в моём трактате, на который я дал ссылку в конце. И я спрятал вычисления с китайской теоремой под спойлер.
Идея в том, что если у нас есть значения многочлена в двух точках, допустим 4 и 5: P(4) = 3500, P(5) = 7667, то мы можем с помощью китайской теоремы об остатках (КТО) восстановить многочлен P(x) mod (x - 4)(x - 5).
P(x) mod (x - 4)(x - 5) = 3500(-1)(x - 5) + 7667(x - 4) = 4167x - 13168
Легко проверить, что многочлен 4167x - 13168 принимает значения 3500 и 7667 в точках 4 и 5. То же самое для точек 2 и 3.
P(x) mod (x - 2)(x - 3) = 937x - 1458
Теперь у нас два многочлена 4167x - 13168 и 937x - 1458. Мы можем восстановить с помощью КТО многочлен третьей степени:
P(x) mod (x - 2)(x - 3)(x - 4)(x - 5) = 135x^3 - 610x^2 + 1422x - 1068
На каждом таком шаге длина многочлена увеличивается в два раза, пока степень не сравняется со степенью результата. И это получается быстрое умножение в натуральных точках, без использования комплексных чисел.
С корнями из единицы этот алгоритм становится чуть быстрее. Обратные многочлены для (x^n ± r) оказываются равны ±1/(2r), и применение КТО превращается в (a + b)/2 + (a - b)/(2r) x^n. Что идентично БПФ.
И жил он в России, и похоронен в России, и его потомки лет сто рулили Российской академией наук, и в конце концов их признали дворянским родом Российской Империи.
https://ru.wikipedia.org/wiki/Эйлеры
Я бы сказал, что очень странно не считать Эйлера российским математиком.
Для меня лично демонстрация быстрого умножения через китайскую теорему об остатках оказалась весьма наглядной и убедительной. На каждом шаге длина многочлена увеличивается в два раза. Тут становится совершенно понятно, почему оказывается быстро, и откуда берётся логарифм.
Разумеется, эта статья не претендует на глубокое и точное описание всех особенностей БПФ. Это огромная тема, в которой очень многое сделано. Я лишь привёл небольшой обзор основных моментов. Более того, как я показал в конце, для решения задач умножения больших чисел фокусироваться на одном БПФ не стоит.
Что касается хранения данных, то можно вспомнить, что БПФ обладает свойством эрмитовой симметричности. Это значит, что половина результата является комплексно-сопряжённой, а значит её можно не хранить. Хранить нужно (N -2)/2 комплексных чисел, а также два действительных. Если эти два действительных упаковать в одно комплексное, то получится N/2 пар, или же всего N чисел. Это очень удобно — у нас на входе N чисел и на выходе N чисел. Преобразование можно делать прямо в том же куске памяти, что даёт дополнительное ускорение из-за использования кеша процессора.
Думаю, здесь речь идёт об умножении очень коротких чисел, реализованном в железе. Это, мягко говоря, совсем другая задача, нежели описанная в статье.
Правый график умножение, а не сложение. Получается минус квадрат синуса.
Именно поэтому интегральный логарифм даёт гораздо более точную оценку числа простых, чем n/ln n.
https://ru.wikipedia.org/wiki/Интегральный_логарифм
Или же можно сказать, что они простые с равной вероятностью. Которая для случайных чисел равна 1/ln x. Вы можете генерировать случайные числа, и именно с такой вероятностью вам будут попадаться простые.
Продолжу пример с первой и второй тысячами.
При просеивании их на глубину 11, мы получаем следующие результаты:
из первой тысячи остаётся 207 кандидатов, из которых только 168 простые.
из второй тысячи остаётся 209 кандидатов, из которых только 135 простые числа.
из диапазона [9000..10000] остаётся снова 207 кандидатов, из которых простыми являются лишь 112 чисел.
Плотность распределения простых чисел никак не влияет на результаты просеивания.
Хорошо, соглашусь, что в пределе к бесконечности простых чисел становится исчезающе мало, что в первой половине бесконечности, что во второй.
Но это не имеет никакого отношения к весам последовательностей. В этой статье я хотел рассказать вам о просеивании и его эффектах на практике. И мне кажется, вы слишком увлеклись теоремой о распределении простых чисел и проглядели основную мысль статьи.
У вас последнее выражение неправильно посчитано.
И я могу вас уверить, что для любого n число простых в [2..n] сильно больше, чем в [n..2n]. В первой тысяче 168, во второй 135.
Если вас зацепила эта тема, предлагаю написать простейший просеиватель, это буквально несколько строк в любом языке программирования. После того, как вы увидите, как ведут себя числа на практике, понять это с теоретической стороны будет легче.
Вы приравняли log 2x к log x. Это принципиально неверно — в каждом следующем отрезке длины n простых чисел всё меньше, и меньше, и меньше.
Другое дело — просеивание. Оно всегда даёт примерно одно и то же число кандидатов в диапазоне. Если совместить эти два факта, получится, что вероятность простоты кандидатов неуклонно снижается. То есть мы получили теорему.о распределении простых чисел.
То, что вы написали, неверно. Количество простых чисел уменьшается с ростом n. А вот количество "выживших" чисел после просеивания остаётся примерно одинаковым для любого отрезка n при фиксированной глубине просеивания. Думаю, именно этот момент вызывает сложности. Просеивание не зависит от теоремы.о распределении простых чисел, оно зависит от произведения вероятностей.
Если мы возьмём нечётные числа, то из этого произведения можно удалить первую 1/2, что приводит к увеличению количества "выживших" в два раза.
Не сомневаюсь, что проявятся ещё какие-нибудь узоры.
Если взять N целых чисел и N нечётных, то после просеивания обоих множеств нечётных очевидно останется больше.
Да, спираль Сакса и треугольник Клаубера выглядят отлично. Но это иллюстрации того же самого принципа на других последовательностях.
Да, конечно. Когда мы говорим про делится/не делится, мы подразумеваем натуральные числа.