Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!usc!apple!motcsd!hpda!hpcuhb!hpsqf!hpqtdla!bww
From: bww@hpqtdla.HP.COM (Brian Woodroffe)
Newsgroups: comp.lang.c
Subject: Re: Integer square root routine needed.
Message-ID: <430003@hpqtdla.HP.COM>
Date: 1 Aug 89 12:40:01 GMT
References: <7415@ecsvax.UUCP>
Organization: HP, Queensferry Telecomms (UK)
Lines: 24

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@hpsqf                 |
| Queensferry Telecomms Division |         bww%hpsqf@hplabs.hp.com   |
| South Queensferry              | UUCP:   ..!hplabs!hpqtdla!bww     |
| West Lothian                   | JANET:  bww%hpqtdla@hpl.hp.co.uk  |
| Scotland EH30 9TG.             | PHONE:  +44-31-331-7234           |
+--------------------------------+-----------------------------------+