GNAT Big_numbers "wedging" in a new RC Task and brute-force algorithm (VERY slow)

Hi;

I am stubbornly running an Ada program using GNAT Big_Numbers with (obviously) a brute-force algorithm that has hidious performance. I don’t think I can blame this glacial slowness entirely on the Big_Number “wedging”; it must be a major flaw in my algorthm. It has been running for almost 38 hours. I suspect that it may take a couple more days. It is almost half-way complete (if the results are correct). The other entries that have tried the stretch goal are consuming 10-90 seconds to find 1,525,141 results. I have 532,952 results so far (assuming that the results are correct). This is the “stretch” goal. I have already posted an Ada solution for this task which is NOT the stretch goal.

pragma Ada_2022;
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;
with Ada.Numerics.Big_Numbers.Big_Integers; use Ada.Numerics.Big_Numbers.Big_Integers;
with Ada.Real_Time; use Ada.Real_Time;

procedure Primes_Whose_Sum_of_Digits_is_25 is

  function Is_Prime (N : in Big_Positive) return Boolean is
    Big_0 : Big_Integer := To_Big_Integer (0);
    Big_2 : Big_Positive := To_Big_Integer (2);
    Big_3 : Big_Positive := To_Big_Integer (3);
    Temp : Big_Integer := To_Big_Integer (5);
  begin
    if N < Big_2 then
      return False;
    end if;
    if N mod Big_2 = 0 then
      return N = Big_2;
    end if;
    if N mod Big_3 = 0 then
      return N = Big_3;
    end if;
    while Temp * Temp <= N loop
      if N mod Temp = Big_0 then
        return False;
      end if;
      Temp := Temp + Big_2;
      if N mod Temp = Big_0 then
        return False;
      end if;
    end loop;
    return True;
  end Is_Prime;

  function Is_Sum_of_Digits_Equal_to_25 (N : Big_Positive) return Boolean is
    Big_0 : Big_Integer := To_Big_Integer (0);
    Big_10 : Big_Integer := To_Big_Integer (10);
    Local_N : Big_Integer := N;
    Sum : Natural := 0;
    Current_Remainder : Natural;
  begin
    while Local_N > Big_0 loop
      Current_Remainder := To_Integer (Local_N mod Big_10);
      if Current_Remainder = 0 then
        return False;
      end if;
      Sum := Sum + Current_Remainder;
      Local_N := Local_N / Big_10;
    end loop;
  return Sum = 25;
  end Is_Sum_of_Digits_Equal_to_25;

  Prime_Count : Natural := 0;
-- Show the count of all such primes that do not contain any zeroes in the range:  
-- (997   ≤   n   ≤   1,111,111,111,111,111,111,111,111).
  Big_2 : Big_Positive := To_Big_Integer (2);
  I : Big_Positive := To_Big_Integer (997);
  Maximum_Prime_Candidate : Big_Positive := From_String ("1111111111111111111111111");  
  Start_Time, Stop_Time : Time;
  Elapsed_Time          : Time_Span;

begin
  Start_Time := Clock;
  loop
    if Is_Sum_of_Digits_Equal_to_25 (I) then
      if (Is_Prime (I)) then
        Prime_Count := Prime_Count + 1;
        Put ("DEBUG: I is ");
        Put_Line (To_String (Arg => I));
        if Prime_Count mod 10_000 = 0 then
          Put (".");
        end if;
      end if;
    end if;
    I := I + Big_2;
    exit when I >= Maximum_Prime_Candidate;
  end loop;
  New_Line;
  Put ("There are ");
  Put (Prime_Count, 0);
  Put (" primes less than ");
  Put (To_String (Arg => Maximum_Prime_Candidate));
  Put_Line (" whose sum of digits is 25 and does not contain a zero.");
  Stop_Time := Clock;
  Elapsed_Time := Stop_Time - Start_Time;
  Put_Line ("Elapsed time: " & Duration'Image (To_Duration (Elapsed_Time)) & " seconds");
  New_Line;
end Primes_Whose_Sum_of_Digits_is_25;

My plan was to make sure that the results were correct and then try to optimize by tasking (take, perhaps, 1000 per task, how many concurrent tasks (?) and how to sum up the results from each task). Reading up on tasking now; as I haven’t used Ada tasking since when Ada 95 was very new…

Of course, there MUST be a permutation or something that is in the pattern of results that could/should reduce the number of calculations…

Thanks for any additional insights…

Retired Build Engineer

Your Is_Prime function could be improved – WikiPedia (Primality test - Wikipedia) suggests the following:

One way to speed up these methods (and all the others mentioned below) is to pre-compute and store a list of all primes up to a certain bound, such as all primes up to 200. (Such a list can be computed with the Sieve of Eratosthenes or by an algorithm that tests each incremental {isplaystyle m} against all known primes {isplaystyle eq {qrt {m}}}). Then, before testing {isplaystyle n} for primality with a large-scale method {isplaystyle n} can first be checked for divisibility by any prime from the list. If it is divisible by any of those numbers then it is composite, and any further tests can be skipped.

You also might want to pre-compute (using regular integers) the sum of digits, of say, every number from 0 to 999_999, and then create a 26-slot table (0…25) where each slot points to the list of numbers with that sum (you can ignore those with sums > 25 of course). With such a 26-slot table, you can efficiently produce progressively longer numbers by first doing a primality test on all 6-digit numbers that sum to 25, then all 12-digit numbers that sum to 25, then all 18-digit numbers, and so on. The summing of digits can all be done with “regular” integers, and you only need to start using “big” numbers once you get past 2**63 (i.e., 24-digit numbers).

1 Like