Marc:
I have some ideas for speeding up some of the algorithms in _num.scm, but my first attempt at something is going awry and I can't fathom it; I'm beginning to thing that there might be a compiler error (quelle horreur!), or an error in reporting how much memory is allocated.
I've written a new naive-div, called, oddly enough, naive-div-new, that is supposed to allocate much less memory when two large bignums of roughly the same size are divided. It relies on a new routine, ##bignum.arithmetic-shift-into!.
naive-div-new has two new arguments, to say whether we want to keep (not overwrite) the dividend and whether we need a quotient. If we don't need a quotient and we're allowed to overwrite the dividend, then I think the routine should allocate 24 bytes on a 64-bit machine with 32-bit mdigits. It calls ##bignum.normalize!, but that doesn't allocate any memory.
However, time is reporting that 240 bytes are allocated. Even accounting for the fact that time's report might double the number of bytes allocated, as explained in your previous e-mail, I don't see anywhere near 240 bytes allocated.
So, can you help a fella out here and tell me where I'm allocating this phantom memory?
Brad
Here's a script showing some issues:
(load "formarc")
"/Users/lucier/programs/gambit/gambit-1/gambit/shift/formarc.o1"
(define a (expt 2 250)) (define b (expt 2 240)) (define c (##bignum.make (##bignum.adigit-length a) a #f)) (define d (##bignum.make (##bignum.adigit-length b) b #f)) (time (naive-div-new c d #f #f))
(time (naive-div-new c d #f #f)) 0 ms real time 0 ms cpu time (0 user, 0 system) no collections 240 bytes allocated no minor faults no major faults (#f . 0)
(define result (##bignum.make 2 #f #f)) (##bignum.normalize! (time (##bignum.arithmetic-shift-into! a -200 result)))
(time (##bignum.arithmetic-shift-into! a -200 result)) 0 ms real time 0 ms cpu time (0 user, 0 system) no collections no bytes allocated no minor faults no major faults 1125899906842624