I have a Is_Prime function which apparently I have not written correctly (it seems to work fine previously) because it fails (overflow exception generated) far too early, like it is not even beyond Ada Integer upper limits.
I’d like to know what compiler options and/or GNAT tool(s) I need to enable in order to determine the statement that causes the overflow.
Here’s my function…
function Is_Prime (N : in Big_Natural) return Boolean is
Big_0 : Big_Natural := To_Big_Integer (0);
Big_2 : Big_Natural := To_Big_Integer (2);
Big_3 : Big_Natural := To_Big_Integer (3);
Big_4 : Big_Natural := To_Big_Integer (4);
Big_Temp : Big_Natural := To_Big_Integer (5);
begin
if N < Big_2 then
return False;
end if;
if N mod Big_2 = Big_0 then
return N = Big_2;
end if;
if N mod Big_3 = Big_0 then
return N = Big_3;
end if;
while Big_Temp * Big_Temp <= N loop
if N mod Big_Temp = Big_0 then
return False;
end if;
Big_Temp := Big_Temp + Big_2;
if N mod Big_Temp = Big_0 then
return False;
end if;
Big_Temp := Big_Temp + Big_4;
end loop;
return True;
end Is_Prime;
If needed, I’ll paste in the entire program.
Also, if needed, I’ll show my output…
I must be missing something very simple and obvious.
if that fails – and only if that fails – compile with -O0 -g and whip out gdb.
gdb is not the easiest tool to use (can’t have spaces between symbols in a debug condition, for example), but amazingly enough it does work with Ada. But usually a strategic use of Put_Line does the trick for me.
That aside, if you want to test for primes, wouldn’t it be better to try a Sieve of Eratosthenes? That’s another Rosetta Code task, and I’m pretty sure it’s been solved for Ada. Even if not, it’s easy to implement. (I haven’t looked at the task you’re trying, so maybe it’s not feasible in your case.)
Well, if I were to use the Sieve then I’d need to have all the prime numbers less than Integer’Last, when I only need a few of them (the first ten primes out of a list of 30 numbers). I am able to obtain the first nine, but the tenth fails…
Yeah, that was one of the dumber things I’ve ever suggested. You had, after all, already pointed out that you were working with Big_Number.
So you are working on this part?
Find and display at least the first 10 Jacobsthal primes
Glancing at the problem page, it looks as some solutions are using brain-dead primality tests, and the largest prime you need isn’t very large.
I used the same Is_Prime function but with a Natural as the incoming parameter (not Big_Natural) as a second version (different parameter signature) and it works! This is bizarre.
which may be overkill in your case because it is most useful if an error is caught and re-raised, but it should give you a stack trace showing the line where the error was raised.
Your Is_Prime function seems fine, I can easily calculate the first 12 Jacobsthal primes with it. There must be something going on in other parts of your code.
I came across this (seemingly very clever) prime number type definition working on some other Rosetta code tasks involving primes. It seems to work just fine, not sure at all about efficiency and all that:
subtype Prime is Positive range 2 .. Positive'Last with
Dynamic_Predicate =>
(for all I in 2 .. (Prime / 2) => (Prime mod I) /= 0);
You then check if a number is prime by doing:
if Candidate in Prime then
<whatever action you need to do>:
end if;
I hope this helps…
(Edit) Doh! It can’t be used with Big Numbers because they’re defined with dynamic predicates themselves, so using them for the ranges is not valid…
Your predicate doesn’t have to go all the way to Prime / 2; it should be able to stop at sqrt (Prime), though type conversions will be necessary.
Does Dynamic_Predicate cache its results, or at least some of them? I’d hate to think that you’d be re-computing over and over whether (e.g.) 101 is prime.
I would be surprised if the RM specified that at all (I didn’t look, so just a guess). It usually leaves a lot of the implementation details to the compiler. And since it is a dynamic predicate (not static) there’s even less chance of it being the case. That said, I would guess that GNAT is capable of optimizing it as cached if multiple uses of the same number are referenced in close proximity. At the end of the day it would probably depend on the compiler/processor how the caching is done.
You do have the option of precaching common values at runtime by declaring constants for them:
Prime_101 : constant Prime := 101;
You could also do a constant hashed set of the range of all of the common prime numbers you might usually encounter to reduce computation. if the number you are interested in is within the bounds of that range, see if it is in the set (constant time calculation). If it is outside the range of common ones, then do the longer time check.
Waaaaait a second I agree that GDB is not the easiest tool to use… but it should be the perfect tool for this issue!
In GDB one can ask it to break (catch) any failed assertion o other exception. Once that is enabled, you just have to run the program and… voilà! You are in the exact line that caused the issue You now just have to poke the values to see which is the one causing the issue. Thanks to this method I found an arithmetic issue in SVD2Ada caused by an uninitialised variable. The issue happened to be that SVD2Ada had not forseen that the values it was reading from an SVD file could be reversed. It took me 15 mins to find this issue in a codebase I had never seen in my life!
I just love Ada <3
@sttaft cannot one creat a subtype and add more Dynamic_Predicate which is added to the base type?
@sttaft cannot one creat a subtype and add more Dynamic_Predicate which is added to the base type?
Yes, you can layer on additional predicates, both Static_… and Dynamic_… They are evaluated in sequence, starting from the “oldest” one to the “newest” one (see RM 3.2.4(29.2/4-29.7/4)). Depending on which predicate, if any fails, you can set up distinct Predicate_Failure actions (RM 3.2.4(31.1/4)).
And for what it is worth, Big_Integers use predicates only for defining various subranges, such as “Valid_Big_Integer” or “Big_Positive” (see RM A.5.6).
I agree that GDB is not the easiest tool to use… but it should be the perfect tool for this issue!
You now just have to poke the values to see which is the one causing the issue. Thanks to this method I found an arithmetic issue in SVD2Ada caused by an uninitialised variable. The issue happened to be that SVD2Ada had not forseen that the values it was reading from an SVD file could be reversed. It took me 15 mins to find this issue in a codebase I had never seen in my life! 