The problem definition states that "the input values will be represented with 32-bit unsigned integers". Is it safe to assume that the output values (including the sums of primes) will also representable with 32-bit unsigned integers?
When you start adding together large 32-bit values, pretty soon you're talking 33 or 34 bits. It will impact the performance of the inner loop if those calculations must be done with 64-bit integers.
- Rick
I do NOT think it is safe to assume only 32 bit sums.
If you think that doing 64 bit additions are a performance issue, is there any thing that can be done to optimise the process? can you detect when you start to need 64 bit additions?
Lets assume worst case scenario, we'd be searching 0 up to 2^32 giving 203280221 prime numbers with a total sum of 42564973619368743 which needs about 59 bits to express. so yeah no way a 32bit variable will be sufficient.
10111101000001101100010111000001100100100000011111110000110
yeah, both duncan & dodo are right.
It it pretty obvious that input can be max value represented by 32 bit integer.
So do not assume any thing, code for all the applicable scenarios.
Still waiting for an official response from Intel... Rama?
Quoting duncanhopkins If you think that doing 64 bit additions are a performance issue...It's not the 64 bit additions. I was thinking the perfect power test can be tighter if everything is 32 bits.
- Rick
My comment still holds:
Can you detect when you can use a 32 bit algo and switch to it?
Hi,
Do not assume output to be constrained to 32-bit. Please code for generic case where the output (the sum of primes) is larger than a 32-bit integer capacity. So, you can use 64-bit type for storing the output.
Thanks
-Rama