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

В программе есть место жёстко завязанное на тип, — печать числа, а мне хотелось сделать так, чтобы при смене типа ничего не ломалось. Поэтому я решить попробовать обобщённое программирование. Его в Си мне использовать ещё не приходилось, вот и выпал случай.

Заодно попробовал в действии функции __builtin_*_overflow, позволяющие использовать математику с контролем переполнения. Я только недавно задумался о том, что они должны бы быть в языке, а до этого переполнение я проверял дедовским способом — смотрел не стал ли результат меньше аргумента.

Обобщённое программирование выглядит следующим образом:

#define PRINT_U(x) ({ \
    _Generic((x), \
        uint128_t: printf_u128, \
        uint64_t: printf_u64, \
        uint32_t: printf_u32 \
    ); \
})(x)

Тут у меня макрос PRINT_U зависит от типа аргумента, а выбор делается при помощи стандартной конструкции _Generic — она принимает аргумент и, в зависимости от того выражение какого типа было передано, возвращает одно значение из указанного списка.

static void printf_u128(const uint128_t v) {
    unsigned long long low, high;

    #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
        low  = MASK64(v);
        high = MASK64(v >> 64);
    #else
        high = MASK64(v);
        low  = MASK64(v >> 64);
    #endif

    printf("0x%016llX%016llX\n", high, low);
    fflush(stdout);
}

static inline void printf_u64(const unsigned long long v) {
    printf("0x%016llX\n", v);
    fflush(stdout);
}

static inline void printf_u32(const unsigned int v) {
    printf("0x%08X\n", v);
    fflush(stdout);
}

Пока отлаживал, нашёл пару досадных багов в исходной программе. Получается, зря мой ноутбук трудился, результат всё равно можно было бы выкинуть.

Функции переполнения у меня используются вот так:

#define MUL2_ADD1(x) ({ \
    typeof(x) y; \
    __builtin_mul_overflow(x, 2, &y) || __builtin_add_overflow(y, 1, &y) ? 0 : y; \
})

Были сомнения будут ли они работать с 128-битным типом, как я уже писал он какой-то неполноценный, но, к моему удивлению, всё работает прекрасно.

Любопытно, что мой ноутбук на процессоре M3 Max справился с перебором за 57 минут, тогда как компьютер с Intel Core i9-9820X на частоте 3,3 ГГц — за 168 минут. Это на одном ядре, разумеется. У меня в планах сделать многопоточность, но пока недосуг было.

В результате нашлось 14434686 значений, из них нечётных подряд — 172 значения, потом появляются «дырки».