Number too big for int64

Quote:

Originally Posted by Doriän

i don't get your point. My func returns 0 if is a prime, doesn't it? isn't 0 a success return value?

It often is, but you are not indicating "success" here. You are indicating whether the number is prime or not. Either way, the function obviously "succeeds" in performing its task.

Also, when a function returns 0 as a success status, typically error conditions are represented by NEGATIVE return values, not positive ones.

None of it matters functionally -- but a function named "is_xxx" is a predicate. Inverting the return values makes absolutely no sense, because it leads to code like this:

Code:

if(!is_prime(x)) { /* That line of code reads "If not is prime..." and yet it MEANS "if prime." BAD. */ }

Quote:

Originally Posted by foxman

Also, you might want to switch this

Code:

for(i=2; i<a/2 ; i++)

for this

Code:

for(i=2; i < sqrt(a); i++)

or something like

Code:

maxUsefulTestValue = (int) sqrt(a); for(i=2; i < maxUsefulTestValue; i++)

but your compiler may have done this optimisation anyway...

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Having said this, it's definitely worthwhile, since for a near 1000000 you only have to go up to 1000, instead of 500000, for roughly a factor of 500 speedup for large a.

> I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires
> LOTS of memory).

Due to the improved asymptotic time over doing a primality test for each number separately, for calculating the sum of the first N primes, where N is sufficiently large, the sieve method should be faster even if it starts swapping and incurs a huge constant factor slowdown (I don't know how large N has to be to make up for the swap penalty). And in going up to a million, it only needs about a megabyte, at one byte per number (one can of course optimize by using one bit per number).

Quote:

Originally Posted by robatino

You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Just add 1 after taking the square root. The imprecision will never be more than 1 unit, or even close to it. And the cost of checking one extra value gets less and less important the larger the number gets.

Quote:

Originally Posted by robatino

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Having said this, it's definitely worthwhile, since for a near 1000000 you only have to go up to 1000, instead of 500000, for roughly a factor of 500 speedup for large a.

Quote:

Originally Posted by brewbuck

Just add 1 after taking the square root. The imprecision will never be more than 1 unit, or even close to it. And the cost of checking one extra value gets less and less important the larger the number gets.

Done. It is indeed several times faster (I had already tried this method some time ago, in another exercise with prime numbers, but that time it didn't work - looks like I'll have to check that one too!)

I changed the return values too - switched 0s with 1s, so that now 1=success, or better, isPrime, and 0 = !isPrime.

edit: A question related to this issue of return values. In my main, I call the function in this way:

Code:

for (i=3; i<MAX; i++) { if(i%2!=0){ if (isPrime(i)==1) { sum += i; printf("%I64d\t", sum); printf("%d\n", i); } }

If I were to call the function in this other way,

Code:

for (i=3; i<MAX; i++) { if(i%2!=0){ if (isPrime(i)) { // <-- Here's the change sum += i; printf("%I64d\t", sum); printf("%d\n", i); } }

would it consider i prime if the function were to return 1 or if the function were to return 0?

edit2: Disregard that, I tried and it works fine indeed. But how's that? I mean, does the main consider "successful" the call (thus isPrime) if the function returns the last value (

Code:

int isPrime(int a) { int i; for(i=3; i<sqrt(a)+1 ; i++) { if(a%i==0) { return(0); } } return (1); }

, so 1 here), and unsuccessful (thus !isPrime) if it return a value which isn't the last? How does it tell the difference?

> would it consider i prime if the function were to return 1 or if the function were to return 0?
When a numeric value is used in a test (such as if, for, while), anything nonzero is true, and zero is false. Conversely, the numeric value of a true statement is 1, and of a false statement is 0 (so "i = (3 > 0);" sets i to 1, and "i = (3 == 5);" sets i to 0).

I didn't know this. Thanks!

Quote:

You have to be careful since the division test has to go up to at least the EXACT square root of i. For example, 49 is composite, but only because it's divisible by 7, which is exactly the square root of 49. So you would at least have to replace "i < sqrt(a)" by "i <= sqrt(a)". I'm still not sure whether this is enough due to being unsure how the square root of an integer is calculated (for example, is sqrt(49) exactly 7, or could it be a little more or less, in which case the loop might miss the last value). You might have to do something like add a small constant like 0.5 to a before taking the square root. I don't know the most elegant way of handling this.

Yeah sorry, i didn't pay attention to that important point (adding one to the sqrt if you stay with the condition < and not <=). I should have, but since my post was more towards the use of printf and the differents types of integer, i went too fast on this particular part. :)

Quote:

Originally Posted by robatino

> I use sieve of erathostenes(sp?), which is a bit faster (but starts to fall apart after a while because it requires
> LOTS of memory).

Due to the improved asymptotic time over doing a primality test for each number separately, for calculating the sum of the first N primes, where N is sufficiently large, the sieve method should be faster even if it starts swapping and incurs a huge constant factor slowdown (I don't know how large N has to be to make up for the swap penalty). And in going up to a million, it only needs about a megabyte, at one byte per number (one can of course optimize by using one bit per number).

Yes, the problem for me is that I run out of possible swap-space long before I get to that point, since the OS I use (currently) is only 32-bit, and swap-space thus is limited to 3GB, which when used in "bitsieve" (which uses 1 bit per number, rather than a byte), it gives about 24 billion sieve-range - I haven't tried that... I have 2GB of RAM in the machine, so it's not going to be THAT bad, but it's MUCH worse than when it fits in memory completely. The worst part is actually for the small primes, because it's touching every few bytes, which means there's no gaps. Once you get somewhere large, it's not too bad, because the memory management only need to swap in/out the pages that are needed, which isn't all (but there's still some churn, because the next number is obviously not going to be touch the same multiples of 4KB).

--
Mats

Number too big for int64_t?