A Simple C Code to Discuss

Discussion in 'C Programming' started by ethanmys, Oct 30, 2005.

  1. ethanmys

    ethanmys Guest

    hello everyone. hours ago i found a topic about solving the problem:
    find out 2 int between certain rang, say 1---100, both the 2 int's sum
    and minus should be a int's square.
    i write this piece of code and i want you to give some advice. can the
    code run quicker? i think there must exist many quicker ones.
    /*
    this doucument and source code belong to Ethan Mys, oct 30, 2005.
    any modification to improve the source code is welcome.
    you can also spit at this piece of "shit", because i am a masochist.
    E-Mail:
    */
    #include<stdio.h>

    int main()
    {
    int k=0;
    int tb[][6]={{1,9,25,81,121,169},\
    {4,16,36,64,100,144,}};
    for(k=1;k<=13;k++)
    {
    int k2=k*k;
    int temp=0;int temp2=0;

    while((temp2=tb[k%2?0:1][temp])<k2)
    {
    int res[10];
    res[temp]=(k2+temp2)/2;
    printf("%3d and %3d ",res[temp],k2-res[temp]);
    temp++;
    }
    printf("\n");
    }
    getchar();
    }
     
    ethanmys, Oct 30, 2005
    #1
    1. Advertising

  2. ethanmys said:

    > hello everyone. hours ago i found a topic about solving the problem:
    > find out 2 int between certain rang, say 1---100, both the 2 int's sum
    > and minus should be a int's square.
    > i write this piece of code and i want you to give some advice. can the
    > code run quicker? i think there must exist many quicker ones.


    Here's a much quicker version:

    #include <stdio.h>

    int main(void)
    {
    puts("The pair (384, 400) is the smallest positive integer solution.");
    return 0;
    }

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Oct 30, 2005
    #2
    1. Advertising

  3. ethanmys

    Simon Biber Guest

    ethanmys wrote:
    > hello everyone. hours ago i found a topic about solving the problem:
    > find out 2 int between certain rang, say 1---100, both the 2 int's sum
    > and minus should be a int's square.


    If I understand you correctly, this is the problem: Find two integers
    within the given range, say 1 to 100, where the sum of the two is the
    square of an integer, and the difference of the two is also the square
    of an integer.

    Mathematically,
    (x + y) == a * a && (x - y) == b * b

    Where 'x' and 'y' are the integers to find, and 'a' and 'b' are the
    square roots of the sum and difference respectively.

    I fed this into Mathematica:

    Reduce[(x + y) == a * a && (x - y) == b * b, {x, y}, Integers]

    And got the result:

    2 2
    a + b 2
    (a | b | x | y) \[Element] Integers && x == ------- && y == a - x
    2

    I then wrote a program to step over possible values of a and b,
    calculate the x and y values, and check if they were within a given range.

    #include <stdio.h>

    int main(void)
    {
    int a, b, n = 0;
    int min = 1;
    int max = 100;

    for(a = 0; a < 100; a++)
    {
    for(b = 0; b < 100; b++)
    {
    int ssq = a * a + b * b;
    if(ssq % 2 == 0)
    {
    int x = ssq / 2;
    int y = a * a - x;
    if(min <= x && x <= max && min <= y && y <= max)
    {
    printf("%d,%d\t", x,y);
    n++;
    }
    }
    }
    if(n)
    {
    printf("\n");
    n = 0;
    }
    }
    return 0;
    }

    The program gives the following results:

    2,2
    5,4
    8,8 10,6
    13,12 17,8
    18,18 20,16 26,10
    25,24 29,20 37,12
    32,32 34,30 40,24 50,14
    41,40 45,36 53,28 65,16
    50,50 52,48 58,42 68,32 82,18
    61,60 65,56 73,48 85,36
    72,72 74,70 80,64 90,54
    85,84 89,80 97,72
    98,98 100,96

    Each of these results seem to be correct according to my understanding
    of the problem. The sum of each pair is a square number, and the
    difference of each pair is also a square number.

    --
    Simon.
     
    Simon Biber, Oct 30, 2005
    #3
  4. Simon Biber said:

    > ethanmys wrote:
    >> hello everyone. hours ago i found a topic about solving the problem:
    >> find out 2 int between certain rang, say 1---100, both the 2 int's sum
    >> and minus should be a int's square.

    >
    > If I understand you correctly,


    I didn't, alas. I don't know why but I read more squares into the problem
    than was warranted by the question. I have cancelled my article, but of
    course many news servers won't honour that.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Oct 30, 2005
    #4
  5. ethanmys

    ethanmys Guest

    your code is clear. but i think it will cost O(n^2). what i think is:
    there shoud be a O(1) solution to this problem ( don't consider the
    input ).
     
    ethanmys, Oct 30, 2005
    #5
  6. ethanmys

    Randy Howard Guest

    ethanmys wrote
    (in article
    <>):

    > your code is clear. but i think it will cost O(n^2). what i think is:
    > there shoud be a O(1) solution to this problem ( don't consider the
    > input ).


    Sure, a pre-computed lookup table. :)


    --
    Randy Howard (2reply remove FOOBAR)
    "The power of accurate observation is called cynicism by those
    who have not got it." - George Bernard Shaw
     
    Randy Howard, Oct 30, 2005
    #6
  7. In article <>,
    ethanmys <> wrote:
    >hello everyone. hours ago i found a topic about solving the problem:
    >find out 2 int between certain rang, say 1---100, both the 2 int's sum
    >and minus should be a int's square. i write this piece of code and i
    >want you to give some advice. can the code run quicker? i think there
    >must exist many quicker ones.


    Let me translate. You are stating:
    Problem 1:
    Find all integers x and y between 1 and N such that
    x+y and x-y are squares.

    However your program does not solve this. It solves the following
    problem instead:
    Problem 2:
    Find all integers x and y such that x+y and x-y are squares
    and x+y is at most N.

    Aside: Your table of squares is missing 7^2 = 49:

    > int tb[][6]={{1,9,25,81,121,169},\
    > {4,16,36,64,100,144,}};


    To solve the problems stated above, it's best to do a little
    math before writing a program. You are looking for x and
    y such that:

    x + y = a^2, x - y = b^2.

    By solving this system of two equations in the two unknowns
    x, and y we get:

    x = (a^2 + b^2)/2, y = (a^2 - b^2)/2.

    We observe that a and b have to be both even or both odd,
    otherwise the fractions shown above will not yield integers.

    In view of this, we can print the numbers you are looking
    for as follows:

    int i, j, I, J, N;

    for (i=1; I=i*i, i<=N; i++)
    for (j=i+2; J=j*j, j<=N; j+=2)
    printf("(%d, %d)\n", (J+I)/2, (J-I)/2);

    This solves Problem 1. To solve Problem 2, change the
    stopping criteria i<=N and j<=N to I<=N and J<=N.

    --
    Rouben Rostamian
     
    Rouben Rostamian, Oct 30, 2005
    #7
  8. ethanmys

    ethanmys Guest

    Yes. Your code is concise and is apt at solving both problem. It
    inspires me a lot and really should be included in a C textbook.:)
    Thanks
     
    ethanmys, Oct 31, 2005
    #8
    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. Raj
    Replies:
    1
    Views:
    406
    Adam Maass
    Aug 25, 2003
  2. Ken North
    Replies:
    0
    Views:
    324
    Ken North
    Feb 13, 2004
  3. Jeff Gaynor
    Replies:
    0
    Views:
    348
    Jeff Gaynor
    May 19, 2004
  4. David Ascher
    Replies:
    0
    Views:
    247
    David Ascher
    Jun 2, 2005
  5. G Patel
    Replies:
    6
    Views:
    325
    Gordon Burditt
    Aug 19, 2006
Loading...

Share This Page