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

Groups > comp.lang.forth > #53562

Re: Challenge for Christmas

From anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups comp.lang.forth
Subject Re: Challenge for Christmas
Date 2016-12-27 16:01 +0000
Organization Institut fuer Computersprachen, Technische Universitaet Wien
Message-ID <2016Dec27.170123@mips.complang.tuwien.ac.at> (permalink)
References <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com> <81704e95-91eb-446c-ae1f-b826bc880941@googlegroups.com> <2016Dec26.165320@mips.complang.tuwien.ac.at> <2016Dec27.141206@mips.complang.tuwien.ac.at> <o3u33l$7nk$1@cherry.spenarnc.xs4all.nl>

Show all headers | View raw

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>In article <2016Dec27.141206@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>>>lehs <skydda.barnen@gmail.com> writes:
>>>>For the buffer 6,8,12 it doesn't work for 576=3D6*8*12, but I don't know if=
>>>> there is a main error or a small error.
>>>
>>>216=6*6*6=8*3*3*3 is also a problematic case.  No simple way to deal
>>>with such cases comes to my mind.  The simplest more complex ways is
>>>probably a search with backtracking or somesuch.
>>
>>I started with my first attempt, added a backtracking search, and
>>arrived at this:
>>
>>: product? recursive { n addr u -- f }
>>    \ is n a product of the numbers in addr u?
>>    n 1 = if
>>       true exit then
>>    addr u cells + addr ?do
>>       n i @ /mod { n1 } 0= if
>>           n1 addr u product? if
>>               true unloop exit then
>>       then
>>    cell +loop
>>    false ;

The disadvantage of this approach is that the same number may be
tested multiple times, leading to explonential* behaviour.  A pretty
bad case is

create z 4 , 6 , 9 ,
x z 3 product?

with x=5*6^n.  The largest x in the 32-bit range is 5*6^11=1813985280,
and that's still pretty fast; for 5*6^16=14105549537280, the time
becomes quite noticable (2.5G cycles on my i5-6600K); for 5*6^17 it's
already 7.3G cycles, for 5*6^18 21G cycles, so it seems to rise with
roughly O(3^n).  The largest such number in the 64-bit range is
5*6^23=3948651115268014080, and PRODUCT? to take about 5T cycles,
about 20 minutes at 4GHz.

One can speed up these cases to have an algorithmic complexity of O(n)
by using memoization; that makes the code more complex, however.

*) The first "l" was a typo, but I actually like the connotations of
this misspelling; google reports 500 hits for it, and there is even a
web site <www.explonential.com>.

>P.s. I've absolutely no problems with an ELSE branch that DROP's if
>it means that in that ELSE branch we don't use or need an item.
>That is part of the algorithm.

Sure, if you need it, you need it.  But if you can avoid it, that's
nicer.

>Here we assume that 1001 is a unique throw code that is reserved for
>this algorithm. I'm not comfortable using -1 as a throw code.

-1 is what ABORT throws.  However, at least in Gforth (and, I expect,
every other competent system) the system does not throw -1 by itself,
and we as programmers do not use ABORT here, so we can use TRUE as
throw-code here and avoid the conversion from TRUE to 1001 and back.

What is more of an issue is if we want to deal with other throw codes
(e.g., user interrupts because it runs for such a long time); we can
deal with that as follows:

: product1? ( n addr u -- f )
    \ is n a product of the numbers in addr u?
    ['] product1 catch dup true <> and throw dup if nip nip nip then ;

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

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

Thread

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

csiph-web