Chudnovsky's Algorithm in Gambit Scheme - A novice's question
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!
participants (3)
-
Bakul Shah -
Bradley Lucier -
Torbjörn Svensson Diaz