Sunday, October 09, 2005
The Joy of Programming
Brahmagupta's Riddle
I recently came across ancient Indian mathematician Brahmagupta's quote "A person who can, within a year, solve x^2 - 92y^2 = 1 is a mathematician." (x square - 92 multiplied by y square = 1).
Since I am no mathematician but a programmer, I tried writing a program to find out the values for x and y.
x^2 - 92y^2 = 1
=> x^2 = 1 + 92y^2
=> x = rootof (1 + 92y^2)
So, my program can vary an integer value y and do floating point computation for the formula rootof (1 + 92y^2), and check if the result is an integer.
But later, I thought, its better to keep it as integer and compute it using two for loops to avoid floating point computation:
#include
#include
int main() {
int x, y;
for(x = 1; x <= SHRT_MAX; x++) {
for(y = 1; y <= SHRT_MAX; y++) {
if ( (x * x) == (1 + 92 * y * y)) {
printf("x = %d, y = %d", x, y);
break;
}
}
}
}
And for my surprise, it found the answer in a few seconds: it prints x = 1151, y = 120
1151 * 1151 == 1 + 92 * 120 * 120
=> 1324801 == 1 + 92 * 14400
=> 1324801 == 1 + 1324800
=> 1324801 == 1324801
Well, even now I don't understand the complexity of the original problem. Can somebody who is good in mathematics explain it to me?
I was also wondering how this program can be made more efficient.
I recently came across ancient Indian mathematician Brahmagupta's quote "A person who can, within a year, solve x^2 - 92y^2 = 1 is a mathematician." (x square - 92 multiplied by y square = 1).
Since I am no mathematician but a programmer, I tried writing a program to find out the values for x and y.
x^2 - 92y^2 = 1
=> x^2 = 1 + 92y^2
=> x = rootof (1 + 92y^2)
So, my program can vary an integer value y and do floating point computation for the formula rootof (1 + 92y^2), and check if the result is an integer.
But later, I thought, its better to keep it as integer and compute it using two for loops to avoid floating point computation:
#include
#include
int main() {
int x, y;
for(x = 1; x <= SHRT_MAX; x++) {
for(y = 1; y <= SHRT_MAX; y++) {
if ( (x * x) == (1 + 92 * y * y)) {
printf("x = %d, y = %d", x, y);
break;
}
}
}
}
And for my surprise, it found the answer in a few seconds: it prints x = 1151, y = 120
1151 * 1151 == 1 + 92 * 120 * 120
=> 1324801 == 1 + 92 * 14400
=> 1324801 == 1 + 1324800
=> 1324801 == 1324801
Well, even now I don't understand the complexity of the original problem. Can somebody who is good in mathematics explain it to me?
I was also wondering how this program can be made more efficient.
# posted by Ganesh @ 10:48 PM 
Comments:
<< Home
Equations of the form
x^2 - n*y^2 = 1 (where n is a non-square integer, x and y are natural numbers)
are called Pell's equation. This problem was of considerable importance and interest during the 7th century. And that was when Brahmagupta gave the smallest solution to the problem x^2-92y^2=1 as 1151 and 120.
Mathematicians worked on a method to solve all such equations, and Bhaskara came out with a complete generic solution for the Pell's equation in the 17th century.
Brahmagupta might have wanted mathematicians to solve the equation within a year because of its complexity, considering the expertise in this field at that point of time. Just a guess!
Now that you have programatically solved Brahmagupta's riddle, try solving this one:
61x^2 + 1 = y^2
for integers x and y!
Keep writing, your posts are good.
Cheers,
Krishna.
Post a Comment
x^2 - n*y^2 = 1 (where n is a non-square integer, x and y are natural numbers)
are called Pell's equation. This problem was of considerable importance and interest during the 7th century. And that was when Brahmagupta gave the smallest solution to the problem x^2-92y^2=1 as 1151 and 120.
Mathematicians worked on a method to solve all such equations, and Bhaskara came out with a complete generic solution for the Pell's equation in the 17th century.
Brahmagupta might have wanted mathematicians to solve the equation within a year because of its complexity, considering the expertise in this field at that point of time. Just a guess!
Now that you have programatically solved Brahmagupta's riddle, try solving this one:
61x^2 + 1 = y^2
for integers x and y!
Keep writing, your posts are good.
Cheers,
Krishna.
<< Home
