[racket] (floor (/ ....))

From: Bradley Lucier (lucier at math.purdue.edu)
Date: Mon Jun 10 12:18:59 EDT 2013

> FWIW, I would have at least written:
>         ((qty (in-range 0 (add1 (min (floor (/ weight-left weight))
>                                      (floor (/ volume-left volume)))))))

I have now seen the

(floor (/ a b))

idiom a number of times, and wonder why people prefer it to

(quotient a b)

Normally, to calculate (/ a b) where a and b are exact integers requires 
one to calculate (gcd a b) to put the fraction into lowest terms 
p/q=(quotient a (gcd a b))/(quotient b (gcd a b)); then, to calculate 
(floor p/q), one must calculate (quotient p q).

For large integers of size  $N$ bits, (gcd a b) takes $O(N\log^2(N))$ 
fixnum operations, where quotient takes $O(N\log N)$ operations.  This 
assumes Fourier-based methods for bignum multiplication; for more direct 
methods, the difference in operation count is larger.

In any case, the (floor (/ ...)) idiom takes noticeably more time than 
(quotient ...).  If one knows that a and b are positive integers, they 
give the same results.

This is an argument not to use (floor (/ ...)).  Are there arguments in 
favor of this idiom?


Posted on the users mailing list.