[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gforth] words backwards ( J. David Boyd) 2 (J. David Boyd)

From: James Gere
Subject: Re: [gforth] words backwards ( J. David Boyd) 2 (J. David Boyd)
Date: Thu, 1 Jun 2017 04:38:39 -0400

     Hi, David,
                       You posed a great question to start us off. 
Maybe I got carried away.   As for "strange," billions of
people around the world write in different, strange ways:
bottom to top, right to left, in circles, or in spirals.
Some of them even use computers:-).

     Bernd Paysan sent me an improved version of 'nwords'
(aka. 'ktop').  I'm not sure it reached the Digest, so here it is:
          : nwords ( n --- )
          cr 0 [: .word >r 1- r> over 0> ;] context @ traverse-wordlist 2drop ;

     I would also like to suggest a different algorithm for
reversing the links on the stack or in an array, IF space is at a 
premium, as this keeps fewer pointers ( about, 2*square-root of N )
and works nearly as fast:

          61 value rootof#
          \ The square-root of the number of words gives minimum space.

          : rlist ( [nt-start] col n -- col' ) 
             ?dup-if  2>r  r@ 1 ?do   dup >link @  loop
                 2r> 0 do  swap .word  loop then ;     
         : rmwords ( -- )   
             0 [:  over rootof# mod 0= if  tuck  then  1 under+  ;] 
             context @ traverse-wordlist
             rootof# /mod
            >r  0 swap cr rlist   r> 0 ?do  rootof# rlist  loop drop ;    

.  Also, you get two reversers in this deal.  
     IF space is at a higher premium yet, you can continue the idea for
the cost of a traversal and some overhead per root, using, 
rootof# + rootofrootof# + ... pointers.  
     So, 65536 words would use, 256 + 16 + 4 + 2 +1  = 279  pointers 
and require the first traversal ( gather rootof# & count ) and 3 similar
traversals, plus the write-out and loop overheads, but the saving of 
1 pointer in the last three terms isn't worth another 2 traversals, 
so 16 looks the place to stop, giving 256 + 16 +16 = 288 pointers and 
4 total traversals ( bundling the write ).

     I use the big-"IF" here, but I'm always a little skeptical of claims
there is always enough space and speed with modern computers.
If that were so, we would bubble-sort everything, defrag our sd-cards,
and never have to worry about how many apps and media files we 
have nor whether to upgrade our phone's os, and we wouldn't fall asleep
during installs and virus scans, and we'd multitask everything at once, 
and be done before we began:-).

     Keep asking good questions, and feel free to explore and experiment.

reply via email to

[Prev in Thread] Current Thread [Next in Thread]