mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-05-28, 16:26   #1
maheshexp
 
May 2004

52 Posts
Lightbulb 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

A CPP Program....

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;
}
Output of CPP Program:

Code:
muls:
        t1:1080490498
        t2:1080490523
25 s
muls:
        t1:1080490523
        t2:1080490537
14 s
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));
	}
Output of Java Program....
Code:
muls:10031 ms
mul:5906 ms
maheshexp is offline   Reply With Quote
Old 2004-05-28, 16:58   #2
dave_dm
 
May 2004

24×5 Posts
Default

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

However, if you only want the square of only one number then straightforward multiplication is much 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 Carey Bloodworth's page
dave_dm is offline   Reply With Quote
Old 2004-05-29, 01:54   #3
maheshexp
 
May 2004

52 Posts
Default

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

does any thing could be done faster using the binary techniques
maheshexp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Do normal adults give themselves an allowance? (...to fast or not to fast - there is no question!) jasong jasong 35 2016-12-11 00:57
Square root of 3 Damian Math 3 2010-01-01 01:56
red square Fusion_power Puzzles 14 2008-04-25 11:37
Find a Square davar55 Puzzles 34 2007-06-12 14:17
How often is 2^p-1 square-free Zeta-Flux Math 16 2005-12-14 06:55

All times are UTC. The time now is 03:36.

Tue Jul 14 03:36:40 UTC 2020 up 111 days, 1:09, 0 users, load averages: 1.58, 1.78, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.