I'll be more explicit here about what these computations tell me about
mzscheme's implementation of bignums and rationals and mzscheme's
integration of gmp into its runtime library. I haven't looked much at
mzscheme's code; perhaps my comments will help mzscheme and other
implementors with their runtime implementations.
> Like I said, this is code from some notes to tell math students how muchSo far, so good. Gambit is faster, but not by much.
> different operations cost (among other things). Notes are at the bottom.
> Formula CPU times (ms)
> (expt 3 1000000) ; a 930 4700
> (* a a) ; c 1170 3150Here things start to look strange. mzscheme's multiplication is
faster than its exponential, but in Gambit-C it's slower. We'll get
back to this later.
> (* a b) ; 1640 4660Similar effect, but smaller.
> (quotient c a) ; 6960 10780Nothing too strange here, but there is a factor of < 3 in Gambit and >
> (sqrt c) ; 14080 57240
5 in mzscheme comparing (sqrt c) to (quotient c a), so it seems that
mzscheme's sqrt implementation could be improved.
> (fib 100000) ; a, note 1 4280 7560No surprises.
> (fib 100001) ; b 4450 7790
> (gcd a b) ; 27580 88780gcd is based on a lot of quotients, but here the gcd times for
> (gcd a b) ; a=3^100000, b=2^100000 23380 56230
Gambit-C are < 4 times (quotient c a), and in mzscheme they can be > 8
times (quotient c a), so it seems again that mzscheme's gcd code is
not tremendously good.
> (expt1 3 1000000) ; note 2 920 1770These two are interesting. Here we have an exponential running in the
> (expt2 3 1000000) ; note 3 6510 6290
interpreter (expt1) that's almost three times as fast as mzscheme's
compiled runtime version of expt. This shouldn't happen; mzscheme's
integer exponential should at the least be replaced by expt1.
> (* a a) ; a=3^1000000 1180 2950A factor of 10 between a Scheme bignum implementation (Gambit) and a
> (expt 10 10000000); a 42770 486200
compiled C bignum implementation (mzscheme) should not be acceptable.
I can't tell why this arises, except perhaps that mzscheme's basic
expt routine is not based on expt1.
> (expt 2 10000000) ; b 990 70300Here we have a factor of 70 difference in speed. This tells me that
mzscheme does not special case either multiplication by a number with
many low-order zero bits or exponential of such a number. This is not
really acceptable in a runtime that goes to great lengths to use fast
algorithms for other operations.
I was surprised by this a few months ago with the Gambit-C bignum
I took the opportunity at that time to add this to Gambit. This
> (quotient a b) ; 140 3169230Here there is a time difference of over 2000; dividing by a number
with many low-order bits zero should also be fast using a grade school
algorithm. And this is useful for fixed-point arithmetic computations
to high precision.
> (expt 2/3 10000) ; a 0 130These two, where mzscheme is about 40 times slower than Gambit, tell
> (expt 3/5 10000) ; b 10 370
me that the mzscheme runtime probably doesn't use the fact that
(expt p/q n) = (make-rational (expt p n) (expt q n))
where you don't have to do a gcd to get things in lowest form. My
> (* a b) ; 280 390Doesn't tell you much, but coupled with the previous two means that
mzscheme's runtime probably does not use the formula
(* p/q r/s) => (make-rational (* (quotient p (gcd p s))
and instead uses the naive
(* p/q r/s) => (make-rational (quotient (* p r) (gcd (* p r) (* q s)))
> (fib 1000) ; note 4 10 2790This time difference of about 300 tells me that mzscheme does not use
(+ n p/q) = (make-rational (+ p (* n q))
and no gcd is necessary. Again, this is very useful in computing
> (factorial 10000) ; note 5 1630 1210I'm not tremendously happy with Gambit's performance here; before
> (partial-factorial 0 10000) ; note 6 170 160
> (binary-splitting-compute-e 1000) ; note 7 980 400
> (naive-compute-e 1000) ; note 8 142970 51520
> (binary-splitting-compute-pi 1000) ; note 9 2070 1130
looking at the runtime, however, I'd like to compile both to see if
the interpreter speed is masking the time of the runtime. But I don't
really want to bother figuring out how to compile code in mzscheme.
> (pi-brent-salamin) ; n. 10, beta^k=10^1000000 1345230Here's another small point related to this computation---I looked at
> (pi-brent-salamin) ; beta^k=2^33219 902040
the mzscheme runtime to see if exact integer square root was available
as a separate routine. It is, as a C routine, but there doesn't seem
to be an associated scheme routine. This is an important operation,
is invoked in (sqrt n) if n is a perfect square, and if you're going
to have a fast implementation of it, which mzscheme has, it should be
available separately. (Perhaps it is, nobody answered when I asked
how to do exact integer square root in mzscheme.)
So I would characterize mzscheme's bignum and ratnum implementation as
This, to me, indicates a design problem that cannot be fixed just by
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.