[gambit-list] Any rational-number->string with infinite precision for decimal output? (i.e. d.ddddd rather than x/y)
Marc Feeley
feeley at iro.umontreal.ca
Thu Jan 16 07:34:41 EST 2014
On Jan 16, 2014, at 4:59 AM, Estevo <euccastro at gmail.com> wrote:
> Oops, no, sorry for the brain fart. It would be a repeated _remainder_ (in the primary school pencil-and-paper algorithm) that would imply a cycle.
>
>
> On Thu, Jan 16, 2014 at 8:59 AM, Estevo <euccastro at gmail.com> wrote:
> If the input numbers are constrained to be rationals, shouldn't it be enough to check for the first repeated digit?
>
>
> On Thu, Jan 16, 2014 at 4:11 AM, Marc Feeley <feeley at iro.umontreal.ca> wrote:
>
> On Jan 15, 2014, at 8:12 PM, Mikael <mikael.rcv at gmail.com> wrote:
>
> >
> >
> > 2014/1/15 Marc Feeley <feeley at iro.umontreal.ca>
> >
> > On Jan 15, 2014, at 5:04 PM, Mikael <mikael.rcv at gmail.com> wrote:
> >
> > > 2014/1/15 Mikael <mikael.rcv at gmail.com>
> > > I believe you addressed now how to detect whether a rational has inifinite decimals - yes I got aware there's an algorithm to do this too, (even while it's iterative - would be nice to understand how fast it is, anyhow) neat.
> > >
> > > Yeah if anyone has an example implementation of such an algorithm |has-infinite-decimals?| feel free to post :)
> >
> > It is really very simple. I’ll let you think about it some more before posting a solution…
> >
> > Marc
> >
> >
> > I trust it's both simple and elegant - implementing something and do not have the proper focus on math in this moment;
> >
> > It just struck me that it's an awesome symmetry that there's this full support both re input, handling and output (per algorithm I suggested in previous email, guess that's how fast at is goes) of these, and the dot on the i in this respect would be the ability to check that a number has a finite number of decimals - saw an algorithm but didn't take it to the level of implementing it - , that was all I was thinking today.
> >
> > Mikael
>
> The following algorithm is not optimal, but it has the virtue of being simple. It puts the repeating decimals in […] if there are any (in other words 1/3 prints as 0.[3] meaning 0.33333333...).
>
> Marc
>
>
> (define (println-decimal n) ;; n is a positive real
>
> (define (generator frac states digits)
> (if (= frac 0)
> (reverse digits)
> (let ((seen (member frac states)))
> (if seen
> (let* ((i (- (length seen) 1))
> (len (length states)))
> (append (reverse (list-tail digits (- len i)))
> '(#\[)
> (list-tail (reverse digits) i)
> '(#\])))
> (let* ((frac*10 (* 10 frac))
> (digit (truncate frac*10)))
> (generator (- frac*10 digit)
> (cons frac states)
> (cons digit digits)))))))
>
> (println
> (let* ((exact (inexact->exact n))
> (int (truncate exact)))
> (list int #\. (generator (- exact int) '() '())))))
>
> (println-decimal 1/1024)
> (println-decimal 1/999)
> (println-decimal 5/700)
> (println-decimal 0.1)
> (println-decimal 0.2)
> (println-decimal 0.3)
> (println-decimal (* 4 (atan 1)))
> (println-decimal (expt 1/3 7))
>
> ;; output:
> ;;
> ;; 0.0009765625
> ;; 0.[001]
> ;; 0.00[714285]
> ;; 0.1000000000000000055511151231257827021181583404541015625
> ;; 0.200000000000000011102230246251565404236316680908203125
> ;; 0.299999999999999988897769753748434595763683319091796875
> ;; 3.141592653589793115997963468544185161590576171875
> ;; 0.[000457247370827617741197988111568358481938728852309099222679469593049839963420210333790580704160951074531321444901691815272062185642432556012802926383173296753543667123914037494284407864654778235025148605395518975765889346136259716506630086877]
The algorithm I gave produces the decimal representation such that the repeating part if there is one is identified. A simple change to the algorithm will return a boolean indicating if there is a repeating part or not (i.e. if the digit generator encounters a cycle).
Marc
(define (has-finite-decimal-representation? n) ;; n is a positive real
(define (generator frac states)
(if (= frac 0)
#t
(let ((seen (member frac states)))
(if seen
#f
(let* ((frac*10 (* 10 frac))
(digit (truncate frac*10)))
(generator (- frac*10 digit)
(cons frac states)))))))
(let* ((exact (inexact->exact n))
(int (truncate exact)))
(generator (- exact int) '())))
(pp (has-finite-decimal-representation? 1/1024))
(pp (has-finite-decimal-representation? 1/999))
(pp (has-finite-decimal-representation? 5/700))
(pp (has-finite-decimal-representation? 0.1))
(pp (has-finite-decimal-representation? 0.2))
(pp (has-finite-decimal-representation? 0.3))
(pp (has-finite-decimal-representation? (* 4 (atan 1))))
(pp (has-finite-decimal-representation? (expt 1/3 7)))
;; output:
;;
;; #t
;; #f
;; #f
;; #t
;; #t
;; #t
;; #t
;; #f
More information about the Gambit-list
mailing list