Тестирование процедур деления многоразрядных чисел

[Paul Kellerman]

Иногда приходится реализовывать алгоритмы деления многоразрядных
чисел (с произвольным количеством разрядов) и с произвольным осно-
ванием системы счисления B >= 2 (необязательно 10). Алгоритмы деле-
ния известны и описаны в множестве книг по программированию, крип-
тографии и компьютерной алгебре. Однако в таких книгах почти ничего
говорится как тестировать корректность процедуры деления, какие вы-
бирать числа для тестирования всех особых случаем алгоритма деления.
Генерация случайных пар делимого и делителя (причем делимое больше
делителя) часто даже после миллиона испытаний не попадают на особые
случаи и ветки алгоритма, отвечающие за эти случаи, остаются непрове-
ренными и нет гарантий того, что не осталась какая-то скрытая ошибка,
которая потом неожиданно проявит себя в самый неподходящий момент.

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

Делимое 6-разрядное B-ичное число (В - четное): B/2+1, 2, 0, B/2-2, B-5, 0
Делитель 3-разрядное B-ичное число (В - четное): B/2, B/2+1, B/2
Частное получается 4-разрядное B-ичное число: 1, 0, B-1, B-3
Остаток получается 3-разрядное B-ичное число: B/2, B/2-1, B/2

В частности, в традиционной 10-й системе счисления тестовые числа:
Делимое: 620350
Делитель: 565
Частное: 1097
Остаток: 545

Таким образом, одним тестом можно проверить на вшивость всю процедуру.