On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote:
2014-02-27 15:23 GMT+01:00 Cristian Baboi <cristian.ba...@gmail.com>:
Hello,
I recently used racket for a math assignment in a crypto class because of
big numbers support. Others used python, java, haskell and bragged with
short execution times. Is there anything I can do to speed up the following
code or is my computer too old ?
First make sure you use the same algorithm. Post it!
Second: (modulo (* l gm1) p) looks inefficient.
If l and gm1 are large, then it is more efficient
to reduce modulo p first, then multiply, then reduce again.
Since all your calculations are modulo p, you can use with-modulus and mod*.
Third: When benchmarking turn off display and use racket (not DrRacket).
Fourth: Use Racket hash tables rather than rnrs ones. (I haven't looked, so
I am unsure how they are implemented - maybe they are slower - maybe they
are the ok)/
Without changing the algorithm, I get this:
#lang racket
(require math)
(require rnrs/hashtables-6)
(define p
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)
(define g
11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568)
(define h
3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333)
(define B (expt 2 20))
(with-modulus p
(define gB (modexpt g B))
(define gm1 (modular-inverse g p))
(define (mx x0 x1) (+ (* B x0) x1))
(define (hash n ht l x1)
(cond
[(> n 0) (hashtable-set! ht l x1)
(when (< x1 10) (displayln (list x1 l)))
(hash (- n 1) ht (mod* l gm1) (+ x1 1))]
[else (hashtable-set! ht l x1)
ht]))
(define (htbl) (hash (- B 1) (make-eqv-hashtable B) h 0))
(define (gol) (make-eqv-hashtable B))
(define (caut n ht l x0)
(cond
[(> n 0) (define x1 (hashtable-ref ht l -1))
(when (< x0 10) (displayln (list x0 l)))
(if (eqv? x1 -1)
(caut (- n 1) ht (mod* l gB) (+ x0 1))
(cons x0 x1))]
[else (define x1 (hashtable-ref ht l -1))
(if (eqv? x1 -1)
(cons -1 -1)
(cons x0 x1))]))
(define run (caut (- B 1) (htbl) 1 0))
(define x (mx (car run) (cdr run)))
(displayln x))
I'm not sure what the hash tables are for, but they're apparently the
culprit. When I removed them, I got 1048575 in a few seconds. (I had
`hash' return `x1', which I passed to `caut' instead of a hash table.)
For this algorithm, is it necessary to keep all the intermediate values
computed by `hash' in a hash table?
Neil ⊥
____________________
Racket Users list:
http://lists.racket-lang.org/users
