Integer long division: Difference between revisions

From Rosetta Code
Content added Content deleted
(Created the task of Long Division)
 
Line 17: Line 17:
; ($/ 1 17) => 588235294117647 ; 16
; ($/ 1 17) => 588235294117647 ; 16
(assert (and (integerp a) (integerp b) (not (zerop b))))
(assert (and (integerp a) (integerp b) (not (zerop b))))
(do* (c (i0 (1+ (max (factor-multiplicity b 2) (factor-multiplicity b 5)))) ; the position which marks the beginning of the period
(do* (c
(i0 (1+ (max (factor-multiplicity b 2) (factor-multiplicity b 5)))) ; the position which marks the beginning of the period
(r a (* 10 r)) ; remainder
(r a (* 10 r)) ; remainder
(i 0 (1+ i)) ; iterations counter
(i 0 (1+ i)) ; iterations counter
Line 25: Line 24:
(multiple-value-setq (c r) (floor r b))
(multiple-value-setq (c r) (floor r b))
(princ c) ))
(princ c) ))


(defun factor-multiplicity (n factor)
"Return how many times the factor is contained in n"
; (factor-multiplicity 12 2) => 2
(do* ((i 0 (1+ i))
(n (/ n factor) (/ n factor)) )
((not (integerp n)) i)
() ))

</lang>
</lang>
{{out}}
{{out}}

Revision as of 10:04, 15 September 2021

Task
Integer long division
You are encouraged to solve this task according to the task description, using any language you may know.

Write a function that prints the result of the division of two integers with infinite precision (only limited by the available memory), stopping before the period starts repeating itself. Return also the length of this period (0 if there is no period).

Demonstrate it with the division 1/149, whose result is 0.0067114093959731543624161073825503355704697986577181208053691275167785234899328859060402684563758389261744966442953020134228187919463087248322147651, where the last 148 digits repeat endlessly.

The result could be stored as a string or simply output to the screen.
Note that the division of any two numbers will always produce a period, but if the numerator is an exact multiple of the denominator, or if the denominator contains only the factors 2 and 5, the period will be 0. In the remaining cases, these possible 2's and 5's of the denominator produce a leading number of digits in the quotient, but have no effect on the period.

References
  • [1] Wikipedia article on Long Division



Common Lisp

<lang lisp> (defun $/ (a b)

"Divide a/b with infinite precision printing each digit as it is calculated and return the period length"
($/ 1 17) => 588235294117647 ; 16
 (assert (and (integerp a) (integerp b) (not (zerop b))))
 (do* (c (i0 (1+ (max (factor-multiplicity b 2) (factor-multiplicity b 5)))) ; the position which marks the beginning of the period
       (r a (* 10 r)) ; remainder
       (i 0 (1+ i)) ; iterations counter
       (rem (if (= i i0) r -1) (if (= i i0) r rem)) ) ; the first remainder against which to check for repeating remainders
      ((and (= r rem) (not (= i i0))) (- i i0))
   (multiple-value-setq (c r) (floor r b))
   (princ c) ))


(defun factor-multiplicity (n factor) "Return how many times the factor is contained in n"

(factor-multiplicity 12 2) => 2

(do* ((i 0 (1+ i)) (n (/ n factor) (/ n factor)) ) ((not (integerp n)) i) () ))

</lang>

Output:
($/ 1 149) 
00067114093959731543624161073825503355704697986577181208053691275167785234899328859060402684563758389261744966442953020134228187919463087248322147651
148