repeated division returning an integer?

[James Cloos]

given (declare (integer dividend divisor)), this works:

(do (( n dividend (/ n divisor))) ((typep n 'ratio) (* divisor n)))

but is there a way to return n /before/ the division which return a ratio?

-JimC
--
James Cloos <cl...@jhcloos.com> OpenPGP: 0x997A9F17ED7DAEA6

[Tom Russ]

On Sunday, May 21, 2023 at 6:48:56 PM UTC-7, James Cloos wrote:
> given (declare (integer dividend divisor)), this works:
>
> (do (( n dividend (/ n divisor))) ((typep n 'ratio) (* divisor n)))

How about

(do ((n dividend (/ n divisor))) ((not (zerop (rem n divisor))) n))

Just make sure you don't pass 0 as either of the inputs....
There may also be a more direct way to compute this, but I can't think of one at the moment.

[Tom Russ]

Of course, if you goal is efficiency, my quick solution actually has more divisions in it
than the original formulation. Since it tests REM (a division) at each step and then
if it doesn't exit performs essentially the same division once again.

There would be other loop formulations using additional variables and more logic that
could preserve the previous value of N and return it, saving a multiplication. But I don't
think you can avoid the extra division.

[Alan Bawden]

Tom Russ <tar...@google.com> writes:

On Monday, May 22, 2023 at 11:16:13 AM UTC-7, Tom Russ wrote:
> On Sunday, May 21, 2023 at 6:48:56 PM UTC-7, James Cloos wrote:
> > given (declare (integer dividend divisor)), this works:
> >
> > (do (( n dividend (/ n divisor))) ((typep n 'ratio) (* divisor n)))
> How about
>
> (do ((n dividend (/ n divisor))) ((not (zerop (rem n divisor))) n))
>
> Just make sure you don't pass 0 as either of the inputs.... There
> may also be a more direct way to compute this, but I can't think of
> one at the moment.

Of course, if you goal is efficiency, my quick solution actually has
more divisions in it than the original formulation. Since it tests
REM (a division) at each step and then if it doesn't exit performs
essentially the same division once again.

I think the function you are looking for is the two-argument version of
FLOOR, which returns both the quotient and the remainder.

- Alan

[Kaz Kylheku]

On 2023-05-22, James Cloos <cl...@jhcloos.com> wrote:
> given (declare (integer dividend divisor)), this works:
>
> (do (( n dividend (/ n divisor))) ((typep n 'ratio) (* divisor n)))
>
> but is there a way to return n /before/ the division which return a ratio?

One possibility: keep dividing until we get something with a denominator
that isn't 1:

(defun strip-factor (integer factor)
(do ((prev integer next)
(next integer (/ prev factor)))
((not (eql 1 (denominator next))) prev)))

Another one: we use the truncate function, which returns two values:
quotient and remainder. We stop when we get a nonzero remainder, and
use the previous value:

(defun strip-factor (integer factor)
(loop with quotient and remainder
do (setf (values quotient remainder) (truncate integer factor))
until (not (zerop remainder))
do (setf integer quotient)
finally (return integer)))

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazi...@mstdn.ca

[James Cloos]

thanks for the replies.

very helpful.

i should have thought of using truncate though...