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

2014-02-28 Thread Matthias Felleisen
Thanks Cristian. Man a full day away from my email and good things happen. I should do this more often. On Feb 28, 2014, at 2:48 PM, Neil Toronto wrote: > Well done. I would never have thought of compiling with CGC. > > Neil ⊥ > > On 02/28/2014 11:46 AM, Matthew Flatt wrote: >> Cristian d

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

2014-02-28 Thread Neil Toronto
Well done. I would never have thought of compiling with CGC. Neil ⊥ On 02/28/2014 11:46 AM, Matthew Flatt wrote: Cristian determined that Racket really was was much slower for the program on Windows than on other platforms, and he also noticed that RacketCGC was significantly faster. That info

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

2014-02-28 Thread Matthew Flatt
Cristian determined that Racket really was was much slower for the program on Windows than on other platforms, and he also noticed that RacketCGC was significantly faster. That information pointed me to a simple inefficiency in the way Racket allocated for GMP with the default collector. I've push

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

2014-02-28 Thread Cristian Baboi
On Thu, 27 Feb 2014 23:29:36 +0200, Eric Dong wrote: I have a 2.4 GHz machine (n-core does not matter; Racket only uses one core), and I get cpu time: 25228 real time: 25202 gc time: 18840 on Linux x86. Are you sure you ran the "Rackety" program Matthias posted? On Linux x64 Debian 6 compil

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

2014-02-27 Thread Eric Dong
On my computer the Java program takes 7 seconds. So you should be seeing a 3x slowdown with Racket. You seem to see a 20x slowdown. This is very strange. How much RAM do you have? Racket performs very poorly when its memory is swapped out to disk. To the rest of the list: is there any inefficienc

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

2014-02-27 Thread Jens Axel Søgaard
Is it this algorithm? http://en.wikipedia.org/wiki/Baby-step_giant-step 2014-02-27 16:38 GMT+01:00 Jens Axel Søgaard : > 2014-02-27 16:33 GMT+01:00 Cristian Baboi : First make sure you use the same algorithm. Post it! >> >> The same algorithm as the algorithm scheme was described in the ass

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

2014-02-27 Thread Matthias Felleisen
Can you send out someone's Python algorithm that runs so much faster? And can you compare them on the same machine because it really is apples vs oranges thus far. -- Matthias On Feb 27, 2014, at 11:21 AM, "Cristian Baboi" wrote: > În data de Thu, 27 Feb 2014 18:07:58 +0200, Sam Tobin-Ho

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

2014-02-27 Thread Cristian Baboi
În data de Thu, 27 Feb 2014 18:07:58 +0200, Sam Tobin-Hochstadt a scris: On Thu, Feb 27, 2014 at 11:03 AM, Cristian Baboi wrote: În data de Thu, 27 Feb 2014 17:40:16 +0200, Matthias Felleisen a scris: $ racket yourprogram.rkt cpu time: 21269 real time: 21571 gc time: 14551 The Rackety

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

2014-02-27 Thread Sam Tobin-Hochstadt
On Thu, Feb 27, 2014 at 11:03 AM, Cristian Baboi wrote: > În data de Thu, 27 Feb 2014 17:40:16 +0200, Matthias Felleisen > a scris: > > >> >> $ racket yourprogram.rkt >> cpu time: 21269 real time: 21571 gc time: 14551 >> >> The Rackety version. > > > DrRacket on my computer > cpu time: 218495 rea

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

2014-02-27 Thread Cristian Baboi
În data de Thu, 27 Feb 2014 17:40:16 +0200, Matthias Felleisen a scris: $ racket yourprogram.rkt cpu time: 21269 real time: 21571 gc time: 14551 The Rackety version. DrRacket on my computer cpu time: 218495 real time: 225567 gc time: 176686 Racket Users list: http:

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

2014-02-27 Thread Cristian Baboi
În data de Thu, 27 Feb 2014 17:41:06 +0200, Neil Toronto a scris: On 02/27/2014 08:33 AM, Cristian Baboi wrote: În data de Thu, 27 Feb 2014 17:04:51 +0200, Neil Toronto a scris: On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote: 2014-02-27 15:23 GMT+01:00 Cristian Baboi : Hello, Your

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

2014-02-27 Thread Eric Dong
This would be highly anomalous. Python is usually at least 10 times slower than Racket for most tasks. On Thu, Feb 27, 2014 at 10:49 AM, Cristian Baboi wrote: > În data de Thu, 27 Feb 2014 17:41:06 +0200, Neil Toronto < > neil.toro...@gmail.com> a scris: > > > On 02/27/2014 08:33 AM, Cristian B

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

2014-02-27 Thread Neil Toronto
On 02/27/2014 08:33 AM, Cristian Baboi wrote: În data de Thu, 27 Feb 2014 17:04:51 +0200, Neil Toronto a scris: On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote: 2014-02-27 15:23 GMT+01:00 Cristian Baboi : Hello, I recently used racket for a math assignment in a crypto class because of big n

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

2014-02-27 Thread Matthias Felleisen
$ racket yourprogram.rkt cpu time: 21269 real time: 21571 gc time: 14551 The Rackety version. #lang racket (require math) (define (main) (define run (caut (- B 1) (htbl) 1 0)) (displayln (mx (car run) (cdr run (define p 134078079299425970995740249982058461274793658205923933777235614

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

2014-02-27 Thread Cristian Baboi
În data de Thu, 27 Feb 2014 17:33:32 +0200, Cristian Baboi a scris: 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 red

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

2014-02-27 Thread Jens Axel Søgaard
2014-02-27 16:33 GMT+01:00 Cristian Baboi : >>> 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. Can you post the pseudo code? /Jens Axel Racket Users list:

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

2014-02-27 Thread Cristian Baboi
În data de Thu, 27 Feb 2014 17:04:51 +0200, Neil Toronto a scris: On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote: 2014-02-27 15:23 GMT+01:00 Cristian Baboi : Hello, I recently used racket for a math assignment in a crypto class because of big numbers support. Others used python, java,

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

2014-02-27 Thread Neil Toronto
On 02/27/2014 07:55 AM, Jens Axel Søgaard wrote: 2014-02-27 15:23 GMT+01:00 Cristian Baboi : 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

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

2014-02-27 Thread Jens Axel Søgaard
2014-02-27 15:23 GMT+01:00 Cristian Baboi : > 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

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

2014-02-27 Thread Cristian Baboi
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 ? The code solves g^x=h mod p