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

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

Challenge for Christmas

Started bylehs <skydda.barnen@gmail.com>
First post2016-12-24 06:10 -0800
Last post2016-12-31 10:53 -0800
Articles 11 on this page of 51 — 8 participants

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

Contents

  Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-24 06:10 -0800
    Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-24 14:17 -0800
      Re: Challenge for Christmas mhx@iae.nl - 2016-12-24 15:37 -0800
      Re: Challenge for Christmas mhx@iae.nl - 2016-12-24 15:43 -0800
      Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 01:25 -0800
        Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 06:59 -0800
          Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 07:26 -0800
            Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 07:57 -0800
              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 08:07 -0800
                Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 08:25 -0800
    Challenge for Christmas Ilya Tarasov <ilya74.tarasov@gmail.com> - 2016-12-25 07:39 -0800
    Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-25 16:52 +0000
      Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 09:33 -0800
        Re: Challenge for Christmas Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2016-12-25 18:15 +0000
          Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-25 13:21 -0800
            Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-25 16:51 -0800
              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 00:48 -0800
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 01:36 -0800
                Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 01:39 -0800
                  Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-26 04:36 -0800
                    Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 07:40 -0800
                      Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 15:53 +0000
                        Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 08:57 -0800
                        Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 13:12 +0000
                          Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 16:58 +0100
                            Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 16:01 +0000
                              Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 19:10 +0100
                                Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-27 18:08 +0000
                                  Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 20:13 +0100
                                    Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 08:19 +0000
                                      Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-28 12:49 +0100
                                        Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 14:26 +0000
                                  Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-29 13:13 +0000
                          Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-27 12:29 -0800
                            Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-27 22:25 +0100
                              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-27 14:19 -0800
                            Re: Challenge for Christmas november.nihal@gmail.com - 2016-12-27 14:14 -0800
                            Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-28 11:06 +0000
                              Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-28 04:22 -0800
                Re: Challenge for Christmas john <anon@example.com> - 2016-12-26 13:05 +0000
                  Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 07:45 -0800
            Re: Challenge for Christmas Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2016-12-26 07:44 +0000
          Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 13:21 +0000
            Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 13:57 +0000
              Re: Challenge for Christmas anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-12-26 14:58 +0000
    Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-26 17:24 +0100
      Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 09:15 -0800
      Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-26 11:45 -0800
      Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-30 10:47 -0800
        Re: Challenge for Christmas albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) - 2016-12-31 15:31 +0100
          Re: Challenge for Christmas lehs <skydda.barnen@gmail.com> - 2016-12-31 10:53 -0800

Page 3 of 3 — ← Prev page 1 2 [3]

#53549

Fromlehs <skydda.barnen@gmail.com>
Date2016-12-26 07:45 -0800
Message-ID<e23cee47-40bd-4646-a680-2bbffdf44bc7@googlegroups.com>
In reply to#53544
Den måndag 26 december 2016 kl. 14:04:40 UTC+1 skrev john:
> In article <1795abbc-3937-419e-9699-4be39eff5aef@googlegroups.com>, 
> skydda.barnen@gmail.com says...
> > Maybe one could use a simple implementation of sets and a set stack?
> > 
> 
> now you're getting somewhere
> 
> -- 
> 
> john
> 
> =========================
> http://johntech.co.uk
> 
> "Bleeding Edge Forum"
> http://johntech.co.uk/forum/ 
> 
> =========================

Yes, I think it will be very difficult to solve the problem without sets, lists, trees or corresponding dynamic structures.

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

#53539

FromGerry Jackson <gerry@jackson9000.fsnet.co.uk>
Date2016-12-26 07:44 +0000
Message-ID<o3qhm8$vch$1@dont-email.me>
In reply to#53537
On 25/12/2016 21:21, lehs wrote:
> I'm afraid non of the solutions above are correct. Try the buffer 3,6,15 for example. Neither solution gives the correct answer for u=6 or u=18. As far as I can see.
>

As NN points out, reverse the order. Only minor changes are needed

create vec 3 , 6 , 15 , here 1 cells - constant end-vec

: factor?   ( u u2 -- u3)
    >r                            ( -- u  ) ( R: -- u2 )
    begin
       dup r@ /mod swap 0=        ( -- u quot rem=0 )
    while                         ( -- u quot )
       nip                        ( -- quot)
    repeat
    r> 2drop                      ( -- u' )
;

: is-a-product  ( u ad1 ad2 -- f )
    do
       i @            ( -- u u2 )
       factor?        ( -- u' )
       -1 cells
    +loop
    1 =
;

: go ( u -- ) vec end-vec is-a-product if ." yes" else ." no" then ;

6 go  yes ok
18 go  yes ok

-- 
Gerry

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

#53545

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2016-12-26 13:21 +0000
Message-ID<2016Dec26.142126@mips.complang.tuwien.ac.at>
In reply to#53535
Gerry Jackson <gerry@jackson9000.fsnet.co.uk> writes:
>While Anton was posting his solution I arrived at an almost identical 
>solution.

I wondered about factoring out the inner loop, you did it.

>: is-a-product  ( u ad1 ad2 -- f )
>    swap
>    ?do
>       i @            ( -- u u2 )
>       factor?        ( -- u' )
>       dup 1 = if leave then
>       1 cells
>    +loop
>    1 =
>;

Either leave out the LEAVE line (I see you did that in the revised
version), or use EXIT instead to avoid testing for 1= again; here's
the latter variant, based on your revised version (untested):

: is-a-product  ( u ad1 ad2 -- f )
    do
       i @            ( -- u u2 )
       factor?        ( -- u' )
       dup 1 = if
           drop true unloop exit then
       -1 cells
    +loop
    drop false ;

The other version looks neater.

>Anton's solution, of course, should have
>
>1 cells +loop
>
>at the end of the do ... loop

Good catch.  Interesting that it passed all the test cases that were
given in the original posting on my machines.  I guess that all the
additional numbers fetched from the array were non-zero, and were not
divisors of the numbers used in the test cases; on a 64-bit system
these numbers were, for the original factors {2,3,4}:

$2 $300000000000000 $3000000000000 $30000000000 $300000000 $3000000
$30000 $300 $3 $400000000000000 $4000000000000 $40000000000 $400000000
$4000000 $40000 $400 $4 $7F00000000000000 $E27F000000000000
$E27F0000000000 $2D00E27F00000000 $BF2D00E27F000000 $7FBF2D00E27F0000
$E57FBF2D00E27F00

My guess is that on lehs' system the next byte after the cell
containing 4 contained 0, and so he got a division by zero.

This bug would have been caught by hardware reporting unaligned
accesses; this is possible on AMD64 and IA-32 (since the 486) in
theory, but in practice the software infrastructure (C library stuff)
does not work if it is enabled.

- 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]

#53546

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2016-12-26 13:57 +0000
Message-ID<2016Dec26.145757@mips.complang.tuwien.ac.at>
In reply to#53545
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>I wondered about factoring out the inner loop, you did it.

I integrated the fixes (cell stride and downwards stride) into my
original unfactored variant, and used some Gforth-specific extensions:

: product? ( n addr u -- )
    \ is n a product of the numbers in addr u?
    >r cell - dup r> th u-do ( n1 )
	begin
	    dup i @ /mod swap 0= while ( n1 n2 )
		nip repeat
	drop cell -loop
    1 = ;

Again, we see that the existing counted-loop words (including Gforth's
U-DO ... -LOOP) are not a good fit striding backwards through an
array.  One would have to do the decrement first, and leave the loop
when crossing the boundary between limit and limit-1.  Maybe with a
syntax like

U-DO
  ( u ) DECREMENT
  ...
REPEAT

The code above would become:

: product? ( n addr u -- )
    \ is n a product of the numbers in addr u?
    cells over + u-do
       cell decrement
	  begin
	    dup i @ /mod swap 0= while ( n1 n2 )
		nip repeat
          drop repeat
    1 = ;
    
The setup in front of the U-DO becomes quite a bit simpler.

- 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]

#53547

Fromanton@mips.complang.tuwien.ac.at (Anton Ertl)
Date2016-12-26 14:58 +0000
Message-ID<2016Dec26.155852@mips.complang.tuwien.ac.at>
In reply to#53546
anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Again, we see that the existing counted-loop words (including Gforth's
>U-DO ... -LOOP) are not a good fit striding backwards through an
>array.  One would have to do the decrement first, and leave the loop
>when crossing the boundary between limit and limit-1.  Maybe with a
>syntax like
>
>U-DO
>  ( u ) DECREMENT
>  ...
>REPEAT
>
>The code above would become:
>
>: product? ( n addr u -- )
>    \ is n a product of the numbers in addr u?
>    cells over + u-do
>       cell decrement
>	  begin
>	    dup i @ /mod swap 0= while ( n1 n2 )
>		nip repeat
>          drop repeat
>    1 = ;
>    
>The setup in front of the U-DO becomes quite a bit simpler.

Given that the convention for specifying arrays is "addr count", why
not simplify the setup even further and have

addr count stride A+DO ... A+LOOP \ i goes from addr...addr+(count-1)*stride
addr count stride A-DO ... A-LOOP \ i goes from addr+(count-1)*stride...addr

The example would become:

: product? ( n addr u -- )
    \ is n a product of the numbers in addr u?
    cell a-do ( n1 )
	  begin
	    dup i @ /mod swap 0= while ( n1 n2 )
		nip repeat
          drop a-loop
    1 = ;

- 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]

#53551

Fromalbert@cherry.spenarnc.xs4all.nl (Albert van der Horst)
Date2016-12-26 17:24 +0100
Message-ID<o3rg8d$7q0$1@cherry.spenarnc.xs4all.nl>
In reply to#53519
In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
lehs  <skydda.barnen@gmail.com> wrote:
>Given a buffer of increasing unsigned integers beginning at addr1 and ending at addr2-cell. I want a routine
>
>is_a_product  ( u addr2 addr1 -- flag )
>
>answering the question wether u is a product of some numbers in the field or not.
>
>Example: if the field contains the integers 2,3,4 then 2,6,9,12
should give true flag while 7,10,21 should give false flag. Unless I'm
wrong there is a lot of different strategies, but I can't see an
obvious one.

I made it a challenge to have it right the first time, i.e. the first
test must succeed. That didn't happen because in the specification
only the examples make clear that each number may be used more than once.
Then the modified program accepted the test cases.
Note that I tightened the specs.

This ask for a program that does recursion on several levels,
much like the infamous coin change program. These programs are
notoriously inefficient. With recursion you don't want three items
on the stack. But the end of the array is fortunately always the
same, which saves one parameter.

------------------------------------------------
WANT TRUE
VARIABLE high
: (is_a_product)   ( n,a)
   OVER 1 = IF 2DROP TRUE EXIT THEN    ( n,a)
   2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
   BEGIN DUP high @ <> WHILE           ( n,a)
      2DUP @ /MOD                      ( n,a, rem, n')
      SWAP IF DROP ELSE
         OVER RECURSE IF 2DROP TRUE EXIT THEN
      THEN                             ( n,a)
   CELL+ REPEAT                        ( n,a')
   2DROP FALSE EXIT ;

\ For  n  and a non-inclusive range  adr1  adr2  ,return
\ "n  can  be written as a product of numbers in the range, where
\ each number can be used zero or more times"
: is_a_product   SWAP high ! (is_a_product) ;

HERE 2 , 3 , 4 , HERE
CONSTANT adr2   CONSTANT adr1

: q adr2 adr1 is_a_product ;

"Expect false " TYPE 7 q . 10 q . 21 q . CR
"Expect true " TYPE 2 q . 6 q . 9 q . 12 q . CR
 ---------------------------------------------------

Expect false 0 0 0
Expect true -1 -1 -1 -1

You can leave out the line with the star. That is an optimisation,
based on the given that the factors are in increasing order.

Note the Moore convention for parameters: and extra space around
the names. My convention to replace -- by `` : ''  `` leaves ''
or `` returns '' complements that.

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

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

#53553

Fromlehs <skydda.barnen@gmail.com>
Date2016-12-26 09:15 -0800
Message-ID<7203526b-8ea4-4097-9ae4-90cffea33a92@googlegroups.com>
In reply to#53551
Den måndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Horst:
> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
> lehs  <skydda.barnen@gmail.com> wrote:
> >Given a buffer of increasing unsigned integers beginning at addr1 and ending at addr2-cell. I want a routine
> >
> >is_a_product  ( u addr2 addr1 -- flag )
> >
> >answering the question wether u is a product of some numbers in the field or not.
> >
> >Example: if the field contains the integers 2,3,4 then 2,6,9,12
> should give true flag while 7,10,21 should give false flag. Unless I'm
> wrong there is a lot of different strategies, but I can't see an
> obvious one.
> 
> I made it a challenge to have it right the first time, i.e. the first
> test must succeed. That didn't happen because in the specification
> only the examples make clear that each number may be used more than once.
> Then the modified program accepted the test cases.
> Note that I tightened the specs.
> 
> This ask for a program that does recursion on several levels,
> much like the infamous coin change program. These programs are
> notoriously inefficient. With recursion you don't want three items
> on the stack. But the end of the array is fortunately always the
> same, which saves one parameter.
> 
> ------------------------------------------------
> WANT TRUE
> VARIABLE high
> : (is_a_product)   ( n,a)
>    OVER 1 = IF 2DROP TRUE EXIT THEN    ( n,a)
>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
>    BEGIN DUP high @ <> WHILE           ( n,a)
>       2DUP @ /MOD                      ( n,a, rem, n')
>       SWAP IF DROP ELSE
>          OVER RECURSE IF 2DROP TRUE EXIT THEN
>       THEN                             ( n,a)
>    CELL+ REPEAT                        ( n,a')
>    2DROP FALSE EXIT ;
> 
> \ For  n  and a non-inclusive range  adr1  adr2  ,return
> \ "n  can  be written as a product of numbers in the range, where
> \ each number can be used zero or more times"
> : is_a_product   SWAP high ! (is_a_product) ;
> 
> HERE 2 , 3 , 4 , HERE
> CONSTANT adr2   CONSTANT adr1
> 
> : q adr2 adr1 is_a_product ;
> 
> "Expect false " TYPE 7 q . 10 q . 21 q . CR
> "Expect true " TYPE 2 q . 6 q . 9 q . 12 q . CR
>  ---------------------------------------------------
> 
> Expect false 0 0 0
> Expect true -1 -1 -1 -1
> 
> You can leave out the line with the star. That is an optimisation,
> based on the given that the factors are in increasing order.
> 
> Note the Moore convention for parameters: and extra space around
> the names. My convention to replace -- by `` : ''  `` leaves ''
> or `` returns '' complements that.
> 
> 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

Hi Albert! This looks good. I don't understand it yet but the tests seems good.

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

#53554

Fromlehs <skydda.barnen@gmail.com>
Date2016-12-26 11:45 -0800
Message-ID<30f7aeeb-e32b-4a17-855e-a9595af047be@googlegroups.com>
In reply to#53551
Den måndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Horst:
> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
> lehs  <skydda.barnen@gmail.com> wrote:
> >Given a buffer of increasing unsigned integers beginning at addr1 and ending at addr2-cell. I want a routine
> >
> >is_a_product  ( u addr2 addr1 -- flag )
> >
> >answering the question wether u is a product of some numbers in the field or not.
> >
> >Example: if the field contains the integers 2,3,4 then 2,6,9,12
> should give true flag while 7,10,21 should give false flag. Unless I'm
> wrong there is a lot of different strategies, but I can't see an
> obvious one.
> 
> I made it a challenge to have it right the first time, i.e. the first
> test must succeed. That didn't happen because in the specification
> only the examples make clear that each number may be used more than once.
> Then the modified program accepted the test cases.
> Note that I tightened the specs.
> 
> This ask for a program that does recursion on several levels,
> much like the infamous coin change program. These programs are
> notoriously inefficient. With recursion you don't want three items
> on the stack. But the end of the array is fortunately always the
> same, which saves one parameter.
> 
> ------------------------------------------------
> WANT TRUE
> VARIABLE high
> : (is_a_product)   ( n,a)
>    OVER 1 = IF 2DROP TRUE EXIT THEN    ( n,a)
>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
>    BEGIN DUP high @ <> WHILE           ( n,a)
>       2DUP @ /MOD                      ( n,a, rem, n')
>       SWAP IF DROP ELSE
>          OVER RECURSE IF 2DROP TRUE EXIT THEN
>       THEN                             ( n,a)
>    CELL+ REPEAT                        ( n,a')
>    2DROP FALSE EXIT ;
> 
> \ For  n  and a non-inclusive range  adr1  adr2  ,return
> \ "n  can  be written as a product of numbers in the range, where
> \ each number can be used zero or more times"
> : is_a_product   SWAP high ! (is_a_product) ;
> 
> HERE 2 , 3 , 4 , HERE
> CONSTANT adr2   CONSTANT adr1
> 
> : q adr2 adr1 is_a_product ;
> 
> "Expect false " TYPE 7 q . 10 q . 21 q . CR
> "Expect true " TYPE 2 q . 6 q . 9 q . 12 q . CR
>  ---------------------------------------------------
> 
> Expect false 0 0 0
> Expect true -1 -1 -1 -1
> 
> You can leave out the line with the star. That is an optimisation,
> based on the given that the factors are in increasing order.
> 
> Note the Moore convention for parameters: and extra space around
> the names. My convention to replace -- by `` : ''  `` leaves ''
> or `` returns '' complements that.
> 
> 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

Very nice! I'm convinced this is the simplest possible approach. With your permission I will use the code on my blog http://forthmath.blogspot.se to study integer monoids, sets of natural numbers that are closed under multiplication (i.e. if two numbers belong to a certain monoid, then also their product do that). 

All such monoids are infinite, but are determed by its generators. With is_a_product it's possible to decide whether a natural number is a member of a finitely generated integer  monoid or not.

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

#53616

Fromlehs <skydda.barnen@gmail.com>
Date2016-12-30 10:47 -0800
Message-ID<a2a6f75b-8292-40ba-a35d-9a75704af23e@googlegroups.com>
In reply to#53551
Den måndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Horst:
> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
> lehs  <skydda.barnen@gmail.com> wrote:
> >Given a buffer of increasing unsigned integers beginning at addr1 and ending at addr2-cell. I want a routine
> >
> >is_a_product  ( u addr2 addr1 -- flag )
> >
> >answering the question wether u is a product of some numbers in the field or not.
> >
> >Example: if the field contains the integers 2,3,4 then 2,6,9,12
> should give true flag while 7,10,21 should give false flag. Unless I'm
> wrong there is a lot of different strategies, but I can't see an
> obvious one.
> 
> I made it a challenge to have it right the first time, i.e. the first
> test must succeed. That didn't happen because in the specification
> only the examples make clear that each number may be used more than once.
> Then the modified program accepted the test cases.
> Note that I tightened the specs.
> 
> This ask for a program that does recursion on several levels,
> much like the infamous coin change program. These programs are
> notoriously inefficient. With recursion you don't want three items
> on the stack. But the end of the array is fortunately always the
> same, which saves one parameter.
> 
> ------------------------------------------------
> WANT TRUE
> VARIABLE high
> : (is_a_product)   ( n,a)
>    OVER 1 = IF 2DROP TRUE EXIT THEN    ( n,a)
>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
>    BEGIN DUP high @ <> WHILE           ( n,a)
>       2DUP @ /MOD                      ( n,a, rem, n')
>       SWAP IF DROP ELSE
>          OVER RECURSE IF 2DROP TRUE EXIT THEN
>       THEN                             ( n,a)
>    CELL+ REPEAT                        ( n,a')
>    2DROP FALSE EXIT ;
> 
> \ For  n  and a non-inclusive range  adr1  adr2  ,return
> \ "n  can  be written as a product of numbers in the range, where
> \ each number can be used zero or more times"/
> : is_a_product   SWAP high ! (is_a_product) ;
> 
> HERE 2 , 3 , 4 , HERE
> CONSTANT adr2   CONSTANT adr1
> 
> : q adr2 adr1 is_a_product ;
> 
> "Expect false " TYPE 7 q . 10 q . 21 q . CR
> "Expect true " TYPE 2 q . 6 q . 9 q . 12 q . CR
>  ---------------------------------------------------
> 
> Expect false 0 0 0
> Expect true -1 -1 -1 -1
> 
> You can leave out the line with the star. That is an optimisation,
> based on the given that the factors are in increasing order.
> 
> Note the Moore convention for parameters: and extra space around
> the names. My convention to replace -- by `` : ''  `` leaves ''
> or `` returns '' complements that.
> 
> 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

Unfortunately, there seems to be an error, at least for me:

The buffer 3 7 13 15 gives true for 64.

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

#53640

Fromalbert@cherry.spenarnc.xs4all.nl (Albert van der Horst)
Date2016-12-31 15:31 +0100
Message-ID<o48fge$vql$1@cherry.spenarnc.xs4all.nl>
In reply to#53616
In article <a2a6f75b-8292-40ba-a35d-9a75704af23e@googlegroups.com>,
lehs  <skydda.barnen@gmail.com> wrote:
>Den m=C3=A5ndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Ho=
>rst:
>> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
>> lehs  <skydda.barnen@gmail.com> wrote:
>> >Given a buffer of increasing unsigned integers beginning at addr1 and en=
>ding at addr2-cell. I want a routine
>> >
>> >is_a_product  ( u addr2 addr1 -- flag )
>> >
>> >answering the question wether u is a product of some numbers in the fiel=
>d or not.
>> >
<SNIP>
>> ------------------------------------------------
>> WANT TRUE
>> VARIABLE high
>> : (is_a_product)   ( n,a)
>>    OVER 1 =3D IF 2DROP TRUE EXIT THEN    ( n,a)
>>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
>>    BEGIN DUP high @ <> WHILE           ( n,a)
>>       2DUP @ /MOD                      ( n,a, rem, n')
>>       SWAP IF DROP ELSE
>>          OVER RECURSE IF 2DROP TRUE EXIT THEN
>>       THEN                             ( n,a)
>>    CELL+ REPEAT                        ( n,a')
>>    2DROP FALSE EXIT ;
>>=20
>> \ For  n  and a non-inclusive range  adr1  adr2  ,return
>> \ "n  can  be written as a product of numbers in the range, where
>> \ each number can be used zero or more times"/
>> : is_a_product   SWAP high ! (is_a_product) ;

<SNIP>
>
>Unfortunately, there seems to be an error, at least for me:
>
>The buffer 3 7 13 15 gives true for 64.

Not for me:
"
HERE 3 , 7 , 13 , 15 , HERE
CONSTANT high   CONSTANT low
: q high low is_a_product ;

64 DUP .
q .
"
With result:

 high : ISN'T UNIQUE
low : ISN'T UNIQUE
q : ISN'T UNIQUE
64 0 ~$

Maybe you forgot to define `high `low `q after you
made a new buffer?
-- 
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

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

#53646

Fromlehs <skydda.barnen@gmail.com>
Date2016-12-31 10:53 -0800
Message-ID<cc281108-9600-4597-a0f5-2e97966b2760@googlegroups.com>
In reply to#53640
Den lördag 31 december 2016 kl. 15:21:10 UTC+1 skrev Albert van der Horst:
> In article <a2a6f75b-8292-40ba-a35d-9a75704af23e@googlegroups.com>,
> lehs  <skydda.barnen@gmail.com> wrote:
> >Den m=C3=A5ndag 26 december 2016 kl. 17:14:08 UTC+1 skrev Albert van der Ho=
> >rst:
> >> In article <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com>,
> >> lehs  <skydda.barnen@gmail.com> wrote:
> >> >Given a buffer of increasing unsigned integers beginning at addr1 and en=
> >ding at addr2-cell. I want a routine
> >> >
> >> >is_a_product  ( u addr2 addr1 -- flag )
> >> >
> >> >answering the question wether u is a product of some numbers in the fiel=
> >d or not.
> >> >
> <SNIP>
> >> ------------------------------------------------
> >> WANT TRUE
> >> VARIABLE high
> >> : (is_a_product)   ( n,a)
> >>    OVER 1 =3D IF 2DROP TRUE EXIT THEN    ( n,a)
> >>    2DUP @ < IF 2DROP FALSE EXIT THEN   ( n,a)    \ * note
> >>    BEGIN DUP high @ <> WHILE           ( n,a)
> >>       2DUP @ /MOD                      ( n,a, rem, n')
> >>       SWAP IF DROP ELSE
> >>          OVER RECURSE IF 2DROP TRUE EXIT THEN
> >>       THEN                             ( n,a)
> >>    CELL+ REPEAT                        ( n,a')
> >>    2DROP FALSE EXIT ;
> >>=20
> >> \ For  n  and a non-inclusive range  adr1  adr2  ,return
> >> \ "n  can  be written as a product of numbers in the range, where
> >> \ each number can be used zero or more times"/
> >> : is_a_product   SWAP high ! (is_a_product) ;
> 
> <SNIP>
> >
> >Unfortunately, there seems to be an error, at least for me:
> >
> >The buffer 3 7 13 15 gives true for 64.
> 
> Not for me:
> "
> HERE 3 , 7 , 13 , 15 , HERE
> CONSTANT high   CONSTANT low
> : q high low is_a_product ;
> 
> 64 DUP .
> q .
> "
> With result:
> 
>  high : ISN'T UNIQUE
> low : ISN'T UNIQUE
> q : ISN'T UNIQUE
> 64 0 ~$
> 
> Maybe you forgot to define `high `low `q after you
> made a new buffer?
> -- 
> 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
You are right, I made an error converting a set to a buffer. Thanks again and happy new year!

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

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

csiph-web