Короткие примеры C++ кода-1 Кувшинов Д

using namespace std;
// Корректность

void test_isqrt()

{

for (uint32_t n = 0;; ++n)

{

const auto

fpu = isqrt_fpu(n),

dt1 = isqrt_dt1(n),

dt2 = isqrt_dt2(n);



if (dt1 != fpu)

cout << "dt1 " << n << endl;

if (dt2 != fpu)

cout << "dt2 " << n << endl;

if (n == UINT32_MAX)

return;

}

}
// Время

#define TIME_TEST(func)\

double time_##func(unsigned dummy)\

{\

const auto t0 = clock();\

for (uint32_t n = 0; func(n) != dummy && n != UINT32_MAX; ++n) {}\

return double(clock() - t0) / CLOCKS_PER_SEC;\

}
TIME_TEST(isqrt_fpu)

TIME_TEST(isqrt_dt1)

TIME_TEST(isqrt_dt2)
void time_all(const char *msg, int dummy)

{

cout << msg;

cout << "\nfpu: " << time_isqrt_fpu(dummy) << "s\n";

cout << "dt1: " << time_isqrt_dt1(dummy) << "s\n";

cout << "dt2: " << time_isqrt_dt2(dummy) << "s\n\n";

}
int main()

{

test_isqrt();

cout << "Correctness testing done." << endl;

time_all("Full uint32_t range:", 65536);

time_all("First 1/64 of uint32_t range:", 8192);

time_all("First 1/256 of uint32_t range:", 4096);

time_all("First 1/4096 of uint32_t range:", 1024);

cout << "Time testing done." << endl;

//cin.ignore();

return EXIT_SUCCESS;

}

0650-polynomials_estrin2.cpp

// polynomials_estrin2.cpp

// Вычисление многочленов.

#include

#include

#include

#include

using namespace std;
/// близость значений по абсолютной разности

bool abs_close(double a, double b, double tol = 1e-10)

{

return abs(a - b) <= tol;

}
// многочлены
// sum(ai*x^i, i=0:(n-1)) = (...((a(n-1)*x + a(n-2))*x + ...)*x + a0

double poly_horner(double x, double a[], size_t n)

{

assert(n != 0);

auto s = a[--n];

while (n != 0)

s = s * x + a[--n];

return s;

}
// fma(a, b, c) --> (a * b + c) с одним округлением (C99, C++11)

double poly_horner_fma(double x, double a[], size_t n)

{

assert(n != 0);

auto s = a[--n];

while (n != 0)

s = fma(s, x, a[--n]);

return s;

}
// a3*x^3 + a2*x^2 + a1*x + a0 = (a3*x + a2)*x^2 + (a1*x + a0)

// sum(ai*x^i, i=0:(n-1)) =

// (...((a(n-1)*x + a(n-2))*x^2 + (a(n-3)*x + a(n-4)))*x^2 + ...)*x^2 + (a1*x + a0)

// -- метод Горнера по x^2

double poly_estrin2_fma(double x, double a[], size_t n)

{

assert(n != 0);

if (n == 1)

return a[0];
// один шаг схемы Эстрина + метод Горнера + fma

const auto x2 = x * x;

auto s = fma(a[n-1], x, a[n-2]);

for (--n; n > 2; n -= 2)

{

const auto p = fma(a[n-2], x, a[n-3]);

s = fma(s, x2, p);

}
// если был нечётный размер массива, то n == 2, иначе 1

return n != 2? s: fma(s, x, a[0]);

}

///////////////////////////////////////////////////////////////////////////////

// Тестирование
typedef double (*poly_eval_fun)(double, double*, size_t);

bool test_poly_eval(poly_eval_fun poly)

{

double test[] = { 20., -1., 4., 9., -8., 4. };

const size_t size = sizeof(test) / sizeof(double);

return poly(100., test, 1) == 20.

&& poly(0., test, size) == 20.

&& poly(0., test, size - 1) == 20.
&& abs_close(poly(1., test, size - 1), 24.)

&& abs_close(poly(-1., test, size - 1), 8.)

&& abs_close(poly(2.5, test, size - 1), -129.375)
&& abs_close(poly(1., test, size), 28.)

&& abs_close(poly(-1., test, size), 4.)

&& abs_close(poly(2.5, test, size), 261.25);

}
int main()

{

using namespace std;

poly_eval_fun poly[] =

{

poly_horner,

poly_horner_fma,

poly_estrin2_fma

};
for (auto pf: poly)

cout << test_poly_eval(pf);

cout << endl;
return EXIT_SUCCESS;

}

0700-amatrix.hpp

// amatrix.hpp

// Общие задачи обслуживания динамических массивов, которые можно интерпретировать как матрицы.

// Работа на C++ в стиле C.

#ifndef AMATRIX_HPP_INCLUDED_AMA700

#define AMATRIX_HPP_INCLUDED_AMA700
// Используются упакованные двумерные массивы.

// Под "упакованным" понимается массив, все элементы которого расположены в памяти без разрывов.

// Таким образом, фактически двумерный массив является одномерным с особым режимом индексирования.

// Элемент с двумерным индексом (i, j) имеет одномерный индекс (i * cols + j),

// где cols -- количество столбцов (т.е. строки идут друг за другом в памяти).

#include // size_t

#include // calloc, realloc, free
/// Описание матрицы.

struct Matrix_info

{

double *data; ///< Указатель на массив элементов.

size_t rows, ///< Количество строк.

cols; ///< Размер строки (количество столбцов).

};

// Ключевое слово inline позволяет размещать определения функций

// непосредственно в заголовочном файле, что часто удобно, так как не требуется отдельный .cpp файл.
/// Определить количество элементов матрицы mtx.

inline size_t matrix_size(const Matrix_info *mtx)

{

return mtx->rows * mtx->cols;

}
/// Создать динамический массив нужного размера, заполнить поля mtx.

/// Возвращает true в случае успеха и false в случае ошибки.

/// В случае ошибки выделения памяти обнуляет поля *mtx.

inline bool alloc_matrix(Matrix_info *mtx, size_t rows, size_t cols)

{

// Проверить, представимо ли произведение rows на cols в виде значения size_t.

const auto elements = rows * cols;

if (elements / rows == cols &&

(mtx->data = (double*)std::calloc(elements, sizeof(double))))

{

mtx->rows = rows;

mtx->cols = cols;

return true;

}

else

{

mtx->data = nullptr;

mtx->rows = 0;

mtx->cols = 0;

return false;

}

}
/// Освободить динамический массив, привязанный к матрице.

/// Обнуляет поля *mtx.

inline void free_matrix(Matrix_info *mtx)

{

std::free(mtx->data);

mtx->data = nullptr;

mtx->rows = 0;

mtx->cols = 0;

}
/// Переформатировать существующую матрицу под новый размер.

/// Возвращает true в случае успеха и false в случае ошибки.

/// В случае ошибки выделения памяти оставляет поля *mtx неизменными.

inline bool realloc_matrix(Matrix_info *mtx, size_t rows, size_t cols)

{

const auto elements = rows * cols;

// Проверить, представимо ли произведение rows на cols в виде значения size_t.

if (elements / rows != cols)

return false;
if (matrix_size(mtx) < elements)

{

const auto bytes = elements * sizeof(double);

if (bytes / sizeof(double) != elements)

return false; // Столько байт нельзя выделить.
// Попытаться расширить блок.

const auto data = (double*)std::realloc(mtx->data, bytes);

if (!data)

return false;
// Удалось расширить блок.

mtx->data = data;

mtx->rows = rows;

mtx->cols = cols;

return true;

}

else

{

mtx->rows = rows;

mtx->cols = cols;

return true;

}

}
/// Присвоить всем элементам матрицы заданное значение.

inline void fill_matrix(Matrix_info *mtx, double value)

{

const auto elements = matrix_size(mtx);

const auto data = mtx->data;

for (size_t i = 0; i < elements; ++i)

data[i] = value;

}
/// Заполнить матрицу значениями из статического массива (если требуется, выделяет память).

/// Значения полей *mtx должны быть инициализированы (хотя бы нулями).

inline void matrix_from_array(Matrix_info *mtx, size_t rows, size_t cols, const double *arr2)

{

// Подготовить место.

realloc_matrix(mtx, rows, cols);

// Скопировать поэлементно подряд.

const auto sz = matrix_size(mtx);

const auto data = mtx->data;

for (size_t i = 0; i < sz; ++i)

data[i] = arr2[i]; // вместо цикла можно использовать memcpy из cstring

}
/// Создать единичную матрицу размера n x n.

/// Значения полей *mtx должны быть инициализированы (хотя бы нулями).

inline void identity(Matrix_info *mtx, size_t n)

{

// Подготовить место.

realloc_matrix(mtx, n, n);

// Большинство элементов единичной матрицы -- нули.

fill_matrix(mtx, 0.0);

// Но по диагонали идут единицы.

auto write_pos = mtx->data;

for (size_t i = 0; i < n; ++i)

{

*write_pos = 1.0;

write_pos += (n + 1);

}

}
/// Скопировать содержимое одной матрицы в другую.

/// Значения полей *dst должны быть инициализированы (хотя бы нулями).

inline void copy_matrix(const Matrix_info *src, Matrix_info *dst)

{

// Подготовить место под копию.

realloc_matrix(dst, src->rows, src->cols);

// Скопировать всё содержимое массива подряд.

const auto elements = matrix_size(src);

const auto sd = src->data;

const auto dd = dst->data;

for (size_t i = 0; i < elements; ++i)

dd[i] = sd[i];

}
/// Сравнить матрицы на равенство.

inline bool matrices_are_equal(const Matrix_info *a, const Matrix_info *b)

{

// Если размеры матриц не равны, то и матрицы не равны.

if (a->rows != b->rows || a->cols != b->cols)

return false;
// Размеры совпали, сравним поэлементно.

const auto elements = matrix_size(a);

auto ad = a->data, bd = b->data;

for (size_t i = 0; i < elements; ++i)

if (ad[i] != bd[i])

return false;
// Равны поэлементно => равны.