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
