hashes are definitely not future-safe, unfortunately. Robby
On Thu, Jul 25, 2013 at 6:50 PM, Joe Gilray <jgil...@gmail.com> wrote: > Here is an update: > > I rewrote gcd and used a hash-table for the squares check. The hash-table > change sped up the sequential code about 10x! Then I tried using future / > touch and it seems to improve the performance a little, but there is quite > a bit of blocking (on >= and hash-ref) still. > > New code below. > > -Joe > > ; function that searches for progressive numbers for a given range of b > values > (define (find-progressive-num2 b-start b-end b-incr lim ht) > (define (mgcd a b) (if (= b 0) a (mgcd b (modulo a b)))) > (for/sum ([b (in-range b-start b-end b-incr)]) > (let loopa ([a (add1 b)] [suma 0]) > (cond > [(> (mgcd a b) 1) (loopa (add1 a) suma)] > [(>= (* a a a b) lim) suma] > [else > (let loopc ([c 1] [sumc 0]) > (define n (+ (* a a a c c b) (* c b b))) > (cond > [(>= n lim) (loopa (add1 a) (+ suma sumc))] > [(hash-has-key? ht n) (loopc (add1 c) (+ sumc n))] > [else (loopc (add1 c) sumc)]))])))) > > ;(require future-visualizer) > (define (euler141b) > (define lim 1000000000000) > (define ht (make-hash)) > (for ([i (in-range 1 1000000)]) (hash-set! ht (sqr i) 1)) > ; (visualize-futures > (let ([f1 (future (λ () (find-progressive-num2 1 1000 4 lim ht)))] > [f2 (future (λ () (find-progressive-num2 2 1000 4 lim ht)))] > [f3 (future (λ () (find-progressive-num2 3 1000 4 lim ht)))]) > (+ (find-progressive-num2 4 1000 4 lim ht) (touch f1) (touch f2) > (touch f3)))) > > > On Wed, Jul 24, 2013 at 9:46 PM, Robby Findler < > ro...@eecs.northwestern.edu> wrote: > >> You might try places. Writing your own gcd seems straightforward. I'm not >> sure about integer-sqrt?, tho. Maybe you could make a table or something if >> you know there are not that many numbers. >> >> Or maybe someone will adjust the runtime to make those future safe! >> >> Robby >> >> >> On Wed, Jul 24, 2013 at 11:34 PM, Joe Gilray <jgil...@gmail.com> wrote: >> >>> So I should write my own (gcd ) and (square? ) functions? >>> >>> I can try that, but isn't there a simple way to use threads? >>> >>> Thanks, >>> -Joe >>> >>> >>> >>> >>> On Wed, Jul 24, 2013 at 7:47 PM, Robby Findler < >>> ro...@eecs.northwestern.edu> wrote: >>> >>>> When I run this, the future visualizer shows that gcd and >>>> square-number? block the futures. square-number? is implemented in TR and >>>> if you take it, you find that integer-sqrt also blocks the futures. I'm not >>>> sure if those functions can be made to run safely in futures or not. >>>> >>>> Robby >>>> >>>> >>>> On Wed, Jul 24, 2013 at 7:26 PM, Joe Gilray <jgil...@gmail.com> wrote: >>>> >>>>> I have a ProjectEuler problem that I wanted to speed up so I thought I >>>>> would try to speed it up with future / touch. >>>>> >>>>> I tried the following: >>>>> >>>>> ; function that searches for progressive numbers for a given range of >>>>> b values >>>>> (define (find-progressive-num b-start b-end b-incr lim) >>>>> (for/sum ([b (in-range b-start b-end b-incr)]) >>>>> (let loopa ([a (add1 b)] [suma 0]) >>>>> (cond >>>>> [(> (gcd a b) 1) (loopa (add1 a) suma)] >>>>> [(>= (* a a a b) lim) suma] >>>>> [else >>>>> (let loopc ([c 1] [sumc 0]) >>>>> (define n (+ (* a a a c c b) (* c b b))) >>>>> (cond >>>>> [(>= n lim) (loopa (add1 a) (+ suma sumc))] >>>>> [(square-number? n) (loopc (add1 c) (+ sumc n))] >>>>> [else (loopc (add1 c) sumc)]))])))) >>>>> >>>>> ; ProjectEuler problem #141 >>>>> ; n = q * d + r >>>>> ; q/d = d/r = a/b (where a and b are relatively prime) >>>>> ; so d = a*r/b and q = a^2 * r / b^2 >>>>> ; since a and b are coprime r must be divisible by b^2 or r = c*b^2 >>>>> ; substituting: d = a*c*b and q = a^2*c >>>>> ; n = a^3 * c^2 * b + c * b^2 >>>>> (define (euler141) >>>>> (define lim 10000000000) >>>>> (let ([f1 (future (λ () (find-progressive-num 1 1000 2 lim)))]) >>>>> (+ (find-progressive-num 2 1000 2 lim) (touch f1)))) >>>>> >>>>> Unfortunately this runs no faster than the sequential version. I >>>>> tried using the future-visualizer but I couldn't understand what it was >>>>> telling me (I guess some operation is blocking). I also tried finer >>>>> grained threads (one for each value of b), but that did no better. >>>>> >>>>> Can anyone give me some pointers to successfully using future / touch? >>>>> >>>>> Thanks, >>>>> -Joe >>>>> >>>>> ____________________ >>>>> Racket Users list: >>>>> http://lists.racket-lang.org/users >>>>> >>>>> >>>> >>> >> >
____________________ Racket Users list: http://lists.racket-lang.org/users
