Вычисление остатков от деления на последовательные модули

[z994175633105]

Есть несколько работ, которые посвящены признакам деления в разных СС. Сергея Гашкова (МГУ). например, или господина Воробьева, "Признаки делимости"адресованных учащимся.
Мне кажется, подход к теме вэтих работах поверхостный. Например, признак делимости на девятку (N-1) позволяет с учетом представленного ниже алгоритма, быстро определять делимость числа на ряд последовательных модулей, без вычисления даже , самих остатков, иначе говоря, возможна быстрая проверка чисел на простоту, что доказывает возможность решения проблем без особых математических "наворотов".

Для того, что бы разделить любое число на $ 9 $ и найти остаток, достаточно
сложить все цифры числа. Видно на примере:
$23 : 9 = 2$ и остаток 5 ($2+3=5$)
$278 : 9 = 30$ и остаток 8 ($2+7+8=17; 1+7=8$)
Аналогично можно найти остаток при делении $ на 99, на 999, на 9999...$
"Принцип девятки" работает в системах счисления с любым целочисленным основанием. Роль «девятки» выполняет число на 1-цу меньшее основания системы счисления (СС), например, если основание СС равно $ 100, 1000.$..
Возьмем число $ A=3456$ и представим в системе счисления с основанием $1000$. Для этого разделим число $3456$ на $N_0=1000$ один раз.
$3456 : 1000 = 3,456$ ;
Значит число $3456_{1000}$ представлено в СС с основанием $N_0=1000$. Запишем его так: $ 3 \cdot1000+456 $, или $3456_{1000}$ –это двухразрядное число, у которого старший разряд $a=3$, младший $b=456$; (b-одноразрядное выраженное в смешанной системе счисления - тысячерично- десятичной)
Теперь, что бы разделить его на $N-1 ( N_1) $ на $999$ и найти остаток $ Amod(N-1)$, достаточно сложить разряды числа в новой СС: $a+b$.
Значит $3+456 = 459$; остаток от деления $3456$ на $999$ равен $459$.
Но, разделив $3456$ на $999$ мы фактически перевели его в СС с основанием $999$ и получили число $3459_{999}$, где $ a=3$ (старший разряд), $b=459$ (младший разряд) тоже одноразрядное. Теперь число $3456$ делим на $998$ в СС с основанием $N- 1=999$:
Остаток от деления равен $ 3+459=462$;
Результат деления записываем как $3462_{998}$;
Теперь мы имеем право, по тем же правилам, разделить на $997$. Причем $997$ - однозначное число в этой СС и на 1-цу меньше основания. То есть “девятка” в данной СС.
Т.о. мы заменили последовательное стандартное деление по последовательным модулям, сложением разрядов.
На некотором этапе данного алгоритма мы видим, что остаток увеличивается на 3 единицы, но этап заканчивается, когда происходит переполнение младшего разряда. Переполнение, это, когда младший разряд b становится равным, или большим "$N-n$" - больше основания счисления и тогда необходимо выполнить перенос единицы в старший разряд "$a$".
Теперь остаток будет увеличиваться на старший разряд ("a" плюс "единица переноса"). Величина единицы переноса определяется целой частью дроби $\frac {b}{N-n}$, где $n$ это $n$-ный перевод в очередную систему счисления ($N_n$),
Вот и все в общих чертах.
Зачем этот алгоритм нужен? Я лично пытался на компе выполнить деление на последовательные модули быстрее, чем компьютер обычно эту процедуру, программу выполняет. Однозначного ответа не получил. Много факторов вмешивается. Например, само кустарное программирование алгоритма.
Есть еще направление исследования:
факторизация числа. Проблема творческая. Я не владею методикой определения сложности алгоритма, что бы сравнить его с существующими. Хотя, признаки деления чисел на основание СС минус единица, позволяют надеяться на конструирование алгоритма факторизации,
вполне конкурентоспособного. Теперь, кажется , высказался. Могу только добавить, что подобных алгоритмов , в которых используется скользящее изменение основания системы счисления, я не нашел. Данный алгоритм как бы существует в пространстве многих систем счисления, но при этом, число "А" представлено в каждой из них. На каждом этапе вычисления остатков от деления на очередной модуль, мы имеем не что иное, как число "А" , но в новой системе счисления, содержащее одновременно искомый остаток в младших разрядах.

[Lia]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неинформативный заголовок;
- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- уточните предмет обсуждения и явно сформулируйте, алгоритм чего именно Вы предлагаете.


Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Deggial]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»
Причина переноса: возвращено
Предмет обсуждения: критика алгоритма

[Sonic86]

z994175633105 в сообщении #982100 писал(а):

Есть несколько работ, которые посвящены признакам деления в разных СС. Сергея Гашкова (МГУ). например, или господина Воробьева, "Признаки делимости"адресованных учащимся.
Мне кажется, подход к теме вэтих работах поверхостный.

Думаете, их кто-то читал?

z994175633105 в сообщении #982100 писал(а):

Например, признак делимости на девятку (N-1) позволяет с учетом представленного ниже алгоритма, быстро определять делимость числа на ряд последовательных модулей, без вычисления даже , самих остатков, иначе говоря, возможна быстрая проверка чисел на простоту, что доказывает возможность решения проблем без особых математических "наворотов".

А вот это уже просто вранье.

Во-первых, задача проверки на простоту проще, чем задача факторизации. Полиномиальный алгоритм проверки на простоту - AKS-тест. Проверка на простоту через факторизацию - стрельба из пушки по воробьям.
Во-вторых, как известно, простой перебор делителей требует минимум $\Omega (\sqrt{n})$ операций, где $n$ - проверяемое число, в то время как на сегодняшний день разработаны алгоритмы со скоростью (оценка сверху!) $O(\exp(C\sqrt{\ln n }\ln\ln ^\epsilon n))$, что очевидно быстрее, чем просто $O(\sqrt{n})$ (решето Эратосфена, простой алгоритм типа Вашего)
Посему, Вам надо пойти в интернеты и скачать книжку Василенко Теоретико-числовые методы в криптографии. Тривиальные алгоритмы типа Вашего разбираются на первых страницах. Далее идут более быстрые и мощные методы, с которыми я Вам предлагаю ознакомиться, прежде чем изобретать велосипеды.

z994175633105 в сообщении #982100 писал(а):

Есть еще направление исследования:
факторизация числа. Проблема творческая. Я не владею методикой определения сложности алгоритма, что бы сравнить его с существующими. Хотя, признаки деления чисел на основание СС минус единица, позволяют надеяться на конструирование алгоритма факторизации,
вполне конкурентоспособного.

вполне бесполезного, см. выше.
Если Вас аргументы не проймут, то для Вас есть проблемы факторизации чисел Ферма и Мерсенна. Берите и проверяйте. Все рекорды фиксируются в интернетах. Успехов.

Относительно вычисления последовательных остатков от деления - оно обычно не нужно, только в качестве задачки студентам на IT-олимпиадах (мне давали, например, там надо было посчитать сумму остатков. Есс-но, я написал алгоритм типа Вашего, только побыстрее)

z994175633105 в сообщении #982100 писал(а):

Могу только добавить, что подобных алгоритмов , в которых используется скользящее изменение основания системы счисления, я не нашел.

Потому что они слишком медленные, потому они никому не интересны.

[z994175633105]

Цитата:

А вот это уже просто вранье.

Хм. Это не вранье. а личная оценка без теории, но, все равно спасибо.

Цитата:

Проверка на простоту через факторизацию - стрельба из пушки по воробьям.

Извините, но меня не поняли.
"С учетом алгоритма", не совсем его реализация. Я имел в виду признак делимости на $N-1$, где N -основание СС, который применим последовательно в каждой СС к исследуемому числу. И сразу всплывает "Вы думаете их кто-нить читает?" :)))). Мою аналогичную тему закрыли в предыдущем форуме и забанили! из-за того, что я тоже эти работы не читал.

Так я закончу:
Признак делимости прост. Если сумма цифр делится на $N-1$ то и число делится,
а само число при переводе в новую СС увеличивается на const. на каждом определенном этапе вычисления. То-есть, думаю, что полная факторизация не требуется.

Этот вопрос не последний, есть еще, который закрыли в "очень умном форуме" до того, как меня забанили.

[provincialka]

(Оффтоп)

z994175633105 в сообщении #983311 писал(а):

Мою аналогичную тему закрыли в предыдущем форуме и забанили! из-за того, что я тоже эти работы не читал.

Не из-за этого. И учтите, интернет -- это большая деревня. Все друг друга знают.

[Sonic86]

z994175633105 в сообщении #983311 писал(а):

а само число при переводе в новую СС увеличивается на const. на каждом определенном этапе вычисления. То-есть, думаю, что полная факторизация не требуется.

Возьмите число типа $pq$, где $p,q$ просты, $p\neq q, p\approx q \Rightarrow p,q\approx \sqrt{n}$ и применяйте свой алгоритм. Очевидно, что пока он не догребет до $p$, он ничего не получит, а $p=O(\sqrt{n})$, значит работать алгоритм в общем случае будет медленно.
И все.
Читайте Василенко. Больше тут говорить не о чем.

[z994175633105]

Цитата:

значит работать алгоритм в общем случае будет медленно.

Уфффф! Вот такой оценки я и хотел добиться! Мне просто было интересно, но на много ли медленнее? Василенко я листал, мне было не понятно из-за специфики изложения.

(Оффтоп)

Госпожа провинциалка, безграмотность проявляли все. Помните, как известный оппонент с пеной у рта доказывал невозможность алгоритма.

И, опять же, не ясно, быстро ли "догребет". Понятно, что модули потребуются не все. Затем, прибавление константы... У Василенко этого нет.

-- 27.02.2015, 12:56 --

Цитата:

Больше тут не о чем говорить

У меня вопрос по восстановлению чисел (полиномов) по остаткам. Я знаю про Китайскую теорему.

Госпожа swedka Предложила восстановить полином , число, в некой СС, если известен хотя бы остаток и основание СС и выполняются условия Китайской теоремы С помощью схемы Горнера.

Это здорово, если возможно.

[Sonic86]

z994175633105 в сообщении #983322 писал(а):

У меня вопрос по восстановлению чисел (полиномов) по остаткам. Я знаю про Китайскую теорему.

Госпожа swedka Предложила восстановить полином , число, в некой СС, если известен хотя бы остаток и основание СС и выполняются условия Китайской теоремы С помощью схемы Горнера.

Вопрос непонятен. О каком полиноме речь? Восстановить число по остатку и основанию системы счисления нельзя.

[shwedka]

(Оффтоп)

Цитата:

Госпожа swedka Предложила восстановить полином , число, в некой СС, если известен хотя бы остаток и основание СС и выполняются условия Китайской теоремы С помощью схемы Горнера.

ТС, забаненный на MATHFORUM.RU под ником njaznajka,
бесстыже лжет. Это он сам взялся восстановить полином , число, в некой СС, если известен хотя бы остаток и основание СС и выполняются условия Китайской теоремы, но ничего не сделал, ссылаясь на опасение, что его идеи будут похищены. Схема Горнера была упомянута совсем по другому поводу.

Ув. Администрация. Я предполагаю, что и на этом Форуме автор забанен.

[z994175633105]

Ув. swedka, я просто не умею лгать. Если имеются несовпадения, то, я так понял, либо меня не поняли. Тему восстановления полиномов я попытаюсь обсудить с участником Sonic86.

Очень надеюсь, меня поймут. Мысли по поводу Китайской теоремы и восстановления числа "А"по двум, или более , взаимно простым остаткам, постараюсь оформить, как этого требуют правила форума. Хочу добавить, что данные вопросы и соображения, это продолжение темы вычисления остатков.

[Deggial]

Убедительная просьба не оффтопить, иначе тема будет закрыта.
Оффтоп обвернут в тег off.

z994175633105, вопросы, не относящиеся к теме, оформляйте в виде новых тем.

[z994175633105]

Хорошо, я открою новую тему, а по поводу алгоритма имеются дополнения.

Если я правильно понимаю, при выполнении алгоритма, число "А" представляется последовательно в виде полиномов , которые в свою очередь являются выражением того же числа в разных СС, а именно:

число

$$3456_{1000}$$

представлено в СС с основанием

$$N_0=1000$$

. Запишем его так:

$$ 3 \cdot1000+456 $$

, или

$$A= 3 \cdot1000^1+456\cdot1000^0 $$

или с основанием

$$N_1 = 999 $$

$$ A=3\cdot999^1+459\cdot999^0 $$

В общем

$$ A=a\cdot N^1+b\cdot N^0$$

[mihailm]

Sonic86 в сообщении #983301 писал(а):

z994175633105 в сообщении #982100 писал(а):

Есть несколько работ, которые посвящены признакам деления в разных СС. Сергея Гашкова (МГУ). например, или господина Воробьева, "Признаки делимости"адресованных учащимся. Мне кажется, подход к теме вэтих работах поверхостный.

Думаете, их кто-то читал?...

А как же? Воробьев вообще классика - просто-просто, а интересно и довольно глубоко.

[Sonic86]

mihailm в сообщении #983460 писал(а):

Sonic86 в сообщении #983301 писал(а):

z994175633105 в сообщении #982100 писал(а):

Есть несколько работ, которые посвящены признакам деления в разных СС. Сергея Гашкова (МГУ). например, или господина Воробьева, "Признаки делимости"адресованных учащимся. Мне кажется, подход к теме вэтих работах поверхостный.

Думаете, их кто-то читал?...

А как же? Воробьев вообще классика - просто-просто, а интересно и довольно глубоко.

Посмотрел: оказывается, это популярная брошюра по признакам делимости для школьников. А мне почему-то подумалось, что это какие-то малоизвестные статьи, напечатанные в каком-то вестнике.
Буду знать.