Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #10725

Re: Sum of squares

Show key headers only | View raw

Am Dienstag, 27. März 2012 13:05:48 UTC+2 schrieb Albert van der Horst:
> In article <10851509008435@frunobulax.edu>, Marcel Hendrix <mhx@iae.nl> wrote:
> >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 numbers 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 SQR + . ;
> >
> >: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 *)
> >
> 
> 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.
> 
> : SUM-OF-SQUARES 2MAX HYP2 ;
> 
> 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.
> 
> 1] Unless of course it leaves 3 by division by 4. Those numbers have
>    no solutions.
> 
>    Example:
>    101 = 10^2 + 1^2
>     97 = 9^2  + 4^2
> 
> 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.
> 
> 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
> 
>   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:
> 
> "
>   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.
> 
> Groetjes Albert
> 
> --
> -- 
> Albert van der Horst, UTRECHT,THE NETHERLANDS
> Economic growth -- being exponential -- ultimately falters.
> albert@spe&ar&c.xs4all.nl &=n 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 = " s1 @ . ." s2 = " s2 @ . ." result: " 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

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Sum of squares mhx@iae.nl (Marcel Hendrix) - 2012-03-26 20:50 +0200
  Re: Sum of squares "A. K." <akk@nospam.org> - 2012-03-26 21:43 +0200
  Re: Sum of squares Paul Rubin <no.email@nospam.invalid> - 2012-03-26 16:52 -0700
    Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-27 03:15 -0700
      Re: Sum of squares Paul Rubin <no.email@nospam.invalid> - 2012-03-28 08:16 -0700
    Re: Sum of squares BruceMcF <agila61@netscape.net> - 2012-03-28 06:06 -0700
  Re: Sum of squares Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2012-03-27 12:13 +0100
    Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-27 04:03 -0700
      Re: Sum of squares Zbiggy <zbigniew2011REMOVE@gmail.REMOVE.com> - 2012-03-27 13:55 +0100
  Re: Sum of squares Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-27 11:05 +0000
    Re: Sum of squares Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-28 11:41 +0000
      Re: Sum of squares Paul Rubin <no.email@nospam.invalid> - 2012-03-28 07:41 -0700
      Re: Sum of squares mhx@iae.nl (Marcel Hendrix) - 2012-03-29 22:06 +0200
      Re: Sum of squares Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-03-31 11:48 +0000
    Re: Sum of squares Alexander Adler <alexander.adler@stud.uni-frankfurt.de> - 2012-03-29 19:33 +0200
      Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-29 11:16 -0700
        Re: Sum of squares Albert van der Horst <albert@spenarnc.xs4all.nl> - 2012-04-03 09:47 +0000
    Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-28 09:42 -0700
    Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-28 11:08 -0700
  Re: Sum of squares Ecki <ecki@intershop.de> - 2012-03-27 16:15 +0200
    Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-27 07:35 -0700
      Re: Sum of squares hwfwguy@gmail.com - 2012-03-27 08:00 -0700
        Re: Sum of squares Helmar Wodtke <helmwo@gmail.com> - 2012-03-27 08:21 -0700
        Re: Sum of squares Ecki <ecki@intershop.de> - 2012-03-29 09:05 +0200

csiph-web