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

Groups > comp.lang.forth > #53253 > unrolled thread

A function to return the sum of the numbers less than n

Back to article view | Back to comp.lang.forth

Contents

  A function to return the sum of the numbers less than n "Robert L." <No_spamming@noWhere_7073.org> - 2016-12-10 10:47 +0000
    Re: A function to return the sum of the numbers less than n Julian Fondren <julian.fondren@gmail.com> - 2016-12-10 03:19 -0800
      Re: A function to return the sum of the numbers less than n foxaudioresearch@gmail.com - 2016-12-10 03:58 -0800
      Re: A function to return the sum of the numbers less than n anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-10 12:48 +0000
        Re: A function to return the sum of the numbers less than n Julian Fondren <julian.fondren@gmail.com> - 2016-12-10 05:29 -0800
          Re: A function to return the sum of the numbers less than n pahihu <pahihu@gmail.com> - 2016-12-10 06:37 -0800
          Re: A function to return the sum of the numbers less than n anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-10 17:08 +0000
    Re: A function to return the sum of the numbers less than n jean-pierre@buechi-schmitt.ch - 2016-12-10 07:04 -0800
      Re: A function to return the sum of the numbers less than n awegel@arcor.de (Alexander Wegel) - 2016-12-10 22:59 +0100

#53253 — A function to return the sum of the numbers less than n

> > This is a function to return the sum of the numbers less than n. ----- (1)
> >
> > (defun sum (n)                 ------- (A)
> >    (let ((s 0))                      ------- (B)
> >      (dotimes (i n s)            ------- (C)
> >         (incf si))))                 -------- (D)
> >
> > It gives this output when I run the code in LispWorks : SUM
> >
> > Line A : Defun defines function. Sum is the function. n is simply n as
> > defined in (1)
> >
> > What about lines B, C and D ? What do the terms like let , s , 0 ,
> > dotimes , i , n , s , inc. and si mean ?
> 
> Aw! I thought you switched to python. :-(
> 
> First, there's a bug in this function:  the variable SI is undefined.
> Also, the variable I is unused.  And there's no term INC.
> 
> Obviously, it wanted to be:
> 
>     (defun sum (n)
>       (let ((s 0))
>         (dotimes (i n s)
>           (incf s i))))

Ruby:

def sum n
  (0...n).reduce(0, :+)
end

sum 0
    ==>0
sum 1
    ==>0
sum 22_000
    ==>241989000

In Forth?

-- 
"If a government uses the instruments of power in its hands for the purpose of
leading a people to ruin, then rebellion is not only the right but also the
duty of every individual citizen."

[toc] | [next] | [standalone]

#53255

On Saturday, December 10, 2016 at 4:47:33 AM UTC-6, Robert L. wrote:
> Ruby:
> 
> def sum n
>   (0...n).reduce(0, :+)
> end
> 
> sum 0
>     ==>0
> sum 1
>     ==>0
> sum 22_000
>     ==>241989000
> 

# /usr/bin/time ruby -e 'def sum n; (0...n).reduce(0, :+) end; puts sum 1_000_000_000'
499999999500000000
45.99user 0.01system 0:46.38elapsed 99%CPU (0avgtext+0avgdata 8692maxresident)k
2680inputs+0outputs (1major+1171minor)pagefaults 0swaps

# /usr/bin/time sf ': sum ( n -- d ) 0. rot 0 do i m+ loop ; 1,000,000,000 drop  sum d. bye'
499999999500000000 
2.56user 0.00system 0:02.59elapsed 98%CPU (0avgtext+0avgdata 2020maxresident)k
0inputs+16outputs (0major+162minor)pagefaults 0swaps

[toc] | [prev] | [next] | [standalone]

#53256

Fascinating.  In this case the source code is equivalent size and the result is 18 times faster.

B

[toc] | [prev] | [next] | [standalone]

#53258

Julian Fondren <julian.fondren@gmail.com> writes:
>On Saturday, December 10, 2016 at 4:47:33 AM UTC-6, Robert L. wrote:
>> Ruby:
>> 
>> def sum n
>>   (0...n).reduce(0, :+)
>> end
>> 
>> sum 0
>>     ==>0
>> sum 1
>>     ==>0
>> sum 22_000
>>     ==>241989000
>> 
>
># /usr/bin/time ruby -e 'def sum n; (0...n).reduce(0, :+) end; puts sum 1_000_000_000'
>499999999500000000
>45.99user 0.01system 0:46.38elapsed 99%CPU (0avgtext+0avgdata 8692maxresident)k
>2680inputs+0outputs (1major+1171minor)pagefaults 0swaps
>
># /usr/bin/time sf ': sum ( n -- d ) 0. rot 0 do i m+ loop ; 1,000,000,000 drop  sum d. bye'
>499999999500000000 
>2.56user 0.00system 0:02.59elapsed 98%CPU (0avgtext+0avgdata 2020maxresident)k
>0inputs+16outputs (0major+162minor)pagefaults 0swaps

# /usr/bin/time gforth -e ": sum ( u1 -- u2 ) dup 1- * 2/ ; 1000000000 sum . bye"
499999999500000000 0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 2780maxresident)k
0inputs+0outputs (0major+334minor)pagefaults 0swaps

(supposedly discovered by Gauss when he was 9 years old).

-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#53259

On Saturday, December 10, 2016 at 6:58:25 AM UTC-6, Anton Ertl wrote:
> Julian Fondren <julian.fondren@gmail.com> writes:
> >On Saturday, December 10, 2016 at 4:47:33 AM UTC-6, Robert L. wrote:
> >> Ruby:
> >> 
> >> def sum n
> >>   (0...n).reduce(0, :+)
> >> end
> >> 
> >> sum 0
> >>     ==>0
> >> sum 1
> >>     ==>0
> >> sum 22_000
> >>     ==>241989000
> >> 
> >
> ># /usr/bin/time ruby -e 'def sum n; (0...n).reduce(0, :+) end; puts sum 1_000_000_000'
> >499999999500000000
> >45.99user 0.01system 0:46.38elapsed 99%CPU (0avgtext+0avgdata 8692maxresident)k
> >2680inputs+0outputs (1major+1171minor)pagefaults 0swaps
> >
> ># /usr/bin/time sf ': sum ( n -- d ) 0. rot 0 do i m+ loop ; 1,000,000,000 drop  sum d. bye'
> >499999999500000000 
> >2.56user 0.00system 0:02.59elapsed 98%CPU (0avgtext+0avgdata 2020maxresident)k
> >0inputs+16outputs (0major+162minor)pagefaults 0swaps
> 
> # /usr/bin/time gforth -e ": sum ( u1 -- u2 ) dup 1- * 2/ ; 1000000000 sum . bye"
> 499999999500000000 0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 2780maxresident)k
> 0inputs+0outputs (0major+334minor)pagefaults 0swaps
> 
> (supposedly discovered by Gauss when he was 9 years old).
> 

Woops. I was going to credit Euler.

# /usr/bin/time ruby -e 'def sum n; (n*(n-1))/2 end; puts sum 1_000_000_000'
499999999500000000
0.03user 0.01system 0:00.21elapsed 20%CPU (0avgtext+0avgdata 8672maxresident)k
0inputs+0outputs (0major+1174minor)pagefaults 0swaps

I only remembered why it worked: if you sum 1 thru 100, then you have
the pairs 1 and 100 to make 101, 2 and 99 to make 101, 3 and 98 to
make 101...  and so on.  Half the larger number's pairs that add to
one plus the larger number. Given a "keep the kids silent for a bit"
makework problem, Gauss thought it through rather than do all the rote
additions.

Which might be a nice lesson for our friend here who keeps managing to
make Ruby look worse than it perhaps deserves, while trying to prove
that Ruby is a superior because you can do it without having to think.


This calculation is also harder for 32-bit Forths to replicate :-/


-- Julian

[toc] | [prev] | [next] | [standalone]

#53260

As you all know the main point in the reduce operation, that you can call with any operation.
So I implemented below REDUCE.

With the same rules on my old notebook SwifthForth is still faster.

pahihu


# time sf reduce.f
499999999500000000 

real	1m11.709s
user	1m11.269s
sys	0m0.183s

# time ruby -e 'def sum n; (0...n).reduce(0,:+) end; puts sum 1_000_000_000'
499999999500000000

real	2m56.984s
user	2m55.880s
sys	0m0.481s


My quick and dirty solution is:
: /CLIP   \ hi x lo -- x'
   max min ;

: SAFE-RANGE  \ lo hi "name" --, create a range
   Create over - , ,
   Does>  ( x a -- i )
     2@ swap >R  swap 0 /clip  R> +
; 

: RANGE  \ lo hi "name" --, create a range
   Create over - , ,
   Does>  ( x a -- i )
     2@ drop +
; 

: /RANGE \ 'r -- u, length of range
   >body @ 1+
;

: REDUCE \ x0 xt 'r --  
   dup /range 0 DO
      I over execute    \ x0 xt 'r xi
      -rot              \ x0 xi xt 'r
      >R dup >R         \ x0 i xt, r: xt 'r
      execute
      R> R>
   LOOP
   2drop
;

0 999,999,999 drop range r1
0. ' m+ ' r1 reduce d.
bye

[toc] | [prev] | [next] | [standalone]

#53264

Julian Fondren <julian.fondren@gmail.com> writes:
>On Saturday, December 10, 2016 at 6:58:25 AM UTC-6, Anton Ertl wrote:
>> # /usr/bin/time gforth -e ": sum ( u1 -- u2 ) dup 1- * 2/ ; 1000000000 sum . bye"
>> 499999999500000000 0.00user 0.00system 0:00.00elapsed 66%CPU (0avgtext+0avgdata 2780maxresident)k
>> 0inputs+0outputs (0major+334minor)pagefaults 0swaps
>> 
>> (supposedly discovered by Gauss when he was 9 years old).
>> 
>
>Woops. I was going to credit Euler.

I took the opportunity to look this up in Wikipedia, and while the
story about Gauss (re)discovering this as a child is well known, Euler
already considered the infinite case
<https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF#History>,
and I guess the finite case was considered trivial by him.
<https://en.wikipedia.org/wiki/Triangular_number> says:

|some find it likely that its origin goes back to the Pythagoreans 5th
|century BC.[2] The two formulae were described by the Irish monk
|Dicuil in about 816 in his Computus.

>Given a "keep the kids silent for a bit"
>makework problem

That was one motivation, the other was to make the pupils exercise
their calculation skills.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2016: http://www.euroforth.org/ef16/

[toc] | [prev] | [next] | [standalone]

#53261

Le samedi 10 décembre 2016 11:47:33 UTC+1, Robert L. a écrit :
> > > This is a function to return the sum of the numbers less than n. ----- (1)
> > >
> > > (defun sum (n)                 ------- (A)
> > >    (let ((s 0))                      ------- (B)
> > >      (dotimes (i n s)            ------- (C)
> > >         (incf si))))                 -------- (D)
> > >
> > > It gives this output when I run the code in LispWorks : SUM
> > >
> > > Line A : Defun defines function. Sum is the function. n is simply n as
> > > defined in (1)
> > >
> > > What about lines B, C and D ? What do the terms like let , s , 0 ,
> > > dotimes , i , n , s , inc. and si mean ?
> > 
> > Aw! I thought you switched to python. :-(
> > 
> > First, there's a bug in this function:  the variable SI is undefined.
> > Also, the variable I is unused.  And there's no term INC.
> > 
> > Obviously, it wanted to be:
> > 
> >     (defun sum (n)
> >       (let ((s 0))
> >         (dotimes (i n s)
> >           (incf s i))))
> 
> Ruby:
> 
> def sum n
>   (0...n).reduce(0, :+)
> end
> 
> sum 0
>     ==>0
> sum 1
>     ==>0
> sum 22_000
>     ==>241989000
> 
> In Forth?

: SUM  		S( n --- )


  0 SWAP 0 
  ?DO I + LOOP 
  CR . 	

;

USAGE:  10 SUM   22000 SUM Etc...


What is the purpose of all these questions that consist in comparing the virtual machine Forth with a programming language?

[toc] | [prev] | [next] | [standalone]

#53266

<jean-pierre@buechi-schmitt.ch> wrote:

> What is the purpose of all these questions that consist in comparing
> the virtual machine Forth with a programming language?

It probably increases the time until someone files a complaint.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web