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

Question

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 испортил мои результаты. Я также предполагаю, что ошибка памяти вызвана размером динамических массивов, но я не могу понять, как решить эту конкретную проблему.

Answer 1

Ответ - это бесшумное целочисленное переполнение в функции std.math.pow().

Выход

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

является

-727379968 
1000000000000 

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

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

writeln(sum_min_pfactor(pow(10L,9L)));