«

doriangray <> writes:

> superpollo wrote:
>> ok, the problem is:
>>
>> https://www.spoj.pl/problems/PRIME1/
>>
>> so i submitted this (C99) code:
> [...]
>
> A quick hint (modified from wikipedia):
>
> #include <stdio.h>
> #include <stdbool.h>
> #include <math.h>
>
> bool Prime(unsigned long * n) {
> for(unsigned long b = 2; b <= (unsigned long)trunc(sqrt(*n)); b++)

Given that *n is unsigned, neither the trunc() call nor the cast do much
good. There's nothing wrong with them, but extra code like this makes
your readers wonder what you thought was happening.

> if((*n) % b == 0) {
> return false;
> }
> return true;
> }

The problem in question requires the correct answer for 1 even though
your driver program does not.

I, too, am puzzled by the use of a pointer. It reminds me of Very Old C
when nothing bigger than an int could be passed or returned from a
function (the reason the time function takes a pointer even though, now,
the type is time_t *).

<snip>
--
Ben.

On 10/20/10 11:23 AM, doriangray wrote:
> Ben Bacarisse wrote:
>
>> I, too, am puzzled by the use of a pointer. It reminds me of Very Old C
>> when nothing bigger than an int could be passed or returned from a
>> function (the reason the time function takes a pointer even though, now,
>> the type is time_t *).
>
> Point taken. At the same time I don't see a reason to make a local copy
> of the argument passed by the caller, if that was not intended.

So you prefer to make a local copy of its address?

--
Ian Collins

On 10/20/10 11:42 AM, doriangray wrote:
> Ian Collins wrote:
>> On 10/20/10 11:23 AM, doriangray wrote:
>>> Ben Bacarisse wrote:
>>>
>>>> I, too, am puzzled by the use of a pointer. It reminds me of Very Old C
>>>> when nothing bigger than an int could be passed or returned from a
>>>> function (the reason the time function takes a pointer even though,
>>>> now,
>>>> the type is time_t *).
>>>
>>> Point taken. At the same time I don't see a reason to make a local copy
>>> of the argument passed by the caller, if that was not intended.
>>
>> So you prefer to make a local copy of its address?
>
> No i didn't say that i prefer to make a copy of the address, i just
> can't see a reason to prefer one over the other. Of course i could be
> wrong, and if i am, give me a reason to justify the choice of one
> between the two options.

Given

bool Prime(unsigned long* );

many programmers will assume that the function is going to change the
the argument passed by the caller because that's idiomatic usage.

While

bool Prime( const unsigned long* );

makes it clear the value will not change, but many programmers will
assume the parameter to be an array of unsigned long.

bool Prime( unsigned long );

is unambiguous.

--
Ian Collins

doriangray <> writes:

> Ben Bacarisse wrote:
>> doriangray<> writes:
> [...]
>>> #include<stdio.h>
>>> #include<stdbool.h>
>>> #include<math.h>
>>>
>>> bool Prime(unsigned long * n) {
>>> for(unsigned long b = 2; b<= (unsigned long)trunc(sqrt(*n)); b++)
>>
>> Given that *n is unsigned, neither the trunc() call nor the cast do much
>> good. There's nothing wrong with them, but extra code like this makes
>> your readers wonder what you thought was happening.
>
> Why extra code...I am using the standard library.

I know, I just meant what advantage does the trunc call provide. I
don't think it makes any difference here.

I spoke too soon about the cast. It may well do some good in that

b <= (unsigned long)sqrt(*n)

might be faster than

b <= sqtr(*n)

but I could not see much difference on my machine (which would have
surprised me were it not that I've stopped thinking I have any intuition
about what's fast and what's not on modern hardware!).

<snip>
--
Ben.

On 10/20/10 12:47 PM, Ben Bacarisse wrote:
> doriangray<> writes:
>
>> Ben Bacarisse wrote:
>>> doriangray<> writes:
>> [...]
>>>> #include<stdio.h>
>>>> #include<stdbool.h>
>>>> #include<math.h>
>>>>
>>>> bool Prime(unsigned long * n) {
>>>> for(unsigned long b = 2; b<= (unsigned long)trunc(sqrt(*n)); b++)
>>>
>>> Given that *n is unsigned, neither the trunc() call nor the cast do much
>>> good. There's nothing wrong with them, but extra code like this makes
>>> your readers wonder what you thought was happening.
>>
>> Why extra code...I am using the standard library.
>
> I know, I just meant what advantage does the trunc call provide. I
> don't think it makes any difference here.
>
> I spoke too soon about the cast. It may well do some good in that
>
> b<= (unsigned long)sqrt(*n)
>
> might be faster than
>
> b<= sqtr(*n)

Why?

> but I could not see much difference on my machine (which would have
> surprised me were it not that I've stopped thinking I have any intuition
> about what's fast and what's not on modern hardware!).



--
Ian Collins

Ian Collins <ian-> writes:

> On 10/20/10 12:47 PM, Ben Bacarisse wrote:
>> doriangray<> writes:
>>
>>> Ben Bacarisse wrote:
>>>> doriangray<> writes:
>>> [...]
>>>>> #include<stdio.h>
>>>>> #include<stdbool.h>
>>>>> #include<math.h>
>>>>>
>>>>> bool Prime(unsigned long * n) {
>>>>> for(unsigned long b = 2; b<= (unsigned long)trunc(sqrt(*n)); b++)
>>>>
>>>> Given that *n is unsigned, neither the trunc() call nor the cast do much
>>>> good. There's nothing wrong with them, but extra code like this makes
>>>> your readers wonder what you thought was happening.
>>>
>>> Why extra code...I am using the standard library.
>>
>> I know, I just meant what advantage does the trunc call provide. I
>> don't think it makes any difference here.
>>
>> I spoke too soon about the cast. It may well do some good in that
>>
>> b<= (unsigned long)sqrt(*n)
>>
>> might be faster than
>>
>> b<= sqtr(*n)
>
> Why?

Typos aside (sqtr should have been sqrt) because a double comparison
(which involves converting b) might be slower than an unsigned long
comparison. Another answer could be "why not?" because it could go
either way. The main point is that the cast is not redundant (the two
examples are different) but it's anyone's guess if the cast is doing any
good.

<snip>
--
Ben.

superpollo <> writes:
> Ben Bacarisse ha scritto:
[...]
>> I spoke too soon about the cast. It may well do some good in that
>>
>> b <= (unsigned long)sqrt(*n)
>>
>> might be faster than
>>
>> b <= sqtr(*n)
>>
>
> maybe b*b <= *n could be even faster...

As long as b*b doesn't overflow.

--
Keith Thompson (The_Other_Keith) kst- <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

In article <M_GdnQ_nKqkQECPRnZ2dnUVZ8n->,
says...
>
> superpollo wrote:
> > Ben Bacarisse ha scritto:
> [...]
> >> I spoke too soon about the cast. It may well do some good in that
> >>
> >> b <= (unsigned long)sqrt(*n)
> >>
> >> might be faster than
> >>
> >> b <= sqtr(*n)
> >>
> >
> > maybe b*b <= *n could be even faster...
>
> Be aware that if (*n > 4294836225), once b reaches the value of
> 65535, the next iteration will assign b the number 65536, but
> 65536 * 65536 == 4294967296. So, if ULONG_MAX == 4294967295, as it
> is on most 32bit architectures, the product (b * b) overflows. That
> means that (b * b) yields 0, because the exact arithmetic result of
> (b * b) will be reduced modulo ULONG_MAX + 1. Therefore, the loop
> becomes infinite.

The problem as stated at the site is preposterous.

For an integer to be useful for cryptographic purposes, it should
{generally} be hundreds of bits in length.

Crypto systems typically use libraries like MPIR for large integers.
Perusal of these openssl archives (for instance) will show that tiny, 32
bit integers are not useful for crypto purposes (other than things like
a loop counter in the source code):
http://www.openssl.org/source/

Hence, as a lower bound for primes, even something like this is much too
small for cryptographic purposes:
5773711106117539064689094729932307

Most of the time type unsigned long long is not large enough. There are
exceptions, of course (e.g. someone might get by with even a 64 bit
message digest like UMAC if the information transmitted is not of great
value).

In article <rKmdndhlO-fdAiPRnZ2dnUVZ7t->,
says...
>
> Dann Corbit wrote:
> [...]
> > The problem as stated at the site is preposterous.
> >
> > For an integer to be useful for cryptographic purposes, it should
> > {generally} be hundreds of bits in length.
> >
> > Crypto systems typically use libraries like MPIR for large integers.
> > Perusal of these openssl archives (for instance) will show that tiny, 32
> > bit integers are not useful for crypto purposes (other than things like
> > a loop counter in the source code):
> > http://www.openssl.org/source/
> >
> > Hence, as a lower bound for primes, even something like this is much too
> > small for cryptographic purposes:
> > 5773711106117539064689094729932307
> >
> > Most of the time type unsigned long long is not large enough. There are
> > exceptions, of course (e.g. someone might get by with even a 64 bit
> > message digest like UMAC if the information transmitted is not of great
> > value).
>
> That's very interesting. Cryptography is really an "unknown land" to me.
> Could you suggest me some good readings about cryptographic algorithms
> in C ? I would also like to know how to implement such huge integer data
> type. Do they normally use assembly in order to get them?

There is a newsgroup called news:sci.crypt that is an excellent place to
learn cryptography. Beware, Robert Silverman will jump down your throat
at the first opportunity, but take your lumps because he definitely
knows what he is talking about. He's the Dan Pop of news:sci.crypt and
he's not just active, he's radioactive.

Read the crypto FAQ before posting, of course. Tom St. Denis who posts
here in c.l.c is a crypto guy.
ftp://rtfm.mit.edu/pub/usenet-by-hierarchy/sci/crypt/

Take a look at this:
http://www.cacr.math.uwaterloo.ca/hac/