Не зная о реализации, можно выбрать шаблоны, которые могут выявить типичные источники ошибок, такие как сбои в распространении переносов между битами или словами, или угловые случаи при округлении.Типичные модели:
- Полномочия двух: 2 i
- Полномочия двух уменьшены на один: 2 i -1
- Сила двух увеличивается на единицу: 2 i + 1
- Сумма двух степеней двух: 2 i + 2 j
- Разность любых двух степеней двух: 2 i - 2 j
- Дополнение к одному из образцов 1.через 5.
- Дополняют два из любых шаблонов от 1. до 5.
Очевидно, что классы шаблонов перекрываются, что позволяет быстро проверять несколько тестовых векторовв виде «дымовых» тестов, а также углубленной проверки с большим количеством тестовых векторов.Поскольку у деления есть два аргумента, шаблоны для делителей и дивидендов также должны создаваться из разных классов шаблонов.
По моему опыту, эти простые шаблоны удивительно эффективны для устранения ошибок во всех видах арифметических операций, включая целочисленное деление,Применение таких тестовых шаблонов обсуждается в этой классической заметке:
Н.Л. Шрайер, «Проверка компьютерного арифметического блока с плавающей точкой».Технический отчет по вычислительной технике № 89, AT & T Bell Laboratories, 4 февраля 1981 г. (онлайн)
На моей машине x64 тест простой реализации 64-разрядного битового деления с использованиемВсе вышеперечисленные классы шаблонов занимают чуть более минуты со следующим кодом C:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
int64_t v[32768]; /* FIXME: size appropriately */
#define ADDcc(a,b,cy,t0,t1) \
(t0=(b), t1=(a), t0=t0+t1, cy=t0<t1, t0=t0)
#define ADDC(a,b,cy,t0,t1) \
(t0=(b)+cy, t1=(a), t0+t1)
/* bit-wise non-restoring two's complement division */
void my_div_core (int64_t dividend, int64_t divisor, int64_t *quot, int64_t *rem)
{
const int operand_bits = (int) (sizeof (int64_t) * CHAR_BIT);
uint64_t d = (uint64_t)divisor;
uint64_t nd = 0 - d; /* -divisor */
uint64_t r, q = 0; /* remainder, quotient */
uint64_t dd = d; /* divisor */
uint64_t cy, t0, t1;
int i;
q = dividend;
r = (dividend < 0) ? (~0) : 0; // sign-extend
for (i = operand_bits - 1; i >= 0; i--) {
if ((int64_t)(r ^ dd) < 0) {
/* shift 128-bit quantity q:r left by 1 bit */
q = ADDcc (q, q, cy, t0, t1);
r = ADDC (r, r, cy, t0, t1);
r += dd;
q += 0; /* record quotient bit -1 (as 0) */
} else {
/* shift 128-bit quantity q:r left by 1 bit */
q = ADDcc (q, q, cy, t0, t1);
r = ADDC (r, r, cy, t0, t1);
r -= dd;
q += 1; /* record quotient bit +1 (as 1) */
}
}
/* convert quotient from digit set {-1,1} to plain two's complement */
q = (q << 1) + 1;
/* fix up cases where we worked past a partial remainder of zero */
if (r == d) { /* remainder equal to divisor */
q = q + 1;
r = 0;
} else if (r == nd) { /* remainder equal to -divisor */
q = q - 1;
r = 0;
}
/* for truncating division, remainder must have same sign as dividend */
if (r && ((int64_t)(dividend ^ r) < 0)) {
if ((int64_t)q < 0) {
q = q + 1;
r = r - d;
} else {
q = q - 1;
r = r + d;
}
}
*quot = (int64_t)q;
*rem = (int64_t)r;
}
int64_t my_div (int64_t dividend, int64_t divisor)
{
int64_t quot, rem;
my_div_core (dividend, divisor, ", &rem);
return quot;
}
int main (void)
{
int64_t dividend, divisor, quot, ref;
int i, j, patterns, idx = 0, nbrBits = sizeof (uint64_t) * CHAR_BIT;
/* pattern class 1: 2**i */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)((uint64_t)1 << i);
idx++;
}
/* pattern class 2: 2**i-1 */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)(((uint64_t)1 << i) - 1);
idx++;
}
/* pattern class 3: 2**i+1 */
for (i = 0; i < nbrBits; i++) {
v [idx] = (int64_t)(((uint64_t)1 << i) + 1);
idx++;
}
/* pattern class 4: 2**i + 2**j */
for (i = 0; i < nbrBits; i++) {
for (j = 0; j < nbrBits; j++) {
v [idx] = (int64_t)(((uint64_t)1 << i) + ((uint64_t)1 << j));
idx++;
}
}
/* pattern class 5: 2**i - 2**j */
for (i = 0; i < nbrBits; i++) {
for (j = 0; j < nbrBits; j++) {
v [idx] = (int64_t)(((uint64_t)1 << i) - ((uint64_t)1 << j));
idx++;
}
}
patterns = idx;
/* pattern class 6: one's complement of pattern classes 1 through 5 */
for (i = 0; i < patterns; i++) {
v [idx] = ~v [i];
idx++;
}
/* pattern class 7: two's complement of pattern classes 1 through 5 */
for (i = 0; i < patterns; i++) {
v [idx] = -v [i];
idx++;
}
patterns = idx;
for (i = 0; i < patterns; i++) {
for (j = 0; j < patterns; j++) {
dividend = v [i];
divisor = v [j];
/* exclude cases with undefined results: division by zero, overflow*/
if (!((divisor == 0LL) ||
((dividend == (-0x7fffffffffffffffLL - 1LL)) && (divisor == -1LL)))) {
quot = my_div (dividend, divisor);
ref = dividend / divisor;
if (quot != ref) {
printf ("error @ (%016llx, %016llx): quot = %016llx ref=%016llx\n",
dividend, divisor, quot, ref);
return EXIT_FAILURE;
}
}
}
}
printf ("64-bit division: test passed\n");
return EXIT_SUCCESS;
}
В дополнение к вышеупомянутым тестам шаблонов, вы хотели бы добавить target псевдослучайный тествекторы, в частности с акцентом на следующие сценарии:
- Малые делители
- Небольшие частичные
- Небольшие остатки
Подходящий способгенерация тестовых векторов для классов 2. и 3. производится путем построения дивиденда путем умножения (выберите небольшой случайный множитель) и умножения и сложения (выберите небольшой случайный результат) из случайного делителя.
В общем, современныекомпьютеры достаточно быстрые, чтобы выдерживать от 2 32 до 2 48 тестовых случаев в зависимости от скорости системы и скорости эталонной системы.ентация.Возможно, вы захотите использовать такое большое количество текстовых векторов на основе шаблонов, целевых случайных и чисто случайных текстов, чтобы иметь разумный шанс создать правильное 64-битное деление.Пусть тесты будут выполняться в течение дня или, по крайней мере, в течение ночи.
Использование большого количества случайных тестовых векторов требует высококачественного PRNG (генератор псевдослучайных чисел). KISS64 профессора Джорджа Марсальи было бы чем-то вроде минимального стандарта:
/*
From: geo <gmars...@gmail.com>
Newsgroups: sci.math,comp.lang.c,comp.lang.fortran
Subject: 64-bit KISS RNGs
Date: Sat, 28 Feb 2009 04:30:48 -0800 (PST)
This 64-bit KISS RNG has three components, each nearly
good enough to serve alone. The components are:
Multiply-With-Carry (MWC), period (2^121+2^63-1)
Xorshift (XSH), period 2^64-1
Congruential (CNG), period 2^64
*/
static uint64_t kiss64_x = 1234567890987654321ULL;
static uint64_t kiss64_c = 123456123456123456ULL;
static uint64_t kiss64_y = 362436362436362436ULL;
static uint64_t kiss64_z = 1066149217761810ULL;
static uint64_t kiss64_t;
#define MWC64 (kiss64_t = (kiss64_x << 58) + kiss64_c, \
kiss64_c = (kiss64_x >> 6), kiss64_x += kiss64_t, \
kiss64_c += (kiss64_x < kiss64_t), kiss64_x)
#define XSH64 (kiss64_y ^= (kiss64_y << 13), kiss64_y ^= (kiss64_y >> 17), \
kiss64_y ^= (kiss64_y << 43))
#define CNG64 (kiss64_z = 6906969069ULL * kiss64_z + 1234567ULL)
#define KISS64 (MWC64 + XSH64 + CNG64)