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

Изобретение относится к области вычислительной техники и может быть использовано в устройствах для генерирования числовых последовательностей. Техническим результатом является эффективное генерирование последовательности фигурных чисел заданного вида. Способ содержит этапы, на которых для первого операнда выбирают производящую функцию и вычисляют квадрат или куб первого операнда на последовательном умножителе с первым АЛУ, сохраняют промежуточный результат в регистре умножения. Одновременно при помощи второго АЛУ переводят первый операнд в дополнительный код до 2-х и суммируют с промежуточным результатом из регистра умножения. Повторяют действия для второго операнда. Одновременно посредством третьего АЛУ вычисляют частное на последовательном делителе. Записывают фигурное число от первого операнда в запоминающее устройство. Производят действия для второго операнда. Повторяют всю последовательность действий для оставшихся операндов. 2 ил.

 

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

Ряд авторских математических методов проф. Шихаева К.Н. и проф. Анохина В.А. основаны на свойствах фигурных чисел и требуют вычисления их последовательностей.

Для обучения решению Великого уравнения Ферма и в некоторых иных случаях предполагается использование последовательностей треугольных и пирамидальных чисел.

Фигурные треугольные и пирамидальные числа, а также их последовательности, могут быть получены на основе известных выражений (Виленкин Н.Я. Комбинаторика. М.: Издательство «Наука», 1969, с. 124):

где - k-е треугольное число;

k - натуральное число.

где - k-е пирамидальное число;

k - натуральное число.

Производящие функции (1), (2) дают последовательность треугольных чисел 1, 3, 6, 10, 15, 21, 28, 36, 45, …, ∞ и последовательность пирамидальных чисел 1, 4, 10, 20, 35, 56, 84, 120, …, ∞. Полученные с использованием выражений (1), (2) последовательности фигурных чисел лишены нуля, что делает указанные выражения непригодными, в частности, для работы с неопределенными уравнениями теории чисел.

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

Авторами установлено, что данные последовательности для натуральных чисел 1, 2, 3, 4, 5, …, ∞ целесообразно вычислять на основе производящих функций (3) и (4), соответственно для треугольных и пирамидальных чисел.

где х - натуральное число.

При x=1 выражения (3) и (4) принимают соответственно вид:

При х>1 выражения (3) и (4) генерируют фигурные треугольные и пирамидальные числа:

Все вышесказанное дает бесконечные последовательности:

последовательность фигурных треугольных чисел =0, 1, 3, 6, 10, 15, 21, 28, 36, 45, …, ∞,

последовательность фигурных пирамидальных чисел =0, 1, 4, 10, 20, 35, 56, 84, 120, …, ∞,

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

В частности, исследовать Великое уравнение Ферма в учебных целях можно на основе тождества Пифагора, взятого авторами в фигурных числах (5).

где x, y, z - натуральные числа;

L_2(x), L_2(y), L_2(z) - соответствующие им треугольные числа.

Тождество (5) получено из элементарного тождества (6) для x и аналогичных тождеств для y и z.

где х - натуральное число;

L_2(x) - соответствующие х треугольное число.

Например, для х равного 10, используя выражение (3), получаем L_2(x)=45, а тождество (6) принимает вид 10²=10+2-45, то есть 100=100, что означает верность данного тождества.

Например, принимая x=3, y=4 и z=5 и беря в тождестве (5) х², y², z² вместо x, y, z, получаем:

.

Подстановка чисел в левую часть этого тождества дает:

х⁴+y⁴-z⁴=3⁴+4⁴-5⁴=81+256-625=-288.

Правая часть того же тождества имеет следующий вид:

Корректность тождества подтверждена равенством его левой и правой частей.

Тождество (5) позволяет получать уравнения Ферма любой степени и обеспечивает их решение благодаря исследованию правой части указанного тождества, представляющей собой уравнение Ферма, заданное в фигурных числах, что расширяет учебные возможности.

В частности, учащиеся выполняют следующие последовательности преобразований.

Из выражения (5):

2²+3²-4²=4+9-16=-3

2+3-4=1

2(L₂₍₂₎+L₂₍₃₎-L₂₍₄₎)=1+3-6=-2

-4+1=-3

-3=-3

Тождество получено.

Также из выражения (5) при линейной форме записи вычислений:

3²+4²-5²=0=3+4-5=2+2(L₂₍₃₎+L₂₍₄₎-L₂₍₅₎=3+6-10=-1)=-2+2=0

Тождества получены.

Далее учащемуся предлагается взять в тождестве (5) вместо чисел x, y, z, числа x², y², z², x³, y³, z³, …xⁿ, yⁿ, zⁿ и построить соответствующие уравнения.

Для чисел xⁿ, yⁿ, zⁿ учащийся получает:

Если предположить, что данное уравнение имеет целочисленное решение, то будет получено:

То есть 1=0, чего не может быть, а уравнение xⁿ+yⁿ=zⁿ не может иметь целочисленные решения.

В качестве примера:

Тождество составлено, а поделив числа его правой части (уравнение в фигурных числах) на число 25, будет получено:

То есть 1=0, чего не может быть, на основе чего учащийся делает вывод о том, что уравнение x⁴+y⁴=z⁴, где х=3, y=4, z=5, не может иметь целочисленных решений.

Свое применение находит и последовательность пирамидальных чисел L_3(x).

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

Из патентного документа RU 2549129 С1 от 20.04.2015 известно устройство для тестирования чисел на простоту, реализующее вычисление выражения N_n=(n²-n)/2, где n - тестируемое число. Известное устройство характеризуется повышенной производительностью при тестировании чисел на простоту, однако при этом устройство имеет ограниченные функциональные возможности, что делает невозможным его использование для генерирования последовательности пирамидальных чисел и запоминания каких-либо числовых последовательностей. Кроме того, конструкция известного устройства не оптимизирована для режима вычислений в потоке, необходимость которого диктуется практикой.

Задачей является эффективное генерирование последовательности фигурных чисел заданного вида и запоминание данной последовательности с целью дальнейшего использования.

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

Технический результат достигается благодаря тому, что способ потокового генерирования последовательности фигурных чисел производящей функцией (3) и/или (4) на основе заданного множества натуральных чисел x, образующих по меньшей мере первый и второй операнды, характеризуется тем, что переводят первый операнд в двоичную форму, выбирают производящую функцию и вычисляют квадрат или куб первого операнда на последовательном умножителе с первым арифметико-логическим устройством (АЛУ), сохраняя промежуточный результат в регистре умножения. Одновременно с этим при помощи второго АЛУ переводят первый операнд в дополнительный код до 2-х, после чего суммируют с промежуточным результатом из регистра умножения, сохраняя промежуточный результат в регистре суммирования. Затем производят перечисленные действия для второго операнда, одновременно с которыми посредством третьего АЛУ вычисляют частное от деления промежуточного результата в регистре суммирования на число 2 или 6 в двоичной форме на последовательном делителе и записывают фигурное число от первого операнда в запоминающее устройство. После чего производят перечисленные действия для второго операнда и повторяют всю последовательность действий для оставшихся операндов.

Изобретение поясняется следующими иллюстрациями.

Фиг. 1: структурная схема вычислительного устройства.

Фиг. 2: основные этапы алгоритма генерирования фигурного числа.

Осуществление настоящего изобретения показано на примере конструкции вычислительного устройства.

Для потокового генерирования последовательности фигурных чисел производящей функцией (3) или (4) используют вычислительное устройство (фиг. 1).

Вычислительное устройство содержит регистр 1 операнда, регистр 2 выбора производящей функции, регистр 3 умножения, регистр 4 суммирования, регистр 5 деления, первое АЛУ 6 умножения, второе АЛУ 7 суммирования, третье АЛУ 8 деления, устройство 9 управления и запоминающее устройство 10.

Регистры 3 и 5 являются сдвиговыми. Регистр 3 выполнен с возможностью осуществления операции «сдвиг вправо», а регистр 5 выполнен с возможностью осуществления операций «сдвиг вправо» и «сдвиг влево». Запоминающее устройство 10 выполнено с возможностью хранения последовательности чисел в двоичной форме.

Первое АЛУ 6 и регистр 3, совместно с устройством 9 управления, образуют последовательный умножитель чисел в двоичной форме для вычисления квадрата или куба операнда.

Второе АЛУ 7, регистр 4 и устройство 9 управления, совместно образуют функциональный узел для перевода операнда в дополнительный код до 2-х и суммирования с сохранением промежуточного результата.

Третье АЛУ 8, регистр 5 и устройство 9 управления образуют последовательный делитель чисел в двоичной форме.

Регистр 1 операнда, последовательный умножитель, функциональный узел для перевода операнда в дополнительный код до 2-х и суммирования, последовательный делитель, а также запоминающее устройство 10 информационно связаны между собой последовательно через свои входы-выходы.

При этом информационный выход регистра 1 электрически связан с первым входом АЛУ 7, вторыми входами АЛУ 6 и регистра 3. Выход регистра 2 связан с первым входом устройства 9. Выход АЛУ 6 связан с первым входом регистра 3. Первый выход регистра 3 связан с первым входом АЛУ 6 и вторым входом АЛУ 7. Второй выход регистра 3 связан со вторым входом устройства 9. Выход АЛУ 7 связан со вторым входом АЛУ 8 через регистр 4. Выход АЛУ 8 связан с первым входом регистра 5. Второй вход регистра 5 связан с устройством 9. Первый выход регистра 5 связан с первым входом АЛУ 8. Второй выход регистра 5 связан с третьим входом устройства 9 и устройством 10. АЛУ 6, 7 и 8, а также регистры 3, 5 связаны с устройством 9 через свои управляющие входы-выходы.

В процессе функционирования описанного вычислительного устройства осуществляется способ потокового генерирования последовательности фигурных чисел производящей функцией (3) и/или (4).

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

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

Выбрав натуральное число переводят его в двоичную форму, после чего записывают в регистр 1. При этом также выбирают производящую функцию (3) или (4). Если выбрана функция (3), то записывают в регистр 2 число 0, а если выбрана функция (4), то в регистр 2 записывают число 1.

После окончания записи в регистры 1, 2 начинает свою работу устройство 9, задающее и контролирующее ход вычислительного процесса.

На информационный вход последовательного умножителя (АЛУ 6 и регистр 3) поступает операнд. Устройство 9 управляет операциями сдвига вправо и записи в регистре 3, считывая его текущее содержимое. При этом, если в регистр 2 записано число 0, то операнд возводится в квадрат, а если в регистр 2 записано число 1, то операнд возводится в куб, в результате чего величина «x²» или «x³» для функции (3) или (4) соответственно оказывается вычисленной и сохраненной в регистре 3 в качестве промежуточного результата.

Одновременно с указанными действиями посредством АЛУ 7 переводят операнд в дополнительный код до 2-х (дополнение до двух) путем инвертирования и сдвига, получая величину «-x» для производящих функций. После этого полученное двоичное число суммируют с промежуточным результатом из регистра 3. В результате работы функционального узла, включающего в себя АЛУ 7 и регистр 4, оказывается вычисленной величина «x²-x» или «x³-x» для функции (3) или соответственно для функции (4). Данная величина сохраняется в качестве промежуточного результата в регистре 4, из которого затем поступает на вход последовательного делителя.

На один из информационных входов последовательного делителя чисел в двоичной форме (АЛУ 8 и регистр 5) подают содержимое регистра 4. Если в регистр 2 было записано число 0, то на другой информационный вход последовательного делителя подают число 2 в двоичной форме, а если в регистр 2 записано число 1, то подают число 6 в двоичной форме. Устройство 9 управляет операциями сдвига вправо и влево, а также записи в регистре 5, считывая его текущее содержимое. В результате получают значение производящей функции от числа х и записывают его в запоминающее устройство 10, формируя в нем последовательность фигурных чисел в двоичной форме. Также в устройстве 10 сохраняют данные, характеризующие соответствующие операнд и производящую функцию.

Следующий операнд помещают в регистр 1 сразу после получения промежуточного результата в регистре 4 и повторяют перечисленные действия, что обеспечивает потоковый режим работы вычислительного устройства.

Таким образом, вычислительное устройство позволяет генерировать числовую последовательность как на основе выражения (3), так и выражения (4), с запоминанием полученных результатов, в результате чего функциональные возможности данного устройства расширены.

Благодаря потоковому режиму работы с задействованием трех АЛУ, работающих одновременно, двух сдвиговых и одного простого регистров, повышена производительность вычислительного устройства. Вместе с тем, его конструкция не содержит лишних и/или сложных элементов и обладает хорошей масштабируемостью для адаптации к работе с числами большой разрядности, что в целом характеризует высокую эффективность генерирования последовательности фигурных чисел.

Способ потокового генерирования последовательности фигурных чисел производящей функцией L_2(x)=(х²-х)/2 и/или L_3(x)=(х³-х)/6 на основе заданного множества натуральных чисел х, образующих по меньшей мере первый и второй операнды, характеризующийся тем, что переводят первый операнд в двоичную форму, выбирают производящую функцию и вычисляют квадрат или куб первого операнда на последовательном умножителе с первым АЛУ, сохраняя промежуточный результат в регистре умножения, одновременно с этим при помощи второго АЛУ переводят первый операнд в дополнительный код до 2-х, после чего суммируют с промежуточным результатом из регистра умножения, сохраняя промежуточный результат в регистре суммирования, затем производят перечисленные действия для второго операнда, одновременно с которыми посредством третьего АЛУ вычисляют частное от деления промежуточного результата в регистре суммирования на число 2 или 6 в двоичной форме на последовательном делителе и записывают фигурное число от первого операнда в запоминающее устройство, после чего производят перечисленные действия для второго операнда и повторяют всю последовательность действий для оставшихся операндов.