[racket] slow g^x=h mod p meet in the middle code

On 02/27/2014 08:33 AM, Cristian Baboi wrote:
> În data de Thu, 27 Feb 2014 17:04:51 +0200, Neil Toronto
> <neil.toronto at gmail.com> a scris:
>
>> On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote:
>>> 2014-02-27 15:23 GMT+01:00 Cristian Baboi <cristian.baboi at 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!
>
> The same algorithm as the algorithm scheme was described in the assignment.
> Minor details can be different.
>
>>> 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.
>
> Well, gm1 and gB are already reduced modulo p ...
> The only one who is not is l which is lower than B which is lower than p.
>
>>> Since all your calculations are modulo p, you can use with-modulus
>>> and mod*.
>
> Makes no difference.
>
>>> Third: When benchmarking turn off display and use racket (not DrRacket).
>
> Why? I don't print much.
>
>>> 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)/
>
> I don't know how. What keywords should I search for in the documentation ?

The terms "hash" or "hash table" would have worked. But "hashtable" 
points almost exclusively to R6RS hash tables, which looks like a flaw 
in the documentation to me.

>>> 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.)
>
> They are for "meet in the middle". The "caut" stops when a match is found.
> hash compute one "hash" table and "caut" use it.
>
>> For this algorithm, is it necessary to keep all the intermediate
>> values computed by `hash' in a hash table?
>
> Yes! The correct answer is 375374217830.

Ah, I see where I went wrong.

> Your changes give the same running time as my version: ~ 3 min on my
> computer in DrRacket.

How fast are your beatnik friends' implementations?

Neil ⊥