Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!npeer01.iad.highwinds-media.com!news.highwinds-media.com!feed-me.highwinds-media.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Helmar Wodtke Newsgroups: comp.lang.forth Subject: Re: Sum of squares Date: Wed, 28 Mar 2012 09:42:36 -0700 (PDT) Organization: http://groups.google.com Lines: 162 Message-ID: <29077647.1167.1332952956906.JavaMail.geo-discussion-forums@vbue17> References: <10851509008435@frunobulax.edu> NNTP-Posting-Host: 62.158.112.15 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1332953320 9897 127.0.0.1 (28 Mar 2012 16:48:40 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Wed, 28 Mar 2012 16:48:40 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=62.158.112.15; posting-account=nibe3QoAAADcYL8fC0WC6vCas4By1Xgn User-Agent: G2/1.0 X-Received-Bytes: 6052 Xref: csiph.com comp.lang.forth:10725 Am Dienstag, 27. M=E4rz 2012 13:05:48 UTC+2 schrieb Albert van der Horst: > In article <10851509008435@frunobulax.edu>, Marcel Hendrix w= rote: > >Admit it (when trying it yourself), this exercise is > >surprisingly tricky. > > > >-marcel > > > >-- ------------------------------------------- > >(* > > * LANGUAGE : ANS Forth with extensions > > * PROJECT : Forth Environments > > * DESCRIPTION : Sum of squares of two largest of three values > > * CATEGORY : Programming exercise > > * AUTHOR : Marcel Hendrix > > * LAST CHANGE : March 25, 2012, Marcel Hendrix > > *) > > > > > > > > NEEDS -miscutil > > > > REVISION -sumsquares "--- Sum of Squares Version 0.01 ---" > > > > PRIVATES > > > >DOC > >(* > > > > Sum of squares of two largest of three values > > > > This exercise comes to us from the book "Structure and Interpretation = of > > Computer Programs" by Abelson and Sussman (exercise 1.3): > > > > Define a procedure that takes three numbers as arguments and returns > > the sum of the squares of the two larger numbers. > >*) > >ENDDOC > > > >: DSQR ( u -- du ) DUP M* ; PRIVATE > >: .ANSWER ( ud -- ) CR ." The sum of the squares of the two larger numb= ers is " (n,3) ; PRIVATE > > > >: SOS ( n1 n2 n3 -- ) > > 2DUP > IF SWAP ENDIF ( x1) DSQR 2>R > > MAX ( x2) DSQR 2R> D+ .ANSWER ; > > > > > >: SQR ( u1 -- u2 ) DUP * ; PRIVATE > >: SUM-OF-SQUARES ( n1 n2 n3 -- ) 2DUP > IF SWAP ENDIF SQR -ROT MAX SQ= R + . ; > > > >:ABOUT CR ." Print the sum of the squares of the two larger numbers from= {n1, n2, n3}." > > CR ." The numbers should have less than 18 digits." > > CR ." Try: 1 2 3 SOS -- print 13, double precision." > > CR ." 1 2 3 SUM-OF-SQUARES -- single precision." ; > > > > .ABOUT -sumsquares CR > > DEPRIVE > > > > (* End of Source *) > > >=20 > Why not start with > ( n1 n2 n3 -- n4 n5 ) 2MAX leave the two largest numbers of 3. > ( a b -- csquare ) HYP2 leave the sum of the squares of a and b. >=20 > : SUM-OF-SQUARES 2MAX HYP2 ; >=20 > A much more interesting problem is: > It is well-known that a prime is the sum of 2 squares in exactly > one way 1]. Find them. >=20 > 1] Unless of course it leaves 3 by division by 4. Those numbers have > no solutions. >=20 > Example: > 101 =3D 10^2 + 1^2 > 97 =3D 9^2 + 4^2 >=20 > This sometimes comes up as a sub problem in Euler, where it has to > be executed millions of times if not more. So it must be fast. >=20 > First all , let us find some primes. > " > AMDX86 ciforth beta $RCSfile: ci86.gnr,v $ $Revision: 5.47 $ > ... > OK > INCLUDE rabbin.frt WANT NEW-IF > ... > AGAIN : ISN'T UNIQUE > OK > DO-DEBUG >=20 > S[ ] OK 1,000,000,000,000,000,001 BEGIN 4 + DUP rprime? UNTIL > S[ 1000000000000000009 ] OK BEGIN 4 + DUP rprime? UNTIL > S[ 1000000000000000177 ] OK BEGIN 4 + DUP rprime? UNTIL > S[ 1000000000000000201 ] OK BYE > " > Now finding solutions: >=20 > " > AMDX86 ciforth beta $RCSfile: ci86.gnr,v $ $Revision: 5.47 $ > ... > OK > INCLUDE findsq.frt WANT MARK-TIME > ... > OK > MARK-TIME 1,000,000,000,000,000,009 solve-p . . ELAPSED .uS > 3 1000000000 517 uS OK > MARK-TIME 1,000,000,000,000,000,177 solve-p . . ELAPSED .uS > 633708561 773571884 535 uS OK > 633708561 SQ DUP . 773571884 SQ DUP . + . > 401586540284690721 598413459715309456 1000000000000000177 OK > BYE > " > The first solution is easy to find, but the second? > I won't spoil the fun by showing findsq.frt already. > It is non-trivial indeed and surprisingly short, once you > have enough modulo arithmetic in place. >=20 > Groetjes Albert >=20 > -- > --=20 > Albert van der Horst, UTRECHT,THE NETHERLANDS > Economic growth -- being exponential -- ultimately falters. > albert@spe&ar&c.xs4all.nl &=3Dn http://home.hccnet.nl/a.w.m.van.der.horst Let me check, if I understand correctly what you want: -------------------- 149909 constant prime \ "sqrt" implementation is a google search result ;) : sqrt-closer 2dup / over - 2 / ; : sqrt 1 begin sqrt-closer dup while + repeat drop nip ; : ^2 dup * ; : val create , ; 1 val s1 prime 1- sqrt val s2 prime 1- s2 @ ^2 - val rem : border @ 2* 1- * rem +! ; : .results prime . ." --- s1 =3D " s1 @ . ." s2 =3D " s2 @ . ." res= ult: " s1 @ ^2 s2 @ ^2 + . cr ; : calculate begin rem @ while 1 s1 +! -1 s1 border rem @ 0 < if 1 s2 border -1 s2 +! then repeat ; calculate .results -------------------- It's stupid implementation, but at least I got what wanted? Regards, -Helmar