Hi,
instead of creating range-unclip, a simpler idea is to use unclip-slice.
this article has some insights regarding unclip vs unclip-slice :
http://docs.factorcode.org/content/article-sequences-slices.html
You can also look at the word next-prime from math.primes
http://docs.factorcode.org/content/word-next-prime,math.primes.html
Usually, we do not add the recursive declaration to non-combinators
recursive words (see
http://docs.factorcode.org/content/word-recursive,syntax.html )
I'm not sure if creating specialized words to unclip (or more generally
create new ranges from previous ranges) is useful, because most of the time
you have one range on which you iterate, not recursive creations of ranges.
You can use unclip-slice, cut-slice etc for that.
Regarding your problem, here's a solution for posterity :)
A very simple prototype implementation could be:
USE: math.primes
: gap ( gap from to -- pair/f )
primes-between dup rest zip [ first2 swap - = ] with find nip ;
It's too simple because it computes all the primes until the end in a
vector and then looks for the gap.
Here's a more complex version with locals to compute primes and check for
the gap on the fly:
:: gap ( gap from to -- pair/f )
from 1 - next-prime dup next-prime
[ 2dup [ swap - gap = ] [ to > ] bi or ]
[ nip dup gap 1 - + next-prime ] until
dup to > [ 2array ] [ 2drop f ] if ;
I think it could be made simpler but didn't try very hard.
Jon
Jon
On Thu, Jan 26, 2017 at 6:59 AM, Alexander Ilin <ajs...@yandex.ru> wrote:
> Hello, fede s!
>
> I'm guessing, unclipping a range (which is a small tuple) produces a huge
> array of integers.
>
> It feels like In this algorithm you don't need any arrays at all, a simple
> iteration would suffice. Plus, you don't need to check all the numbers with
> prime?, only the odd ones, so unlcip is doubly unfit here as the propulsion
> engine.
>
> The idea of doing the special range-unclip is fine. Although the current
> implementation never ends producing the "first" elements, even after the
> range is exhausted. This is due to the possibility of having ranges with
> negative step slot, as in `5 -5 [a,b]`. The regular `unclip` on the other
> hand, throws an error when applied to an empty sequence.
>
> I've looked at the code, and I don't see a way to override the word unclip
> to work on ranges in the more optimal way that you suggest. Maybe some
> specialized words like range-unclip could be added to math.ranges?
>
> 23.01.2017, 02:24, "fede s" <elfeder...@yahoo.com.ar>:
>
> Hi, I noticed this Q in StackExchange http://codereview.
> stackexchange.com/questions/153288/codewars-gap-in-primes
> and attempted a (naive) solution for the problem:
>
> : next-prime ( range -- rest prime? )
> dup empty?
> [ f ]
> [ unclip dup prime?
> [ drop next-prime ] unless
> ] if ; recursive
>
> :: check-gap ( gap prev rest last -- g p r l ? )
> gap prev rest last
> prev last - gap = ;
>
> : (primes-gap) ( gap range last -- n1? n2? )
> swap next-prime dup
> [ check-gap
> [ nip rot drop ]
> [ [ drop ] 2dip (primes-gap) ]
> if ]
> [ 4 ndrop f f ] if ; recursive
>
> : primes-gap ( gap from to -- n1? n2? )
> [a,b] next-prime over
> [ (primes-gap) ]
> [ 3drop f f ] if ;
>
>
> For that version,
> [ 8 3,000,000 4,000,000 primes-gap [ . ] bi@ ] time
> gave 59 seconds on my system, most spent on unclip.
>
> I changed:
>
> : range-unclip ( r -- r' 1st )
> [ first 1 + ] [ last [a,b] ] [ first ] tri ;
>
> : next-prime ( range -- rest prime? )
> dup empty?
> [ f ]
> [ range-unclip dup prime?
> [ drop next-prime ] unless
> ] if ; recursive
>
> which gave only "Running time: 0.000342938 seconds"
>
> Factor 0.98 x86.64 (1777, heads/master-ed29fbd93f, Mon Aug 8 20:45:47
> 2016)
> [Microsoft Visual C++ 190023506] on windows 7
>
> I know there have been some changes since then, and that I'm probably
> doing things in a very sub-optimal way, but thought that there may still be
> something of value here.
>
>
>
>
> ---=====---
> Александр
>
>
> ------------------------------------------------------------
> ------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, SlashDot.org! http://sdm.link/slashdot
> _______________________________________________
> Factor-talk mailing list
> Factor-talk@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
>
------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
