В обычной позиционной системе счисления алгоритм сложения двух чисел разрядности n выполняется за 
шагов. Известные соотношения для сложения чисел в двоичной системе счисления 
, где 
, 
, 
, 
, 
, 
. Перенос 
зависит от переноса в предыдущий разряд 
. Возможно распространения переноса вплоть до старшего разряда. Следовательно, данный алгоритм невозможно распараллелить. Его трудоемкость всегда есть величина . Возможность распараллеливания возникает при использовании избыточных систем. Пусть 
- основание системы. Для записи числа будем использовать цифры 
. При этом появляется избыточность в представлении чисел. Например, число представляется двумя способами 
. Но избыточность дает возможность распараллелить алгоритм сложения. Алгоритм сложения чисел 
и 
выглядит следующим образом.
Алгоритм A1.
1. Параллельно для всех i вычислим переносы 
равные 0 при 
и 1 в противном случае.
2. Вычислим разряды суммы (так же параллельно) по формуле 
, где 
.
В результате работы алгоритма получим число, записанное в избыточной системе счисления. Трудоемкость операции сложения при использовании k процессоров равна 
.
Аналогично, можно рассмотреть избыточную сокращенную систему счисления.
