Integer division with rounding

[m35]

I coincidentally happen to be struggling with rounding issues at the same time as http://newlispfanclub.alh.net/forum/viewtopic.php?f=16&t=3611">this topic pops up. I don't want to hijack that thread any further, plus my issue is a little different, so thus this thread.



I'm trying to write a generic algorithm for integer-only (no floating-point involved) division that includes rounding (rounding 0.5 away from zero) and avoids overflow. The function should basically work like this floating-point equivalent.

Code Select Expand

(define (int-div-round1 i1 i2)
  (round (div i1 i2))
)
I know that the typical solution is to add half the divisor to the numerator

Code Select Expand

(define (int-div-round2 i1 i2)
  (setq half2 (/ i2 2))
  (/ (+ i1 half2) i2)
)
Of course this version has two major problems:

(1) only accurate when i1 and i2 have the same sign (i.e. both positive or both negative)

(2) can overflow



#1 isn't too difficult to fix, but I haven't found an approach that avoid #2. All my brainstorming, trial-and-errors, and Googling have failed me.



Maybe a clever newLISPer has some thoughts?

[Lutz]

Perhaps not solving either #1 or #2 but giving a little efficiency boost:

Code Select Expand

(define (int-div-round i1 i2)
(/ (+ i1 (>> i2)) i2))


the shift will maintain the sign too. The danger of overflow only exists for the addition part, but if you limit i1 to being smaller than (>> i1) then overflow can never occur and you still have 63 bits of precision because integers in newLISP are 64-bit even on the normal 32-bit compile. You also would have to make sure i2 isn't 0 to guard against division-by-zero exceptions.