Dear Brad or Marc and list,
Curious, so you can parse into Gambit a decimal number with infinite precision, with exactness, by just appending "#e" to it i.e. > (define (string->exact-number s) (string->number (string-append "#e" s)))
(string->exact-number "1.23478289348923749872394728934")
61739144674461874936197364467/50000000000000000000000000000
Is there any way to do the opposite? All I see number->string give is "61739144674461874936197364467/50000000000000000000000000000"
- how would the definition of an exact-number->string look that produced an output with decimals, i.e. something that gave "1.23478289348923749872394728934" or "#e1.23478289348923749872394728934" back?
I understand there are cases with unlimited number of decimals i.e. 1/3, a typechecker for that would be awesome.
Thanks, Mikael
Afficher les réponses par date
Ah, actually this can be implemented for #e12345.6789 by first flooring and printing that out ("12345") then deducting that from the value (=> 0.6789) and then doing * 10 and |truncate| up to eq? 0 - that works. Perhaps it'd even be quite close to optimum speed?
I.e. #e12345.6789 (floor #) (- ## #) , and then repeat (eq? # 0) (* ## 10) (truncate #) (- ## #).
2014/1/15 Mikael mikael.rcv@gmail.com
Dear Brad or Marc and list,
Curious, so you can parse into Gambit a decimal number with infinite precision, with exactness, by just appending "#e" to it i.e. > (define (string->exact-number s) (string->number (string-append "#e" s)))
(string->exact-number "1.23478289348923749872394728934")
61739144674461874936197364467/50000000000000000000000000000
Is there any way to do the opposite? All I see number->string give is "61739144674461874936197364467/50000000000000000000000000000"
- how would the definition of an exact-number->string look that produced
an output with decimals, i.e. something that gave "1.23478289348923749872394728934" or "#e1.23478289348923749872394728934" back?
I understand there are cases with unlimited number of decimals i.e. 1/3, a typechecker for that would be awesome.
Thanks, Mikael
On 01/15/2014 12:58 PM, Mikael wrote:
Ah, actually this can be implemented for #e12345.6789 by first flooring and printing that out ("12345") then deducting that from the value (=> 0.6789) and then doing * 10 and |truncate| up to eq? 0 - that works. Perhaps it'd even be quite close to optimum speed?
I.e. #e12345.6789 (floor #) (- ## #) , and then repeat (eq? # 0) (* ## 10) (truncate #) (- ## #).
Well, this is a mathematical question rather than a programming question: Are rational numbers and repeating decimals (possibly repeating 0 at the end) the same kind of numbers? The answer is yes, of course.
To go from repeating decimals, where you have a pattern <pattern> of r repeating digits at the end, multiply by a power of 10 ($10^k$, say) such that the digits behind the decimal point are the start of the repeating pattern, then multiply the number again by $10^{r+k}$:
10^{r+k}x = integer<pattern>.<pattern><pattern>... 10^kx = integer.<pattern><pattern>...
subtract
(10^{r+k}-10^k)x=(integer<pattern> - integer)
so
x = (integer<pattern> - integer)/(10^{r+k}-10^k)
To go the other way, if $x=p/q$, divide p.00000000... by q in longhand. If any of the remainders are 0, then the division ends and 0 is repeated indefinitely. Otherwise, there can be only q-1 different remainders, so eventually one of them will have to repeat; after that the digits in the quotient repeat indefinitely.
I'm old enough to have taken the "New Math" in the 1960s, and I remember my teacher in 6th or 7th grade asking this question. They asked pretty sophisticated questions in those days, even if most of the students didn't really realize it.
Brad
After thinking this through a bit, I guess the algorithm I suggested is as fast as it goes, as because it's a rational, the actual result decimal digits are *not* available plaintext in the number's internal structures or alike, so this is the fastest algorithm. If you have any other thought on this feel free to tell.
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.
I agree with you fully that being exposed to challenging questions at every age does good to the soul.
Mikael
2014/1/15 Bradley Lucier lucier@math.purdue.edu
On 01/15/2014 12:58 PM, Mikael wrote:
Ah, actually this can be implemented for #e12345.6789 by first flooring and printing that out ("12345") then deducting that from the value (=> 0.6789) and then doing * 10 and |truncate| up to eq? 0 - that works. Perhaps it'd even be quite close to optimum speed?
I.e. #e12345.6789 (floor #) (- ## #) , and then repeat (eq? # 0) (* ## 10) (truncate #) (- ## #).
Well, this is a mathematical question rather than a programming question: Are rational numbers and repeating decimals (possibly repeating 0 at the end) the same kind of numbers? The answer is yes, of course.
To go from repeating decimals, where you have a pattern <pattern> of r repeating digits at the end, multiply by a power of 10 ($10^k$, say) such that the digits behind the decimal point are the start of the repeating pattern, then multiply the number again by $10^{r+k}$:
10^{r+k}x = integer<pattern>.<pattern><pattern>... 10^kx = integer.<pattern><pattern>...
subtract
(10^{r+k}-10^k)x=(integer<pattern> - integer)
so
x = (integer<pattern> - integer)/(10^{r+k}-10^k)
To go the other way, if $x=p/q$, divide p.00000000... by q in longhand. If any of the remainders are 0, then the division ends and 0 is repeated indefinitely. Otherwise, there can be only q-1 different remainders, so eventually one of them will have to repeat; after that the digits in the quotient repeat indefinitely.
I'm old enough to have taken the "New Math" in the 1960s, and I remember my teacher in 6th or 7th grade asking this question. They asked pretty sophisticated questions in those days, even if most of the students didn't really realize it.
Brad
2014/1/15 Mikael mikael.rcv@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 :)
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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
2014/1/15 Marc Feeley feeley@iro.umontreal.ca
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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
On Jan 15, 2014, at 8:12 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Marc Feeley feeley@iro.umontreal.ca
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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]
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@iro.umontreal.cawrote:
On Jan 15, 2014, at 8:12 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Marc Feeley feeley@iro.umontreal.ca
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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]
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
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@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@iro.umontreal.cawrote:
On Jan 15, 2014, at 8:12 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Marc Feeley feeley@iro.umontreal.ca
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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]
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/gambit-list
On Jan 16, 2014, at 4:59 AM, Estevo euccastro@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@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@iro.umontreal.ca wrote:
On Jan 15, 2014, at 8:12 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Marc Feeley feeley@iro.umontreal.ca
On Jan 15, 2014, at 5:04 PM, Mikael mikael.rcv@gmail.com wrote:
2014/1/15 Mikael mikael.rcv@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
On Thu, Jan 16, 2014 at 07:34:41AM -0500, Marc Feeley wrote:
On Jan 16, 2014, at 4:59 AM, Estevo euccastro@gmail.com wrote:
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
If all you want is a boolean, maybe it would be simpler to reduce the fraction to lowest terms (might this already have been done?) and then checking if the denominator is divisible by 2 or 5.
-- hendrik
On Jan 16, 2014, at 8:35 AM, Hendrik Boom hendrik@topoi.pooq.com wrote:
If all you want is a boolean, maybe it would be simpler to reduce the fraction to lowest terms (might this already have been done?) and then checking if the denominator is divisible by 2 or 5.
I guess you mean that 2 and 5 are the only factors (for example 1/140 has an infinite decimal representation but the denominator is divisible by 2, 5 and 7).
Marc
(define (has-finite-decimal-representation? n) ;; n is a positive real
(define (remove-factor factor n) (if (zero? (modulo n factor)) (remove-factor factor (quotient n factor)) n))
(= 1 (remove-factor 2 (remove-factor 5 (denominator (inexact->exact n))))))
On Thu, Jan 16, 2014 at 08:58:00AM -0500, Marc Feeley wrote:
On Jan 16, 2014, at 8:35 AM, Hendrik Boom hendrik@topoi.pooq.com wrote:
If all you want is a boolean, maybe it would be simpler to reduce the fraction to lowest terms (might this already have been done?) and then checking if the denominator is divisible by 2 or 5.
I guess you mean that 2 and 5 are the only factors (for example 1/140 has an infinite decimal representation but the denominator is divisible by 2, 5 and 7).
You are right. I was wrong.
-- hendrik