mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Fast way to square??? (https://www.mersenneforum.org/showthread.php?t=2545)

 maheshexp 2004-05-28 16:26

Fast way to square???

can any one help me to find out wheather it multiples faster to get the "square of a number i.e x^2 "or not. if you have better solution , could u please give me.

y(1) = 1;
y(n) = y(n-1) + ( 1 + 2* (n-1)), n > 1

eg: to find 4^2
y(1) = 1
y(2) = y(1) + (1 + 2*(1)) => 4
y(3) = y(2) + (1 + 2*(2)) => 9
y(4) = y(3) + (1 + 2*(3)) => 16

[B]A CPP Program....[/B]

[CODE]
void test2() {
long long max = 60000;
long long y = 1;
time_t t1, t2;

time(&t1);
for (long long j = 0; j < max / 3; j++)
for (long long i = 1; i <= max; i++) {
y = i * i;
}
time(&t2);
cout<<"muls:\n\t"<<"t1:" << t1 << "\n\tt2:" <<t2 <<"\n"<<(t2-t1)<<endl;

time(&t1);
for (long long j = 0; j < max / 3; j++)
for (long long i = 2; i <= max; i++) {
y = y + (1 + (i << 1));
}
time(&t2);
cout<<"muls:\n\t"<<"t1:" << t1 << "\n\tt2:" <<t2 <<"\n"<<(t2-t1)<<endl;
}
[/CODE]

[B]Output of CPP Program:[/B]

[CODE]muls:
t1:1080490498
t2:1080490523
25 s
muls:
t1:1080490523
t2:1080490537
14 s[/CODE]

A java Program...
[CODE] private static void test1() {
long max = 60000;
long y = 1;
long t1, t2;

t1 = System.currentTimeMillis();
for (int j = 0; j < max / 3; j++)
for (int i = 1; i <= max; i++) {
y = i * i;
}
t2 = System.currentTimeMillis();
System.out.println("muls:" + (t2 - t1));

t1 = System.currentTimeMillis();
for (int j = 0; j < max / 3; j++)
for (int i = 2; i <= max; i++) {
y = y + (1 + (i << 1));
}
t2 = System.currentTimeMillis();
System.out.println("mul:" + (t2 - t1));
}
[/CODE]

[B]Output of Java Program....[/B]
[CODE]muls:10031 ms
mul:5906 ms[/CODE]

 dave_dm 2004-05-28 16:58

The algorithm you've given is probably close to optimal for computing the square of [I]all[/I] integers 1 <= x <= max.

However, if you only want the square of only one number then straightforward multiplication is [I]much[/I] quicker. For the range 1 <= x <= 60000, there is no quicker way to square a number than just "y = x * x;"

For larger numbers whose squares don't fit in a word, there are more efficient algorithms. A description of many of them is given on [URL=http://careybloodworth.tripod.com/]Carey Bloodworth's page[/URL]

 maheshexp 2004-05-29 01:54

thanks friend...what u say is right...

does any thing could be done faster using the binary techniques

 All times are UTC. The time now is 06:59.