Фонд Развития Физтех Лицея

Лебедев Григорий , 8 класс

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

Руководитель: Киртаева М. А., Научный консультант: Лебедев А. Н.

Выполнение арифметических операций с большими целыми числами (скажем 500 или 1000 десятичных знаков) даже на современных быстродействующих компьютерах вызывает определенные проблемы, т.к. уже простое сложение двух таких чисел не может быть завершено пока не закончится процесс переноса в старшие разряды результата переполнения младших разрядов. Это сильно замедляет любой алгоритм, включающий массовое выполнение арифметических операций с большими целыми числами. В то же время современные двухъядерные или более мощные мультиядерные процессоры могут обрабатывать параллельно сразу несколько однородных процессов с одинаково большой скоростью. Поэтому заманчивой кажется, возможность так организовать арифметику больших целых чисел, чтобы процессы обработки отдельных знаков (цифр) могли идти параллельно и независимо. Но обычные системы счисления: 10-ичная, 2-ичная, 8-ичная и т.д. не удовлетворяют этим требованиям. В своей работе мы построили новые системы счисления, использующие как положительные, так и отрицательные цифры и допускающие избыточные представления чисел, в которых распространение переноса в старшие разряды числа при выполнении арифметических операций ограничено небольшим (одним или двумя) количеством шагов. Конкретно, мы строим такие системы счисления с основанием В, что допустимыми являются все возможные значения цифр от -А, -(А-1), . . . , -1, 0, 1, . . . , А для некоторого натурального числа А < В и допускаем все возможные записи целых чисел с такими цифрами. В результате мы получаем следующую теорему: Теорема 1. Для всякого натурального основания В системы счисления (В >= 3) существует такая натуральная граница А ( А < В ), что допуская в представлении целых чисел с основанием В все возможные значения цифр от -А до А, мы можем так задать элементарные таблицы сложения и умножения цифр, что при сложении и умножении больших целых чисел в такой системе можно всегда добиться, что перенос от переполнения в старшие разряды числа не будет распространяется более чем на фиксированное число шагов. Следствие 1. При В = 10 и А = 6 можно так определить элементарные таблицы сложения и умножения цифр, что перенос переполнения в старшие разряды при выполнении арифметических операций не будет превышать двух шагов. Следствие 2. При использовании системы счисления из следствия 1, можно построить устройства сложения и умножения больших целых чисел таким образом, что при любой длине их эти операции будут выполняться не более двух тактов.

Вернуться к списку тезисов

Обсуждение закрыто.

Владимир Путин:

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

Источник

Андрей Воробьев, губернатор МО:

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

Игорь Агамирзян:

"Наконец-то, «Физтех-лицей» получил замечательное новое здание. К тому же, ему присвоили имя великого человека и ученого Петра Капицы. Сегодня МФТИ обзавелся новым источником для своей кадровой базы, а Московская область — новым центром притяжения для талантливых детей, с которых все начинается."

Константин Новоселов, Нобелевский
лауреат:

"Я по-хорошему завидую вам, сегодняшним лицеистам, и вашим родителям, потому что у вас есть возможность учиться у самых лучших преподавателей и студентов МФТИ. Близость к Физтеху и близость к живой науке дают колоссальные возможности. Вы будете учиться передовым знаниям в прекрасно оборудованных экспериментальных классах».

Н.В.Карлов, ректор МФТИ 1987-97 г.г.

Мы задумывали сделать такую школу, где и работать и учиться будет трудно, но интересно, где будет царить дух Физтеха.
А «Физтех» означает думать творчески…
«Физтех» означает вечное стремление к совершенству во всем

Из книги «Я – Физтех»


Все отзывы
  • Подписаться на рассылку

    * Это поле обязательно
  • Ваши предложения и комментарии Вы можете направить по адресу info@go2phystech.ru