Generating PI in Clojure 57
The SICP book shows a cute algorithm for computing PI using infinite sequences (lazy evaluation). I have adapted it for Clojure and modified it to use Java’s BigDecimal class, so that I can generate arbitrary precision.
First we define a function that generates an “infinite” list of terms of the form 1/1 + 1/3 – 1/5 + 1/7 – ... This is a well known series that very slowly converges on Pi. Notice that I’m using the ‘M’ suffix to denote BigDecimal, and I’m restricting the precision to 300 places. Notice also that I’m using lazy-seq. This function delays the execution of the ‘cons’ term until that part of the list is actually used. This allows the list to appear to be infinite.
(defn pi-summands [n]
(lazy-seq
(cons (with-precision 300 (/ 1M n))
(map - (pi-summands (+ n 2))))))
Next we have two utility functions. The first multiplies the terms of a list by a scale factor. The other adds two lists together producing a list of sums. If the input lists are ‘infinite’, the output lists will also be ‘infinite’.
(defn scale-stream [stream factor] (map (fn [x] (* x factor)) stream)) (defn add-streams [p q] (map + p q))
partial-sums takes a list of terms produces a list of the sums of those terms. Given [a b c] it produces [a a+b a+b+c]. And, again, the lists can be infinite.
(defn partial-sums [s]
(lazy-seq
(cons (first s) (add-streams (next s) (partial-sums s)))))
pi-stream mutiplies the partial-sums of the pi-summands by 4. Turning the summing sequence into 4/1 + 4/3 – 4/5…
(def pi-stream (scale-stream (partial-sums (pi-summands 1)) 4))
A simple squaring function.
(defn square [s] (* s s))
Euler’s transform is a fancy way to average three terms of a +/- sequence. It can dramatically increase the precision of an otherwise slowly converging sequence. The euler-transform function produces a sequence of results from the pi-stream. Again, note the constraint I place on BigDecimal precision.
(defn euler-transform [s]
(let [s0 (nth s 0)
s1 (nth s 1)
s2 (nth s 2)]
(lazy-seq
(cons (with-precision 300 (- s2 (/ (square (- s2 s1))
(+ s0 (* -2 s1) s2))))
(euler-transform (next s))))))
It turns out that you can use Euler’s transform on it’s own results to further increase precision. The make-tableau function arranges the reapplication of a transform so that it can be repeatedly applied to itself.
(defn make-tableau [transform s]
(lazy-seq
(cons s (make-tableau transform (transform s)))))
And now we grab the first element of each repetition.
(defn accelerated-sequence [transform s] (map first (make-tableau transform s)))
A little utility to print the elements of a list.
(defn print-list [s] (doseq [n s] (println n)))And now finally we print the first 150 iterations of the accelerated euler-transformation of the pi sequence.
(print-list (take 150 (accelerated-sequence euler-transform pi-stream)))
The 150th result (the first two lines of which are accurate) 3.14159265358979323846264338327950288419716939 93751058209749445923078164062862089986280348253 25256352154500957038098311477352066337027814620 46050836612955894790973622135628850706785335611 34661971615744147647325427374216175843967838084 09640502874355811103562027043480098593797655792 36344321165429010895M
I love laziness. A while back, I wrote a Mandelbrot Set generator in Haskell. The computation I formed was over an infinite grid ([0..] in x and y). Afterward, I used this function to “pluck” out interesting areas. With laziness, these areas were computed on demand:
This is a form of abstraction which is harder to achieve in non-lazy languages. You form a general computation and impose the edges later.
You inspired me to try this in Scala. I had some trouble reading the prefix notation, but I think I figured it out. My result for the 150th value in the sequence is close to yours, but not identical. May have to do with the type of rounding I’m doing on the division.
Doesn’t feel as nice as your clojure version, but I’m a Scala newbie. There is probably a much better way.
http://gist.github.com/162977
Instead of using lazy-seq “manually” you could use some of the build in Clojure functions. For example, you can write pi-summands using the standard iterate function (in a slightly evil feeling way and I’m sure there’s a better way to do this!)
(def pi-summands (map first (iterate (fn [[x y]] (let [n (+ y 2)] [(/ 1 n) n])) [1 1])))Clojure also has some nifty short-hand syntax
(defn scale-stream [stream factor] (map #(* % factor) stream))Where # indicates an anonymous function of one argument (represented by %).
I thought I’d attempt a clone of your algorithm in Scala, since I’m learning that. Here’s my best result so far:
http://gist.github.com/162860
Still some rough edges in 2.7.5 I felt compelled to work around (BigDecimal support, no cons(::) operator for streams. The Clojure version feels cleaner to me – even though I’m not comfortable with prefix notation.
All the type definitions are required, of course. However, I feel like they’re more clutter than useful to the developer.
Great stuff. I learned something new.
@Jeff:You missed the part where the summands are negative on every other term. Uncle Bob’s explicit lazy-seq is really novel with the “map -”!
@Uncle Bob: You can use the deconstructing bind (“Vector binding-exprs”) for your
euler-transforminstead oflet:(defn euler-transform [[s0 s1 s2 :as s]] ...)Also I find I get a “Divide by zero error” and/or “Stack overflow error” if I try to calculate a lot of terms, like say 350, with your implementation. i.e.
(print-list (take 50 (drop 300 pi-terms)))-> ... java.lang.ArithmeticException: Divide by zeroBTW, 300 terms yields 126 correct digits, while my implementation of the Calculating Pi using the van Wijngaarden transformation yields 296 digits after 300 terms, which comes closer to the limits set by the with-precision. (Actually the comparison is more like apples to oranges, because the latter is calculating more. Oh well.) Still, 126 digits ought to be enough for anybody (in this universe).
The Leibniz series actually converges on Pi/4, but the second paragraph says it converges on Pi. It took me a while to understand what the multiplication was needed for.
However, it’s very nice to read and try to grasp lisp after 8 or so years from taking the SICP course.
Living without an aim is like sailing without a compass. with a new http://www.handbags4buy.com/ idea is a crank until the idea succeeds.
Very quietly I take my leave.To seek a dream in http://www.edhardy-buy.com/ starlight.
mutiplies the partial-sums of the pi-summands by 4. Turning the summing sequence into 4/1 + 4/3 – 4/5…
The SICP book is very well.
denote BigDecimal, and I’m restricting the precision to 300 places. Notice also
An electric radiator can offer an energy efficient heating solution to your home.Make your home become warm in a short time with the high efficiency.T he electric towel rail made the towels warm and softy during your bath time.You can have a comfortable touch of luxury to have a warm towels and wouldn`t worried about is.We supply all types of radiators includingelectric radiators and electric towel rail.The electric towel rails give you the most luxury life in the bath room.The electric towel rails keep the towels dry all the time.
I think I figured it out. My result for the 150th value in the sequence is close to yours, but not identical. May have to do with the type of rounding I’m doing on the division.
we offer you canada goose to enjoy the winter!! Canada goose jakkesnug Goose jakkeYou’re Worth It Canada goose jakkerremain stylish Canada goose parkais a trustworthy brand Canada goose tilbudis the best one
canada goosewarm canada goose parka protection canada goose expeditionfashionable canada goose jakkerlet you have Happy winter canada goose jakkeGood quality
canada goose jacka vogue goose jacka pretty canada goose jackordifferent designs outlet canada goose amazing canada goose Expedition smooth welcome to buy!thank you!
Multiplies the partial-sums of the pi-summands by 4. Turning the summing sequence into 4/1 + 4/3 – 4/5
This is a great blog, I’ve loved having a look around today. moncler jackets I’m sure you could definitely make a dollar or two if you sold some more advertising on here!moncler
Thanks for the compliment. I’ve straddled the state line a few times while enjoying a nice cool beverage at the FloraBama. It’s on my list of faves.ugg online outlet
it probably doesn’t deserve all of the build up that I just gave it, but I suspect that I’ll be writing more about this topic. There’s definitely more to discuss.
Mold making is the core business of Intertech (Taiwan). With world level technology, Intertech enjoys a very good reputation for making Injection Mold and Plastic Moldsfor their worldwide customers.
thanks for Moncler Jackets || Christian louboutin UK || Moncler coats || Christian louboutin shoes || Christian louboutin pumps your post!
This is one of the most professional manufacturers and suppliers in plastic packing machinery. We mainly provide non woven bag making machine,disposable glove machines,blowing film machines,flexo printing machines,garbage bag making machine etc.
The euler-transform function produces a sequence of results from the pi-stream. Again, note the constraint I place on BigDecimal precision.
good May have to do with the type of rounding I’m doing on the division.
We are the professional shorts manufacturer, shorts supplier, shorts factory, custom shorts.
I wonder if u can do this in other Programming languages?
Skin Prep Pads (I use Cavilon) Migthy Tite Glue *(not necessary …your choice) EnduraBond (from Truetape)
25% IC MOisturiser (make sure its the one in the brown bottle w/ the Aloe Vera plant on it) Fast track knot sealer (from Adventhair) Fray Block (at Walmart, Fabric stores)
I am rather glad to see such information which I was searching for a long time.
A bad beginning makes a bad ending. A bird in the hand is worth than two in the bush. A year’s plan starts with
spring. Bad news has wings. Better to ask the way than go astray. By reading we enrich the mind, by conversation we
polish it. Custom makes all things easy. He is not fit to command others that cannot command himself. He laughs best
who laughs last. tiffany and co outlet
i need it. Thanks
internette görüntülü olarak okey oyunu oyna, gerçek kisilerle tanis, turnuva heyecanini yasa.
Mr Coates coach purses is the longest U.S. market popular with one of the most successful leather brand. Mr Coates coach purses store represents the most admirable American fashion innovative style and traditional skills . Mr Coates coach bags have durable quality and exquisite technology, Conspicuous Coach Heels in the female consumers have good reputation. Welcome to our shop Elegant Coach Purses
I miss this old code practice.
I attempted these beats by dr dre studio out in several genres thinking about which i listen to an eclectic mix Beats By Dr Dre. a washing cloth as well as the manual. Do not purchase any beats by dr dre solo purple products inside the internet unless you’re getting from an Authorized internet DealerBeats By Dre Just Solo. We are reliable provide good beats by dr dre pro black by reduced price.
Weekend ago, I purchased this ray ban online here. Today, I come here to select another cheap ray ban sunglasses for my son. I am fond of good sunglasses for the charm I bought here.
Blog posts about wedding and bridal are always rare to find , at least with great quality,you qualify for a great blog post writer title,kep the great job happening
Thank you so much for the English translation! I love this shawl and will be making is soon.
This shawl just jumped to the top of my project list! Very pretty indeed. Thanks for sharing the pattern with us.
very interesting article,and i am so happy to see this,thanks to lovely share
Never would have thunk I would find this so indisepsnable. | Backpack
y project list! Very pretty indeed. Thanks for sharing the pattern with ubeats by dre sale cheap beats by dre
Excellent article?The Jovani dress showed in the picture are very beautiful. Can you tell me where I can buy a mori lee dress at a low price
Wow I read about it, but to be honest I never watched any picture of it, Ash sandals Ash womens sandals cheap Ash thong sandals Ash reef sandals it was truly a serious event, the climate its changing very rapidly around the world, maybe the 2012 premonition is true.
Great post. Please write more and more about this.
Great post. Please write more and more about this.
I really enjoy your articles. Very well written. wholesale women replicate Coach backpacks more order,more discount
Bandage Dresseswill show your beautiful line and tender silhouette. Each clipping of Bandage Dresses is close to the body, and by this way can make you more comfortable and sexy. If you want yourself posses perfect figure, if you imagine yourself the focus in any occasions, the Bandage Dresseswill be your best choice. Note:Dry clean only. Rayon, Nylon, Spandex.
The public may not have known what the messages meant, but it helped pay for them. The skywriting stunt was supported by city and state public funding, according to the High Line’s website. MTS ??? “I wanted a narrative trajectory towards something optimistic at the end, which was the last message, ‘Now Open,’” she said of the work. MTS ??? Mac
When it comes to feather dress, what appears in your mind? Which kind brand of down jacket do you like prefer? Though there are many down jackets for you to choose from, on the word, which one you really enjoy? I want to say that canada goose coats is really your best choice. I believe you can’t agree with me any more. When you take the quality into consideration, you will find that it is superior to any other kind of coat. Besides, discount canada goose jackets is a world well-known brand, which has gained high reputation in the world, which has accepted by our customers and some organization. Because of its high quality, some of our loyal customers have promoted it to the people around them. In their opinion, it is good to informing others to know it. Recently, Canada Goose Trillium Parka is on hot sale. What I have to inform you is that all the products there are made by hand, so they are elaborative and elegant enough. It is really beautiful once you dress in. So, if you are a lovely girl or woman, go to the store to buy one for you. You will appreciate it that you have such a coat.In addition, they also have any other products like canada goose Gloves and canada goose jacket supplier.Hope your will like its!
Afterwards, custom NFL jersey Dorsett said to succeed, the NFL must keep New York Giants teaching the game to as many Chinese kids as possible.Chinese love World Cup Soccer NFL jersey custom and NBA basketball. Selling them NFL New England Patriots football has proven much more difficult. On Sunday, the NFL set Philadelphia Eagles up an elaborate, interactive exhibition NFL custom jerseys outside a Shanghai stadium in an attempt to build a fan custom NFL jerseys base in the world’s most populous nation.
For non-monarch said: I plan for her for years until now affair nod to blow assured. Afterwards she confused to Kyoto, we would not acquire appear
here, aggregate today here, feel chargeless to allocution about my memories! And June road: monks of the bodies I consistently brash afflicted to
into soil, too slick
Shopping inside a incredibly outlet juicy couture sale in regards to the web can be incredibly a great offer handy especially once the regional shop outlet exactly where it is possible to buy the item that you desire is a good offer out of your area. Apart from this, going to malls demands some trip and of course, you would ought to devote resources to the fare of going to mall.
Every women always has Christian Louboutins Wedding Shoes turn of fame but it also has its own goodbyes.
I really enjoyed this site. This is such a Great resource that you are providing and you give it away for free. It gives in depth information. Thanks for this valuable information. http://www.nuvodev.com/
Generating PI in Clojure 55 good post35
Generating PI in Clojure 56 hoo,good article!!I like the post!158