Re: PRIME1 (SPOJ)

Discussion in 'C Programming' started by Ben Bacarisse, Oct 19, 2010.

  1. 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.
    Ben Bacarisse, Oct 19, 2010
    #1
    1. Advertising

  2. Ben Bacarisse

    Ian Collins Guest

    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
    Ian Collins, Oct 19, 2010
    #2
    1. Advertising

  3. Ben Bacarisse

    Ian Collins Guest

    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
    Ian Collins, Oct 20, 2010
    #3
  4. 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.
    Ben Bacarisse, Oct 20, 2010
    #4
  5. Ben Bacarisse

    Ian Collins Guest

    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, Oct 20, 2010
    #5
  6. Ian Collins <> 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.
    Ben Bacarisse, Oct 20, 2010
    #6
  7. 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) <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"
    Keith Thompson, Oct 20, 2010
    #7
  8. Ben Bacarisse

    Dann Corbit Guest

    In article <>,
    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).
    Dann Corbit, Oct 20, 2010
    #8
  9. Ben Bacarisse

    Dann Corbit Guest

    In article <>,
    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/
    Dann Corbit, Oct 20, 2010
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Shriphani
    Replies:
    2
    Views:
    549
    Ian Kelly
    Jun 1, 2008
  2. bert

    Re: PRIME1 (SPOJ)

    bert, Oct 18, 2010, in forum: C Programming
    Replies:
    4
    Views:
    441
    Michael Foukarakis
    Oct 20, 2010
  3. Ben Bacarisse

    Re: PRIME1 (SPOJ)

    Ben Bacarisse, Oct 19, 2010, in forum: C Programming
    Replies:
    2
    Views:
    426
    Ben Bacarisse
    Oct 19, 2010
  4. BartC

    Re: PRIME1 (SPOJ)

    BartC, Oct 19, 2010, in forum: C Programming
    Replies:
    5
    Views:
    508
    BartC
    Oct 19, 2010
  5. Dann Corbit

    Re: PRIME1 (SPOJ)

    Dann Corbit, Oct 20, 2010, in forum: C Programming
    Replies:
    2
    Views:
    919
    Dann Corbit
    Oct 20, 2010
Loading...

Share This Page