The difficulty I had with this problem was generating
all the required primes in a reasonable time. I resorted
to using PARI-GP to produce the 100000 primes
specified. My timing tests suggest that it would take
well over an hour in J:
timer'10{.((4&p:)&.(+&100000000000000))^:(>:i.1000) 0'
47.335 | 31 67 97 99 133 139 169 183 261 357
Perhaps there's a better way to do that.
As for the fibonacci part, I think you need to think again.
I used a combination of two different techniques, both
described somewhere within the J essays, if I recall
correctly. Reading the requisite list of primes from a file
produced by PARI-GP, the fibonacci part in J took about
two minutes, fast enough for my purposes!
Mike
On 28/02/2011 14:46, David Ward Lambert wrote:
> Problem: fibn vector_length_100thousand runs too long (10 hours and
> running).
> 35% of my memory& all swap is available.
>
> The analysis shown indicates the problem could run in well under an
> hour.
> Did memoize decide the task is impossible?
> Discarding the M. cache every now and then might help.
> References: ProjectEuler #304, Dijkstra's Fibonacci formula
> http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html#exact
>
> Thanks, Dave.
>
>
> $ jconsole
> NB. Least significant figures of large Fibonacci numbers.
>
> (9!:12 ,&(' '&,@":) 9!:14)'' NB. unix j7
> 5 j701/2011-01-10/11:25
>
> ts=: 6!:2, 7!:2@]
> int =: =<.
>
> fibn_test =: +:@(<&2) + 2&|
>
> (,. fibn_test)i.6
> 0 2
> 1 3
> 2 0
> 3 1
> 4 0
> 5 1
>
> fibn_even_term =: fibn@-: * +:@fibn@<:@-: + fibn@-:
> fibn_odd_term =: (fibn@<: +&*: fibn)@-:@>:
> fibn =: (1234567891011x |
> fibn_even_term`fibn_odd_term`0:`1:@.fibn_test)M."0
>
> a=: 1!:1<'e304.primes'
> #primes=:".' '(I.LF=a)}a
> 100000
> q: primes{~5?#primes
> 100000001643887
> 100000000146283
> 100000003087511
> 100000000129571
> 100000000933793
>
> NB.-------------------KEY TIMING RESULT--------------------
> ts'fibn 10{.primes' NB. could take well under an hour all
> 0.003889 142592
>
> fibn i.10 NB. fibn is possibly correct
> 0 1 1 2 3 5 8 13 21 34
>
> NB. without M.
> fibn=:(1234567891011x |
> fibn_even_term`fibn_odd_term`0:`1:@.fibn_test)"0
>
> ts'fibn {.primes'
> longer than I'll wait.
>
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
