Re: Challenge for Christmas

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From	anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups	comp.lang.forth
Subject	Re: Challenge for Christmas
Date	Tue, 27 Dec 2016 18:08:59 GMT
Organization	Institut fuer Computersprachen, Technische Universitaet Wien
Lines	40
Message-ID	<2016Dec27.190859@mips.complang.tuwien.ac.at> (permalink)
References	<26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com> <2016Dec27.141206@mips.complang.tuwien.ac.at> <o3u33l$7nk$1@cherry.spenarnc.xs4all.nl> <2016Dec27.170123@mips.complang.tuwien.ac.at> <o3uaqo$86i$1@cherry.spenarnc.xs4all.nl>
Injection-Info	mx02.eternal-september.org; posting-host="51431ac844d180f11178c8caa7215e4d"; logging-data="25694"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+QDyPNNP0TcYWAkXDolvsT"
X-newsreader	xrn 10.00-beta-3
Cancel-Lock	sha1:BWbUW0BOFUemgCi9RL4wnSHOAGU=
Xref	csiph.com comp.lang.forth:53564

Show key headers only | View raw

albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>In article <2016Dec27.170123@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>
>>One can speed up these cases to have an algorithmic complexity of O(n)
>>by using memoization; that makes the code more complex, however.
>
>I don't think so. I'm pretty sure the worst case behaviour of this
>problem is pretty bad. Say NP-complete.

Definitely polynomial, but O(n) is too optimistic indeed.  It's linear
in the number of nodes in the search graph (i.e., in the number of
unique nodes in the search tree).  For the 4^i*6^j*9^k example, and
5*6^n as input number, I expect at worst O(n^3) unique nodes (that's
the maximum number of different combinations of i,j,k that gives a
number below 6^n), but probably more like O(n^2) (because many
different combinations of i,j,k give the same number).

>Look at this example.
>Imagine a set of 2*p_i and a number that has 3 factors
>2. All combination of 3 has to be tried. And that is just one prime.
>With 2^16 it becomes pretty bad.

You lost me here.  What is p_i? Do you mean the number 8?  Why would
all combinations of 3 have to be tried?  3 is not a factor of 8, so it
is eliminated right away.

>A useful and straightforward optimisation is throwing all numbers
>out of the set that are not a divisor of n beforehand.

That just saves a constant factor.  Numbers that are not a divisor of
n always fail the divisibility test, and don't have any descendents in
the search tree.

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

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