### CodingKnight's blog

By CodingKnight, 2 years ago, Hello Math lovers,

The following is a C++ data structure whose constructor uses arithmetic difference equations of the form $f(n+1)-f(n)$ to generate all squared integers up to a given upper bound $N$ without multiplication.

struct squares: std::vector<int64_t> {
squares(int64_t N) {
for (int64_t f = 0, g = 1; f <= N; ++g)
push_back(f), f += g++; } };


It is well known in arithmetics that if $f(n) = n^2$ and $g(n) = 2n+1$, then $f(n+1) = f(n)+g(n)$ and $g(n+1) = g(n)+2$. The initial state for the iterative algorithm is $f(0) = 0$ and $g(0) = 1$.

Alternatively, squared integers up to $N$ could have been generated using multiplication directly without using difference equations.

struct direct_squares: std::vector<int64_t> {
direct_squares(int64_t N) {
for (int64_t f, n = 0; f = n*n, f <= N; ++n)
push_back(f); } };


The following is the C++ program written to compare the performance of both data structures.

using Clock = std::chrono::high_resolution_clock;
using Time  = std::chrono::time_point<Clock>;
inline Time Now() { return Clock::now(); }
template<class T>
inline int64_t msec(T t) {
return std::chrono::duration_cast<std::chrono::milliseconds>(t).count(); }

inline std::string type_name(const std::string &s) {
int i = 0;
while (isdigit(s[i]))
++i;
return s.substr(i); }

template<class T>
void test() {
const Time initial_time = Now();
const T s(1e14);
const int64_t t = msec(Now()-initial_time);
const auto name = type_name(std::string(typeid(T).name()));
std::cout << "struct " << name << ": elapsed time " << t << " msec.\n"; }

int main() {
test<squares>(),
test<direct_squares>(); }


The following is the results of running the performance evaluation program.

A. Using G++14 6.4.0

struct squares: elapsed time 110 msec.
struct direct_squares: elapsed time 112 msec.

=====
Used: 218 ms, 197032 KB


B. Using G++17 7.3.0 (32-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 93 msec.

=====
Used: 234 ms, 197040 KB


C. Using G++17 9.2.0 (64-bit)

struct squares: elapsed time 121 msec.
struct direct_squares: elapsed time 94 msec.

=====
Used: 218 ms, 198056 KB  Comments (0)