Статья написана на основе части курса «анализ алгоритмов» для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных. Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса. Показаны проблемы, возникающие при обработке больших целых чисел, связанные с «нарезкой» цифр. Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга (на англ.). С. 90-95.

The paper is written on the basis of a part of “Analysis of algorithms'' course for students of the Computer science department of the Division of mathematics and mechanics of Saint Petersburg State University. The example of the computer implementation of the Gauss method illustrates the difference between the algebraic complexity (the number of arithmetic operations) of processing integers and the computational complexity which depends on the length of the input data. A formula which specifies the increase in the length of matrix coefficients, along with the implementation the Gauss method, is proved. The problems arising in the processing of large integers associated with ``chopping'' numbers are shown. To overcome the indicated problems, the possibility of using multi-valued integers is proposed. The upper bounds of the number of steps for processing the multi-valued integers is shown to coincide with such bounds for a multi-tape Turing machine.