egallesio / STklos

STklos Scheme
http://stklos.net
GNU General Public License v2.0
69 stars 17 forks source link

Optimize `double2rational` (and `inexact->exact`) #534

Closed jpellegrini closed 1 year ago

jpellegrini commented 1 year ago

And consequently, exact.

When the full GMP is available, we just turn the double into an mpq_t variable and get back the numerator and denominator.

Much faster than the current code:

(let ((a 3.1)
      (b #f))
  (time
   (repeat 5_000_000
           (set! b (exact a))))
  b)

Current code: 14535.114 ms
This patch:    2461.519 ms  ==> Actually, 2105 ms, after using mpz_clear

This uses conditional compilation, since the mini-GMP does not have rationals.

There is another PR (#524) which also adds a primitive %stklos-has-gmp?

edit: I also added mpz_clear to several places in number.c. It's of course required (we were leaking some memory), and also seems to make the code faster.

edit, again: I also noticed a speedup in expt with exact exponent.

jpellegrini commented 1 year ago

The results from double2rational, and from exact, are the same as before, and the same as most Schemes. There is only one Scheme which does something different, which is Gauche, using a continued fraction expansion of the number:

3.1 == most Schemes exact ==> 6980579422424269/2251799813685248
3.1 == Gauche exact ==> 31/10

Maybe we can try to do that too, later. But I think this PR is already a nice enhancement, isn't it?

egallesio commented 1 year ago

Merged this one too.The last one for today :smile:

Thanks.

egallesio commented 1 year ago

Not merged, in fact, since I have sync problems between machine. Will merge later.