Hello!
First of all, I don't know if this is the right place to ask this question. If you think not, please let me know. Maybe you think the question is too basic. I emphasize, it's not homework.
Here's Chudnovsky's algorithm in Scheme.
(define (pi (digits)) (let* ((A 13591409) (B 545140134) (C 640320) (C^3/24 (quotient (expt 640320 3) 24)) (D 12)) (define (-1^n*g n g) (if (odd? n) (- g) g)) (define (split m n) (if (= 1 (- n m)) (let* ((6n (* 6 n)) (g (* (- 6n 5) (- (+ n n) 1) (- 6n 1)))) (list g (* C^3/24 (expt n 3)) (* (-1^n*g n g) (+ (* n B) A)))) (let* ((mid (quotient (+ m n) 2)) (gpq1 (split m mid)) (gpq2 (split mid n)) (g1 (car gpq1)) (p1 (cadr gpq1)) (q1 (caddr gpq1)) (g2 (car gpq2)) (p2 (cadr gpq2)) (q2 (caddr gpq2))) (list (* g1 g2) (* p1 p2) (+ (* q1 p2) (* q2 g1)))))) (let* ((num-terms (inexact->exact (floor (+ 2 (/ digits 14.181647462))))) (sqrt-C (integer-sqrt (* C (expt 100 digits)))) (gpq (split 0 num-terms)) (g (car gpq)) (p (cadr gpq)) (q (caddr gpq))) (quotient (* p C sqrt-C) (* D (+ q (* p A)))))))
||| |
|There's a C version of the same algorithm that is about sixteen times as long, so Scheme is expressive indeed. What I want to do is to compare the two implementations, ||but I get stuck and don't know how to proceed!|
|First I want to write a version of the Scheme program that asks me how many digits I want to calculate and then calculate that using interpretation, but I don't manage to do that. Then I want to compile the Scheme code and see how fast it runs and how much RAM it uses. Lastly, I want to compile the C version and run it. I want to compare the performance and RAM usage in all three cases. |
|Could you please help me out with the Scheme part? I guess I am supposed to use "read" somehow, but how? I am a Scheme novice. |
|Best regards,|
| |
|-- |
|Torbjörn Svensson Diaz |
| |
Afficher les réponses par date
On 8/16/23 4:40 PM, Torbjörn Svensson Diaz wrote:
|Could you please help me out with the Scheme part? I guess I am supposed to use "read" somehow, but how? I am a Scheme novice.
My mail's all screwed up, but see the discussion here:
https://mailman.iro.umontreal.ca/pipermail/gambit-list/2013-June/006789.html
Basically, gmp-chudnovsky.c optimizes the algorithm used in chud1.scm, but I link to a python version that I believe uses exactly the same algorithm, but with the Gnu Multiprecision Library (gmp).
Brad
On Aug 16, 2023, at 1:40 PM, Torbjörn Svensson Diaz torbjorn_svensson_diaz@yahoo.com wrote:
Hello!
First of all, I don't know if this is the right place to ask this question. If you think not, please let me know. Maybe you think the question is too basic. I emphasize, it's not homework.
Here's Chudnovsky's algorithm in Scheme.
(define (pi (digits)) (let* ((A 13591409) (B 545140134) (C 640320) (C^3/24 (quotient (expt 640320 3) 24)) (D 12)) (define (-1^n*g n g) (if (odd? n) (- g) g)) (define (split m n) (if (= 1 (- n m)) (let* ((6n (* 6 n)) (g (* (- 6n 5) (- (+ n n) 1) (- 6n 1)))) (list g (* C^3/24 (expt n 3)) (* (-1^n*g n g) (+ (* n B) A)))) (let* ((mid (quotient (+ m n) 2)) (gpq1 (split m mid)) (gpq2 (split mid n)) (g1 (car gpq1)) (p1 (cadr gpq1)) (q1 (caddr gpq1)) (g2 (car gpq2)) (p2 (cadr gpq2)) (q2 (caddr gpq2))) (list (* g1 g2) (* p1 p2) (+ (* q1 p2) (* q2 g1)))))) (let* ((num-terms (inexact->exact (floor (+ 2 (/ digits 14.181647462))))) (sqrt-C (integer-sqrt (* C (expt 100 digits)))) (gpq (split 0 num-terms)) (g (car gpq)) (p (cadr gpq)) (q (caddr gpq))) (quotient (* p C sqrt-C) (* D (+ q (* p A)))))))
This is exactly the same (except for indentation) as what I posted on HackerNews a few months ago: https://news.ycombinator.com/item?id=35021745
I don't recall but I may have posted it elsewhere too! This version has no globals compared to the version I posted on May 23, 2013 on a RaspberryPi forum but basically the same.
||| |
|There's a C version of the same algorithm that is about sixteen times as long, so Scheme is expressive indeed. What I want to do is to compare the two implementations, ||but I get stuck and don't know how to proceed!|
Do you mean Compare the scheme code with the C code? If so, you'd have understand the main part of the function above. For that I think your best bet may be to start with the wikipedia article: https://en.wikipedia.org/wiki/Chudnovsky_algorithm
And understand the recurrence form. But if you just want to compare their overall resource use and timing, don't bother!
|First I want to write a version of the Scheme program that asks me how many digits I want to calculate and then calculate that using interpretation, but I don't manage to do that. Then I want to compile the Scheme code and see how fast it runs and how much RAM it uses. Lastly, I want to compile the C version and run it. I want to compare the performance and RAM usage in all three cases. |
|Could you please help me out with the Scheme part? I guess I am supposed to use "read" somehow, but how? I am a Scheme novice.
'supposed to use "read" somehow' -- This does sound like homework but this is the easy part. Look at some interactive Scheme program. Alternatively pass the number of digits as an argument. I don't think *compiling* the Scheme program would help much for performance.
I am still not clear on why you want do all this though!
|
|Best regards,|
| |
|-- |
|Torbjörn Svensson Diaz |
| |
Gambit-list mailing list Gambit-list@iro.umontreal.ca https://mailman.iro.umontreal.ca/cgi-bin/mailman/listinfo/gambit-list
On 2023-08-18 02:33, Bakul Shah wrote:
On Aug 16, 2023, at 1:40 PM, Torbjörn Svensson Diaz torbjorn_svensson_diaz@yahoo.com wrote:
This is exactly the same (except for indentation) as what I posted on HackerNews a few months ago: https://news.ycombinator.com/item?id=35021745
I don't recall but I may have posted it elsewhere too! This version has no globals compared to the version I posted on May 23, 2013 on a RaspberryPi forum but basically the same.
You have indeed posted it elsewhere, more precisely at the FreeBSD forums. Here's a link, https://forums.freebsd.org/search/332332/?q=chudnovsky&o=date.
||| |
|There's a C version of the same algorithm that is about sixteen times as long, so Scheme is expressive indeed. What I want to do is to compare the two implementations, ||but I get stuck and don't know how to proceed!|
Do you mean Compare the scheme code with the C code? If so, you'd have understand the main part of the function above. For that I think your best bet may be to start with the wikipedia article: https://en.wikipedia.org/wiki/Chudnovsky_algorithm
And understand the recurrence form. But if you just want to compare their overall resource use and timing, don't bother!
I think you're right. I should start with some simpler algorithm that's easier to understand and tinker with it instead. I'm just a Scheme novice.
|First I want to write a version of the Scheme program that asks me how many digits I want to calculate and then calculate that using interpretation, but I don't manage to do that. Then I want to compile the Scheme code and see how fast it runs and how much RAM it uses. Lastly, I want to compile the C version and run it. I want to compare the performance and RAM usage in all three cases. |
|Could you please help me out with the Scheme part? I guess I am supposed to use "read" somehow, but how? I am a Scheme novice.
'supposed to use "read" somehow' -- This does sound like homework but this is the easy part. Look at some interactive Scheme program. Alternatively pass the number of digits as an argument. I don't think *compiling* the Scheme program would help much for performance.
It's not homework. Basically no schools teach Scheme anymore.
I am still not clear on why you want do all this though!
Just want to learn Scheme and see if it's as good as some people say it is. That's all!
-
Bakul Shah -
Bradley Lucier -
Torbjörn Svensson Diaz