core.exception.OutOfMemoryError@(0) с использованием большого динамического массива

import std.math;
import std.bigint;
import std.stdio;

BigInt sum_min_pfactor(long N){
    BigInt f(int n) {
        return BigInt(n)*(BigInt(n)+1) / 2 - 1;
    }

    int v = cast(int)(sqrt(float(N)));

    bool[] used;
    used.length = v+1;

    BigInt ret;
    BigInt finish;

    BigInt[] s_sum,s_cnt,l_cnt,l_sum;
    s_sum.length = v+1;
    l_sum.length = v+1;
    s_cnt.length = v+1;
    l_cnt.length = v+1;

    for (long i = 0; i <= v; i++) {
        s_cnt[i] = i - 1;
        s_sum[i] = f(cast(int)i);
    }

    for (long i = 1; i <= v; i++) {
        l_cnt[i] = N / cast(int)i - 1;
        l_sum[i] = f(cast(int)(N) / cast(int)i);
    }

    for (long p = 2; p <= v; p++) {
        if (s_cnt[p] == s_cnt[p-1]) {
            continue;
        }

        BigInt p_cnt = s_cnt[p-1];
        BigInt p_sum = s_sum[p - 1];
        long q = p * p;

        ret = ret + p * (l_cnt[p] - p_cnt);
        l_cnt[1] = l_cnt[1] - l_cnt[p] + p_cnt;
        l_sum[1] = l_sum[1] - (l_sum[p] - p_sum) * p;

        long interval = (p & 1) + 1;

        if (v > N / q) {
            finish = N / q;
        }
        else {
            finish = v; 
        }

        for (long i = p+interval; i <= finish; i += interval){
            if (used[i]) {
                continue;
            }

            long d = i * p;

            if (d <= v) {
                l_cnt[i] = l_cnt[i] - l_cnt[d] + p_cnt;
                l_sum[i] = l_sum[i] - (l_sum[d] - p_sum) * p;
            }
            else {
                long t = N / d;   
                l_cnt[i] = l_cnt[i] - s_cnt[t] + p_cnt;
                l_sum[i] = l_sum[i] - (s_sum[t] - p_sum) * p;
            }
        }

        if (q <= v) {
            for (long i = q; i < finish; i += p*interval){
                used[i] = true;
            }
        }

        for (long i = v; i >= q - 1; i--) {
            long t = i / p;
            s_cnt[i] = s_cnt[i] - s_cnt[t] + p_cnt;
            s_sum[i] = s_sum[i] - (s_sum[t] - p_sum) * p;
        }
    }
    return l_sum[1] + ret;
}

void main () {
    writeln(sum_min_pfactor(pow(10,12)));
}

Приведенный выше код отлично работает при работе с числами ниже 10 ^ 9. Однако после этого он начинает выдавать неверные значения и вылетает с ошибкой памяти при попытке вычислить ответ для 10^9. Я использую библиотеку BigInt, но я предполагаю, что одна из переменных не объявлена, поскольку BigInts искажает мои результаты. Я также предполагаю, что ошибка памяти вызвана размером динамических массивов, но я не могу понять, как решить эту конкретную проблему.


person Nicolás Siplis    schedule 12.07.2015    source источник
comment
Скомпилируйте с параметром -g, и он должен сказать вам, где именно возникает исключение, если вы еще этого не знаете.   -  person Bauss    schedule 13.07.2015
comment
Вы компилируете как 32-битную или 64-битную? Если он 32-битный, у вас меньше доступной памяти, и сборщик мусора с большей вероятностью случайно закрепит большие массивы и не освободит их (с большим массивом на 32-битном уровне вероятность того, что ложный указатель укажет на него, несколько высока). , и тогда сборщик мусора решит, что он все еще используется, и поэтому не освободит его)   -  person Adam D. Ruppe    schedule 13.07.2015
comment
Пробовал компилировать с флагом -g и -m64, но ничего не изменилось. Вывод не сказал мне, где происходит исключение, но я знаю, что это происходит при объявлении векторов BigInt.   -  person Nicolás Siplis    schedule 14.07.2015


Ответы (1)


Ответ — молчаливое целочисленное переполнение в функции std.math.pow().

Результат

writefln("%d", pow(10, 12));
writefln("%d", pow(10, 12L));

is

-727379968
1000000000000

Теперь sqrt(-727379968) это -nan. Приведение к целому числу дает int.min, что составляет около -2 ГиБ. Свойство length массивов не имеет знака. Поэтому каждый массив имеет размер type.sizeof * 2 ГиБ, что объясняет ошибку нехватки памяти.

Решение: добавьте суффикс L к одному или обоим числам, например

writeln(sum_min_pfactor(pow(10L,9L)));
person Kai Nacke    schedule 14.07.2015
comment
Хотя это работает для 10 ^ 9, оно дает неверные значения для 10 ^ 10 и выше. 10 ^ 10 должно быть 2220827932427240957, а D возвращает 2244705520836203068 (странно, поскольку на самом деле это более высокое значение, чем правильный ответ, поэтому я не уверен, что на этот раз это проблема переполнения). - person Nicolás Siplis; 16.07.2015
comment
Я не смотрел на ваш расчет. Я хочу сказать, что pow(int,int) возвращает неправильные значения, начиная с 10 ^ 10. При использовании pow(long,long) ошибка OutOfMemoryError должна исчезнуть. - person Kai Nacke; 16.07.2015
comment
По крайней мере, начиная с 10 ^ 14, ваш расчет также страдает от целочисленного переполнения: cast(int)(N) усекает некоторые биты из N. - person Kai Nacke; 16.07.2015
comment
Но ошибка в значениях бывает еще раньше. Я уже настроил pow на использование длинных значений, но я не знаю, что еще может быть их причиной. - person Nicolás Siplis; 16.07.2015
comment
Измените тип параметра с f(int) на f(long) и удалите все приведения (int). Тогда вы получите правильный ответ для 10^10, если начнете с pow(10,10L). - person Kai Nacke; 16.07.2015
comment
Отлично, теперь работает! Это намного медленнее, чем я думал, тем более что версия Nim (которая использует неоптимизированную 128-битную библиотеку) вычисляет 10^12 за 6 секунд. Это придется сделать, я думаю. - person Nicolás Siplis; 16.07.2015