Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.forth > #53579
| From | anton@mips.complang.tuwien.ac.at (Anton Ertl) |
|---|---|
| Newsgroups | comp.lang.forth |
| Subject | Re: Challenge for Christmas |
| Date | 2016-12-28 08:19 +0000 |
| Organization | Institut fuer Computersprachen, Technische Universitaet Wien |
| Message-ID | <2016Dec28.091930@mips.complang.tuwien.ac.at> (permalink) |
| References | <26197516-a481-4262-a604-5cae2c7dc49a@googlegroups.com> <2016Dec27.170123@mips.complang.tuwien.ac.at> <o3uaqo$86i$1@cherry.spenarnc.xs4all.nl> <2016Dec27.190859@mips.complang.tuwien.ac.at> <o3ueg3$8hg$1@cherry.spenarnc.xs4all.nl> |
albert@cherry.spenarnc.xs4all.nl (Albert van der Horst) writes:
>In article <2016Dec27.190859@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.
And here's the version with memoization:
variable memokey
: memo-insert ( value key wid -- )
get-current >r
set-current memokey ! memokey cell nextname constant
r> set-current ;
: product-table ( -- wid )
table true 1 2 pick memo-insert ;
: memo-lookup ( key wid -- value true | false )
>r memokey ! memokey cell r> search-wordlist dup if
swap execute swap then ;
defer productm1 ( n addr u -- f )
: productm? { n addr u wid -- f }
n wid memo-lookup if
exit then
n addr u wid productm1
dup n wid memo-insert ;
:noname { n addr u wid -- f }
\ is n a product of the numbers in addr u?
addr u cells + addr ?do
n i @ /mod { n1 } 0= if
n1 addr u wid productm? if
true unloop exit then
then
cell +loop
false ;
is productm1
create z 4 , 6 , 9 ,
product-table constant z-table
cr 3948651115268014080 z 3 z-table productm? . .s
>>>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).
>
>So you say that the number of nodes cannot grow exponentionally in
>the dimension of the set. Not convinced.
>
>>
>>>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.
>
>P_i are different prime numbers. All those prime numbers are assumed
>to divide the number under investigation. O(n) means the size of the
>set, note that the number under investigation is without limit.
>Maybe you should state what exactly you mean by O(n) in this case.
The input number is 5*6^n, so this is the n in O(n). For the meaning
of the O(...)-Notation, see Wikipedia.
For 5*6^11, the memo table contains 73 entries at the end; for 5*6^22,
266 entries; 266/73=3.64, so it's a little less than quadratic.
As for your p_i etc. stuff, I still cannot follow you. n is the size
of which set?
And here are the entries of the memo-table for 5*6^8; the entries are
shown in reverse order of insertion (i.e., the bottom entry (1) was
inserted first):
8398080 0
933120 0
103680 0
11520 0
1280 0
1399680 0
155520 0
17280 0
1920 0
2099520 0
233280 0
25920 0
2880 0
320 0
349920 0
38880 0
4320 0
480 0
524880 0
58320 0
6480 0
720 0
80 0
87480 0
9720 0
1080 0
120 0
131220 0
14580 0
1620 0
180 0
20 0
21870 0
2430 0
270 0
30 0
32805 0
3645 0
405 0
45 0
5 0
1 -1 ok
- 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
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