Integer square root routine needed.

Brian Woodroffe bww at hpqtdla.HP.COM
Tue Aug 1 22:40:01 AEST 1989


The following `facts' may be of help in designing an algorithm:-
1/ A perfect square is the square of an integer.
2/ All perfect squares are the sum of a sequence of odd numbers.
3/ The sum of the sequence is the square of the length of the sequence.

eg 	n	seq(n)	sqr(n)
	2	1+3	4
	3	1+3+5	9
	4	1+3+5+7	16
etc

The proof by induction can be derived from (x+1)**2 == x**2 + 2*x + 1


An algorithm based on a binary chop should converge quickly, too!
   
+--------------------------------+-----------------------------------+
| Brian Woodroffe                | HPDESK: Brian Woodroffe/HP1400/B1 |
| Hewlett Packard Ltd            | ARPA:   bww at hpsqf                 |
| Queensferry Telecomms Division |         bww%hpsqf at hplabs.hp.com   |
| South Queensferry              | UUCP:   ..!hplabs!hpqtdla!bww     |
| West Lothian                   | JANET:  bww%hpqtdla at hpl.hp.co.uk  |
| Scotland EH30 9TG.             | PHONE:  +44-31-331-7234           |
+--------------------------------+-----------------------------------+



More information about the Comp.lang.c mailing list