A Simple C Code to Discuss

E

ethanmys

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: (e-mail address removed)
*/
#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();
}
 
R

Richard Heathfield

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;
}
 
S

Simon Biber

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.

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.
 
R

Richard Heathfield

Simon Biber said:
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.
 
E

ethanmys

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 ).
 
R

Randy Howard

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. :)
 
R

Rouben Rostamian

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.
 
E

ethanmys

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top