Циклы for становятся медленнее, чем дольше они повторяются? Почему эти два исполнения цикла for различны?

В настоящее время я создаю собственную структуру BIG_INTEGER на чистом C в качестве проекта для времяпрепровождения. Одна из функций, которую я решил реализовать в своем проекте, — это PRNG, которая возвращает случайное BIG_INTEGER с указанным количеством цифр.

Это структура BIG_INTEGER:

typedef struct BIG_INTEGER
{
    BOOL bHasSign, bInit;
    SIZE_T szLength;
    INT* arrnDigits;
} BIG_INTEGER, *PBIG;

Это код, который я придумал для PRNG.

VOID birndl(PBIG pbigOut, ULONG szLength)
{
    if (pbigOut->bInit != 1)
    {
        // Initialize the input with binew() first.
        fprintf(stderr, "birndl!1: no content");
        abort();
    }
    else
        // Simply resets the values and frees the int array
        bidel(pbigOut);
    // Prepare
    pbigOut->bInit = TRUE;
    pbigOut->bHasSign = FALSE;
    pbigOut->szLength = szLength;
    pbigOut->arrnDigits = malloc(szLength * sizeof(INT));
    if (pbigOut->arrnDigits != NULL)
    {
        NTSTATUS ntErr;
        UCHAR buf[512];
        SIZE_T index1, index2, index3, index4;
        // Fill buffer with random bytes
        ntErr = BCryptGenRandom(NULL, buf, 512, BCRYPT_USE_SYSTEM_PREFERRED_RNG);
        if (!NT_SUCCESS(ntErr))
        {
            fprintf(stderr, "birndl!2: bcrypt failed with code %ld", ntErr);
            abort();
        }
        index1 = index2 = index3 = index4 = 0;
        *(pbigOut->arrnDigits) = (buf[index1] * buf[index2] * buf[index3] * buf[index4]) % 10;
        // Zero cannot be the first digit, since the resulting length would be szLength - 1
        // Slightly biased, but the show must go on; transfer the chances of getting a #0 to #5
        if (*(pbigOut->arrnDigits) == 0)
            *(pbigOut->arrnDigits) = 5;
        // By multiplying 4 selected UCHAR in the buffer mod 10, a digit from 0-9 is obtained
        for (SIZE_T _iter = 1; _iter < szLength; ++_iter)
        {
            // Select a different UCHAR from the buffer for every iteration
            if (index1 == 512 && index2 < 512)
            {
                index2++;
                index1 = 0;
            }
            else if (index1 == 512 && index2 == 512 && index3 < 512)
            {
                index3++;
                index2 = 0;
            }
            else if (index1 == 512 && index2 == 512 && index3 == 512 && index4 < 512)
            {
                index4++;
                index3 = 0;
            }
            else if (index1 == 512 && index2 == 512 && index3 == 512 && index4 == 512)
            {
                fprintf(stderr, "birndl!3: exceeding capability");
                abort();
            }
            else
                index1++;
            *(pbigOut->arrnDigits + _iter) = (buf[index1] * buf[index2] * buf[index3] * buf[index4]) % 10;
        }
    }
    else
    {
        fprintf(stderr, "birndl!4: memory error");
        abort();
    }
}

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

LARGE_INTEGER frequency, start, end;
QueryPerformanceFrequency(&frequency);
QueryPerformanceCounter(&start);
ULONGLONG length = 10000000;
BIG_INTEGER num;
binew(NULL, &num);
birndl(&num, length);
PCHAR str = bistr(&num);
bidel(&num);
free(str);
QueryPerformanceCounter(&end);
printf("QPC: Program took %fs to finish. (digits=%I64u)\n",
    (double)((end.QuadPart - start.QuadPart)) / frequency.QuadPart, length);
_CrtDumpMemoryLeaks();

Обратите внимание, что я пробовал это и с другими степенями 10 ниже, чем 10M. Это сводка его производительности с использованием того же метода устранения неполадок, за исключением того, что я соответствующим образом изменил значение length.

1-10 K digits: instantly
100 K digits: 0.5~0.6 seconds
1 M digits: 47~53 seconds
2 M digits: ~197 seconds
10 M digits: >10 minutes and still not finished

Если следовать здравому смыслу, кто генерирует 10M цифры, верно? Однако я хотел знать, есть ли лучший и быстрый способ генерировать такие большие суммы. Я подумал, может быть, если скорость for-цикла снижается по мере выполнения итерации, то, возможно, я смогу сначала разделить значения, передать их через birndl с меньшими итерациями, преобразовать эти BIG_INTEGER результаты в строку и, наконец, объединить их в одну большую строку. . Вот код точки входа вместе с bistr, который преобразует мой BIG_INTEGER в строку.

INT main(VOID)
{
    LARGE_INTEGER frequency, start, end;
    QueryPerformanceFrequency(&frequency);
    QueryPerformanceCounter(&start);
    // Compute necessary values
    ULONGLONG aim_digits = 10000000;
    UINT divisions = 2500;
    ULONGLONG per_division = aim_digits / divisions;
    // Create an array of BIG_INTEGER values
    BIG_INTEGER* list = malloc(sizeof(BIG_INTEGER) * divisions);
    // Store the string forms of the BIG_INTEGER values here
    // Last element (hence +1) would contain the concatenation of all strings in the array
    PCHAR* strlist = malloc(sizeof(PCHAR*) * (divisions + 1));
    assert(list != NULL && strlist != NULL);
    // Iterate for each division
    for (SIZE_T i = 0; i < divisions; ++i)
    {
        binew(NULL, &list[i]);
        birndl(&list[i], per_division);
        // Convert generated portion into a string
        strlist[i] = bistr(&list[i]);
    }
    // Allocate
    strlist[divisions] = malloc(aim_digits + 1);
    assert(strlist[divisions] != NULL);
    // Start concatenating everything
    strcpy(strlist[divisions], strlist[0]);
    for (SIZE_T i = 1; i < divisions; ++i)
        strcat(strlist[divisions], strlist[i]);
    // Make sure to free all the used memory by the end
    for (SIZE_T i = 0; i < divisions; ++i)
    {
        bidel(&list[i]);
        free(strlist[i]);
    }
    free(strlist[divisions]);
    free(strlist);
    free(list);
    QueryPerformanceCounter(&end);
    printf("QPC: Program took %fs to finish. (digits=%I64u)\n",
        (double)((end.QuadPart - start.QuadPart)) / frequency.QuadPart, aim_digits);
    _CrtDumpMemoryLeaks();
    return 0;
}

PCHAR bistr(PBIG pbigIn)
{
    if (pbigIn->bInit != 1)
    {
        fprintf(stderr, "bistr!1: no content");
        abort();
    }
    PCHAR pstrOut = calloc(pbigIn->szLength + pbigIn->bHasSign + 1, sizeof(CHAR));
    if (!pstrOut)
    {
        fprintf(stderr, "bistr!2: memory error");
        abort();
    }
    if (pbigIn->bHasSign)
        strcat(pstrOut, "-");
    for (SIZE_T i = 0; i < pbigIn->szLength; ++i)
    {
        CHAR digit[2];
        snprintf(digit, 2, "%d", pbigIn->arrnDigits[i]);
        strcat(pstrOut, digit);
    }
    return pstrOut;
}

Я провел тестовый прогон «логарифмически» с примерно 4000 цифрами на деление, и это дало чрезвычайно потрясающие результаты!

d - digits; v - divisions
10d,5v:        }
100d,25v:      }
1Kd,25v:       } instantly
10Kd,25v:      }
100Kd,25v:     }
1Md,250v: 0.5~0.6 seconds
10Md,2500v: 6.6~7.0 seconds
100Md,25000v: ~197 seconds

Это определенно намного быстрее, чем простой способ использования PRNG. Он генерирует 100 миллионов цифр за то же время, что и первый метод, когда он пытался сгенерировать 2 миллиона!

Однако, как следует из названия, мне также интересно, почему birndl приводит к тому, что скорость for-цикла со временем ухудшается. Есть ли способ оптимизировать его так, чтобы он работал так же или, по крайней мере, почти так же, как «метод разделения», или это просто природа for-циклов замедляться со временем во время итераций, что следует сохранять количество итераций мало для поддержания эффективности?

Почему второй метод будет быстрее, который использует birndl много раз среди других дополнительных шагов (bistr, strcat), но с меньшим количеством пройденных итераций по сравнению с первым методом, который просто говорит birndl сгенерировать очень большое количество цифр за один раз?

Спасибо!