Comment detail

分数を小数に展開 (Nested Flatten)
バッファ使わないで頑張りました。巨大な数もほとんど使ってないつもり。
1/8388609 (1,398,101 桁で循環)ぐらいなら計算できました。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
(defun expand-rational (a b)
  (if (zerop (rem (expt 10 31) b))
      ;; b が 10 の冪で割り切れるなら有限
      (expand-terminating a b)
    ;; 割り切れないなら循環する
    (expand-recurring a b)))

(defun expand-terminating (a b)
  (do ((c (/ a b) (* c 10))
       (e 0 (1+ e)))
      ((integerp c)
       ;; a/b = c * 10^{-e}, c は 10 の倍数ではない整数
       (format t "0.~V,'0D" e c))))

(defun normalize-denominator (b)
  (let ((tmp b) (i 0))
    (loop
      (let ((g (gcd tmp 10)))
	(if (= g 1)
	    (return (values i tmp))
	  (setq tmp (/ tmp g)
		i (1+ i)))))))

(defun expand-recurring (a b)
  (multiple-value-bind (e b1)
      (normalize-denominator b)
    ;; a/b = 10^{-e} * a / b1, (b1, 10) = 1
    ;; let n + x = a/b1, x < 1
    (multiple-value-bind (n x)
	(truncate (/ a b1))
      (if (plusp n)
	  (format t "0.~V,'0D" e n)
	(format t "0.~V@{0~}" e t))
      (princ "{")
      (expand-recurring-part x)
      (princ "}"))))

;; 分母 b1 から循環節の長さを求める。b1 は 10 と互いに素と仮定
(defun rec-length (b1)
  (do ((x (mod 10 b1) (mod (* x 10) b1))
       (c 1 (+ c 1)))
      ((= x 1) c)))

;; x < 1 の循環節を出力
(defun expand-recurring-part (x)
  (let ((len (rec-length (denominator x))) d)
    (dotimes (i len)
      (multiple-value-setq (d x) (truncate (* x 10)))
      (princ d))))

Index

Feed

Other

Link

Pathtraq

loading...