восстановление числа A по остаткам от деления

[z994175633105]

В моей теме topic94091.html описан алгоритм определения остатков от числа $A$, взятого по последовательным модулям.
Рекуррентная форма записи алгоритма деления положительного целого числа $A$ на последовательные модули $m_1,m_2=m_1+1.....m_n=m_1+(n-1)...$:
$b_{i+1}=a_i+b_i-C_j\cdot{N_i}$
${N_i}$, тождественно равно модулю $m_i$ но используется в качестве обозначения основания системы счисления в которую переводится число $A$ при взятии его по модулю $m_i$
$a_{i+1}=a_i +C_j$
$a_i $и $b_i$ старший и младший разряды числа взятого по $\mod$$N_i$ ($A\bmod N_i$).
$C_j$ - принимает целые значения 1,2,3... Это единица переноса в старший разряд из младшего в тот момент, когда младший разряд (в результате пошагового накопления) превысил $ N_i $ - вес младшего разряда. $N_i$ вычитается из $b_i$ пока $b_i$ остается положительным. Максимальное количество вычитаний и будет составлять "единицу переноса" равную $C_j$
Из алгоритма непосредственно вытекает формула восстановления числа $A$ по двум последовательным остаткам:
$b_2 = b_1+a_1-C_1\cdot{m_1}$ откуда:
$a_1 = b_2-b_1+C_1\cdot{m_1}$
Имеем систему уравнений:
$a_1 = b_2-b_1+C_1\cdot{m_1}$
$ a_2 = a_1+C_1$
$a_1$-целая часть [ $A/m_1$], $b_1$- остаток от деления $A/m_1$ (простите, строгого математического описания, оформления остатков я не нашел)
$a_2$-целая часть[$A/m_2$],$b_2$- остаток от деления $A/m_2$ решаем систему относительно числа $ A $:

$A = m_2(b_2 - b_1 + C_{1}\cdot{m_2})+b_2$
В реальных устройствах редко применяют восстановление $A$ по двум остаткам . Это связано с ограничением для числа $A$ Китайской теоремой $A < \cdot{m_1}\cdot{m_2}\cdot{m_3}...$, что ограничивает диапазон вычислений. Поэтому,
для $m_3$ и $m_4$ строим идентичную систему уравнений.
Совпадение результата вычислений для $A$ в допустимом числовом диапазоне и будет искомым числом $A$
В данном алгоритме отсутствует операция деление, которая является бичом модульных вычислений.
Строго говоря, из приведенного способа восстановления числа $A$ по остаткам не следует то, что для восстанавливаемого числа $A$ существуют ограничения , определенные в Китайской теореме, а именно то, что
$A < \cdot{m_1}\cdot{m_2}\cdot{m_3}...$,
и восстановление числа $A$ зависит только от правильного подбора параметра $C_j$. Выше приведенный способ, учитывающий ограничения Китайской теоремы , это , думаю, один из способов нахождения единственно правильного $C_j$.
Иначе говоря , алгоритм позволяет восстанавливать исходное $A$ по остаткам при взятии их по модулям.

Алгоритм детерминирован, в сторону вычисления остатков, но имеет варианты при восстановлении исходного числа $A$ по остаткам, в узлах появления единицы переноса в старшие разряды. На участках алгоритма, на которых нет подобного переноса, возможно, однозначное восстановление числа $A$ по одному остатку (при фактическом отсутствии ограничений, наложенных Китайской теоремой).
Существует несколько формулировок Китайской теоремы об остатках. Мое предложение
сформулировать возможность восстановления конкретного значения полинома, многочлена по младшему их разряду и весам каждого разряда.
При переводе числа $ A$ в иную систему счисления число представляется в виде значений полинома у которого младший разряд является остатком от деления новой СС на его новое основание. Вес каждого разряда числа переведенного в новую СС определяется степенью основания системы счисления.
с основанием СС $N_1 = 999, $ $ A=3\cdot999^1+459\cdot999^0 $
В общем виде: $ A=a\cdot N^1+b\cdot N^0$

Алгебра многочленов глубоко проработана. Перед ней можно ставить любую задачу, в том числе вопрос о восстановлении всех его разрядов, если известна только часть разрядов, например, младшие и вес остальных.

[Cash]

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

[z994175633105]

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

Я предлагал в другом форуме задавать наводящие вопросы. Так можно перекинуть мостик.

[arseniiv]

Cash, кроме того, в исходной теме z994175633105 уже признались, что обычный алгоритм для китайской теоремы им был доселе неведом.

[Lia]

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

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

Вы просто не в теме.

Таким образом, Ваш стартовый пост свою задачу не выполнил. Редактируем до ясности.

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

[Deggial]

Тема перемещена из форума «Карантин» в форум «Дискуссионные темы (М)»
Возвращено.

[Brukvalub]

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

..
Делаем предположение: алгоритм можно использовать для вывода более простых (не содержащих операции деление) формул восстановления, чем те, которые используются в данное время.
...

Продемонстрируйте, как реализуется такое "предположение".
Вот я, например, предполагаю, что прочное знание таблицы умножения мигом приводит к доказательству гипотезы Римана, но многие в этом сомневаются.
Нелепые предположения без подтверждений выглядят как грубый само-пиар, преследующий цель раздуть до размеров открытия тривиальные упражнения в началах элементарной теории чисел.

[z994175633105]

Я обязан демонстрировать "таблицу умножения", по словам оппонента?
Могу привести слова специалиста о том, что формула работает: " Не дергайся, Миша, твоя формула работает". Он посоветовал не переоценивать значение параметра $ C_j$.
Лично я хотел бы обратить внимание на этот аспект работы. Именно параметр $C_j$ позволяет выйти за пределы условия $ A<m_1m_2...m_n $. Это важнее других проблем.
"Нелепые предположения без подтверждений выглядят как грубый само-пиар, преследующий цель раздуть до размеров открытия тривиальные упражнения в началах элементарной теории чисел".
"Вот я, например, предполагаю, что прочное знание таблицы умножения мигом приводит к доказательству гипотезы Римана, но многие в этом сомневаются".
Оппонент бездоказательно утверждает,что мое предположение нелепо, иначе, зачем, эти нападки?
Не хотите обсуждать конструктивно? Я могу уйти и без обсуждения. Это просто :).
В форум приходят за советом , за развитием идеи, как это произошло с моим
предположением о том, что через полиномы, возможно восстановление числа A
по младшим разрядам его значений.
https://ru.wikipedia.org/wiki/%CA%E8%F2 ... 2%EA%E0%F5

раздел "алгоритм Гарнера" Этот раздел появился появился совсем недавно. На днях!
Инженер советует, математик реализует. :)

[Deggial]

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

Я обязан демонстрировать "таблицу умножения", по словам оппонента?

Вы в дискуссионном разделе обязаны отвечать на вопросы, заданные заслуженными участниками. Бессодержательные ответы наказуемы.

z994175633105, замечание за неконструктивные формы ведения дискуссии и неправильное оформление цитат.

[Otta]

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

раздел "алгоритм Гарнера" Этот раздел появился появился совсем недавно. На днях!

В 2012 году, можно сказать и на днях, конечно.

[Sonic86]

В общем, суть такова: ТС м.б. изобрел алгоритм вычисления $A \bmod m_1m_2$ по $A \bmod m_1$ и $A \bmod m_2$ (я точно не разбирался, что там у него, потому что изложено довольно коряво, видимо, Карантин не помог, но в принципе подобное возможно).
Однако в отличие от КТО алгоритм этот частичный: $A$ должно иметь только 2 разряда в системах счисления $m_1,m_2$, т.е. по-человечески говоря $A<m_1^3, A<m_2^3$.
Ну и заявление о том, что этот алгоритм быстрее, чем вычисление по КТО голословно: сравнения нет, а если и быстрее, то только на какую-нибудь константу. Может оказаться, что и быстрее, но алгоритм-то частичный. Т.е. по классификации Munin это велосипед без одного колеса, а второе колесо - квадратное.
В общем ниче интересного.

[Brukvalub]

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

Я обязан демонстрировать "таблицу умножения", по словам оппонента?
...

Вы сделали безосновательное предположение: "Делаем предположение: алгоритм можно использовать для вывода более простых (не содержащих операции деление) формул восстановления, чем те, которые используются в данное время."
Вы уже делали такие "финты" на другом форуме, пытаясь там выдать свои детские упражнения в началах элементарной теории чисел за великие открытия. Оттуда вас выгнали за безобразное поведение. Теперь вы повторяете отработанные там приемчики здесь.
Вот я, уже зная, что последует, сразу потребовал от вас подкреплять вашу пустую демагогию делом, чтобы вы не могли раздувать пустой пузырь "великих открытий".
Итак, покажите на примере, как можно использовать алгоритм для вывода более простых (не содержащих операции деление) формул восстановления, чем те, которые используются в данное время.
Это всюду в мире и называют тем, чего вы хотите, то есть "конструктивным обсуждением".
А называть заданные по вашим же заявлениям вопросы "нападками" - очередная демагогия.

[z994175633105]

Otta

Цитата:

В 2012 году, можно сказать и на днях, конечно.

Я в течении двух недель следил за этим разделом. Форма изложения и доказательство со ссылкой на один источник, менялась несколько раз.

(Оффтоп)

Уважаемый Супермодератор, я стараюсь, как могу. соблюдать ваши требования. Пожалуйста, делайте новичкам снисхождение. Часто они не математики и требования к ним слишком строги. За формой, бывает, ускользает содержание и смысл.
Пишешь ответ и думаешь только об одном: "Сейчас забанят", как это было в форуме МГУ, в котором я вынужденно терпел оскорбления пользователя Brukvalub с потаканий модератора. Вы только скажите уходи с форума и я уйду не пикнув. Я уже поделился своими мыслями , может, кто, заинтересуется, если голова "на месте"! Я , только, свои данные оставлю и уйду.

[Brukvalub]

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

Otta

Цитата:

В 2012 году, можно сказать и на днях, конечно.

Я в течении двух недель следил за этим разделом. Форма изложения и доказательство со ссылкой на один источник, менялась несколько раз.
Уважаемый Супермодератор, я стараюсь, как могу. соблюдать ваши требования. Пожалуйста, делайте новичкам снисхождение. Часто они не математики и требования к ним слишком строги. За формой, бывает, ускользает содержание и смысл.
Пишешь ответ и думаешь только об одном: "Сейчас забанят", как это было в форуме МГУ, в котором я вынужденно терпел оскорбления пользователя Brukvalub с потаканий модератора. Вы только скажите уходи с форума и я уйду не пикнув. Я уже поделился своими мыслями , может, кто, заинтересуется, если голова "на месте"! Я , только, свои данные оставлю и уйду.

Итак, вы, как и на другом форуме, отказываетесь отвечать на мой вопрос, переводя дискуссию в выяснение личных отношений? Сейчас, как было там, снова начнете угрожать сообщить обо мне в "компетентные органы", как о "диверсанте, разрушающем Российскую науку"?

[Otta]

z994175633105
Во-первых, что там в Википедии, мало кого волнует. Во-вторых, последняя правка этого раздела была в июне 2014 года, это легко проверяется. Не уводите в сторону. В-третьих, было бы желательно увидеть от Вас конструктивное обсуждение вопроса. Вашей же темы. В частности, ответ на вопрос post995154.html#p995154