Zadanie można rozwiązać, implementując zasadę dodawania pisemnego, której przykłady
podaliśmy w rozwiązaniu zadania 3. Zgodnie z tą zasadą dodajemy odpowiadające sobie cyfry
i przeniesienia, zaczynając od prawej strony. Przyjmujemy przy tym, że ostatnie przeniesienie
R[1] (na skrajnie prawej pozycji 1) jest równe zero. Ponadto wiemy, że:
• i-ta cyfra wyniku jest równa (A[i] + B[i] + R[i]) mod p, gdzie R[i] to i-te przeniesienie,
• (i + 1)-sze przeniesienie R[i + 1] jest równe (A[i] + B[i] + R[i]) div p,
gdzie mod i div oznaczają odpowiednio operacje reszty z dzielenia i wyniku dzielenia całkowitego
(tzn. zaokrąglenia dokładnego wyniku dzielenia do liczby całkowitej w dół). Musimy
jednak uwzględnić, że wynik może być o jedną cyfrę dłuższy od dodawanych liczb. Dlatego
przyjmiemy, że wynik ma n+1 cyfr i najbardziej znaczącą cyfrę wyniku zapiszemy na pozycji
n+1.
i ← 1
R[1] ← 0
dopóki i < n+1 wykonuj
c ← A[i] + B[i] + R[i]
C[i] ← c mod p
R[i + 1] ← c div p
i ← i + 1
C[n+1] ← R[n+1]
W modelu odpowiedzi zamieściliśmy trochę inne rozwiązanie:
- zamiast tablicy przeniesień R przechowujemy tylko aktualne przeniesienie, w zmiennej
r;
- pokazujemy tam, jak można uniknąć stosowania operatorów mod i div, korzystamy
przy tym z tego, że A[i]+B[i] jest zawsze nie większe niż 2p – 2, a reszta R[i] jest równa
0 lub 1.