On 2013-01-12, at 7:40 PM, Bradley Lucier lucier@math.purdue.edu wrote:
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.
After examining your program, I notice that the call to ##cons at the end of the code is in a loop (and is called 4 times). My guess is that you expected this call to ##cons to only happen once. This is probably because you did not nest your loops properly, so the call to ##cons which you expect to be a tail call, actually isn't.
Marc