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