chiles@chiles.slisp.cs.cmu.edu (Bill Chiles) (05/30/90)
This is a general query of how to do 64-bit by 32-bit division when a
machine only gives you a 32-bit by 32-bit instruction. At first I was
shocked that MIPS didn't offer this since a 32-bit by 32-bit multiply
potentially results in a 64-bit result, and I expected to be able to
reverse the operation. I suspect all of their intensive profiling has
revealed that C programs only ever divide a long integer by a long integer
at best. I wonder if they profiled any languages that support infinite
precision integer arithmetic? Maybe they did, and what they found is that
conventional computing almost never requires a 64x32 divide.
Some languages and number packages do support this stuff and require a
64x32 divide for completeness, even if profiling dictates that it isn't
worth providing such an instruction. This assumes the implementation has
chosen 32-bit digits values.
Has anyone implemented this on the MIPS? Is there some theory I'm missing
that makes 64x32 divide fairly simple given a 32x32 divider? Given a
routine
DIVIDE x1 x2 y --> q, r
DIVIDE could make the following assumptions:
1] x1 is the high 32 bits of a 64-bit positive integer.
2] x2 is the low 32 bits of a 64-bit integer.
3] y is positive and sufficiently large to adhere to your favorite
infinite precision integer divide algorithm.
4] q and r are unsigned 32-bit quantities.
I'm curious to know what MIPS has seen profiling programs regarding the use
of 64x32 bit division if anyone there can report this kind of information.
Billok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (05/31/90)
In article <9462@pt.cs.cmu.edu>, chiles@chiles.slisp.cs.cmu.edu (Bill Chiles) writes: > This is a general query of how to do 64-bit by 32-bit division when a > machine only gives you a 32-bit by 32-bit instruction. [...] > Some languages and number packages do support [bignums] and require a > 64x32 divide for completeness, even if profiling dictates that it isn't > worth providing such an instruction. If you want to implement bignums, you can treat a bitstring as a sequence of 16-bit "bigits" just as easily as you can treat it as 32-bit "bigits". In fact, you can do your addition and subtraction in 32-bit chunks and your division in 16-bit chunks. All you need, then, is 32-bit/16-bit, and the existing 32-bit/32-bit will give you that. Isn't code for a double-precision division in Knuth vol 2? A certain popular RISC hasn't _any_ division instruction... -- "A 7th class of programs, correct in every way, is believed to exist by a few computer scientists. However, no example could be found to include here."
mash@mips.COM (John Mashey) (06/02/90)
In article <9462@pt.cs.cmu.edu> chiles@cs.cmu.edu writes: >This is a general query of how to do 64-bit by 32-bit division when a >machine only gives you a 32-bit by 32-bit instruction. At first I was >shocked that MIPS didn't offer this since a 32-bit by 32-bit multiply >potentially results in a 64-bit result, and I expected to be able to >reverse the operation. I suspect all of their intensive profiling has >revealed that C programs only ever divide a long integer by a long integer >at best. I wonder if they profiled any languages that support infinite >precision integer arithmetic? Maybe they did, and what they found is that >conventional computing almost never requires a 64x32 divide. Whether they require it or not, in general, it's something hard to specify from most languages, and so of coruse, it never shows up in thr profiles. Although I think it was discussed, it dropped out as a possibility very early [like, 1Q85]. However, in any case, it turns out that 64/32->32 requires a 64-bit wide datapath, which would have caused serious chip layout problems in the middle of something where every other integer thing was 32-wide. (32/32->32 is OK, and so is 32*32->64, i.e., / is a worse problem than *). -- -john mashey DISCLAIMER: <generic disclaimer, I speak for me only, etc> UUCP: mash@mips.com OR {ames,decwrl,prls,pyramid}!mips!mash DDD: 408-524-7015, 524-8253 or (main number) 408-720-1700 USPS: MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086