https://github.com/jgrant27/jngmisc/tree/master/rust/machin-pi

Latent Semantic Indexing (LSI) is used widely today in Semantic Search and has many other uses in Deep Machine Learning. This is a pretty good explanation/visualization from 40 years ago.

A few months back I took a look at Elixir. More recently I’ve been exploring F# and I’m very pleased with the experience so far. Here is the ring probabilities algorithm implemented using F#. It’s unlikely that I will ever use Elixir again because having a powerful static type system provided by F# at my disposal is just too good. let rec calcStateProbs (prob: float, i: int, currProbs: float [], newProbs: float []) = if i < 0 then newProbs else let maxIndex = currProbs.

*Updated 08-23-2012 01:04:38* Replaced the use of Data.Vector with the persistent Data.Sequence which has O(logN) worst case time complexity on updates. A Haskell version of the previous code using the more efficient(access and update) persistent Data.Sequence type so that the desired time complexity is maintained for the union operation. -- Disjoint set data type (weighted and using path compression). -- O((M+N)lg*N + 2MlogN) worst-case union time (practically O(1)) -- For M union operations on a set of N elements.

It’s been a while since I last posted in this series. Today we look at the disjoint-set data structure, specifically disjoint-set forests and the complementary algorithm : union-find. In computing, a disjoint-set data structure is a data structure that keeps track of a set of elements partitioned into a number of disjoint (nonoverlapping) subsets. A union-find algorithm is an algorithm that performs two useful operations on such a data structure:

CODEBREAKER tells the story of one of the most important people of the 20th century. Alan Turing set in motion the computer age and his World War II codebreaking helped save two million lives. Yet few people have heard his name, know his tragic story, or understand his legacy. In 1954, Turing committed suicide at age 41 after being forced to undergo hormone therapy to “fix” his sexual orientation. He left behind a lasting legacy and lingering questions about what else he might have accomplished if society had embraced his unique genius instead of rejecting it.

Richard Carrier puts forward a fantastic approach to verifying history in his latest book : Proving History: Bayes’s Theorem and the Quest for the Historical Jesus “… historian Richard C. Carrier proposes Bayes’s theorem as a solution to the problem of establishing reliable historical criteria. He demonstrates that valid historical methods—not only in the study of Christian origins but in any historical study—can be described by, and reduced to, the logic of Bayes’s theorem.

In this second post in this series we look at an implementation of the always useful Fast Fourier Transform. (FFT) An algorithm for computing the Fourier transform of a set of discrete data values. Given a finite set of data points, for example a periodic sampling taken from a real-world signal, the FFT expresses the data in terms of its component frequencies. It also solves the essentially identical inverse problem of reconstructing a signal from the frequency data.

White paper : To a mathematical theory of evolution and biological creativity We present an information-theoretic analysis of Darwin’s theory of evolution, modeled as a hill-climbing algorithm on a fitness landscape. Our space of possible organisms consists of computer programs, which are subjected to random mutations. We study the random walk of in-creasing fitness made by a single mutating organism. In two different models we are able to show that evolution will occur and to characterize

Artificial Intuition – A New Possible Path To Artificial Intelligence – by Monica Anderson Artificial Intelligence was born in Computer Science departments, and inherited their value sets including Correctness. This mindset, this necessity to be logical, provable, and correct has been a fatal roadblock for Artificial Intelligence since its inception. The world is Bizarre, and Logic can not describe it. Artificial Intuition will easily outperform Logic based Artificial Intelligence for almost any problem in a Bizarre problem domain.

// pi_spigot.s - calculates Pi using a spigot algorithm // as an array of n digits in base 10000. // http://mathworld.wolfram.com/SpigotAlgorithm.html // // x86-64/SSE3 with for Linux, Intel, gnu assembler, gcc // // assemble: as pi_spigot.s -o pi_spigot.o // link: gcc -o pi_spigot pi_spigot.o // example run: ./pi_spigot 100 // output: 3.14159265358979323846264338327950288419716939937510582097494459230 ... // ... 78164062862089986280348253421170679 // .section .rodata .LC0: .string "%d." .LC1: .string "%04d" .text .globl print .type print, @function print: .

// pi_x64.s - calculates Pi using the Leibniz formula. // Each iteration prints a closer approximation to 50 digits. // This is not an optimal implementation and it runs forever. // // x86-64/SSE3 with for Linux, Intel, gnu assembler, gcc // // assemble: as pi_x64.s -o pi_x64.o // link: gcc -o pi_x64 pi_x64.o // run: ./pi_x64 // output: 3.14159264858204423376264458056539297103881835937500 // 3.14159265108366625440794450696557760238647460937500 // 3.14159265191852199450295302085578441619873046875000 // 3.14159265233600137889879988506436347961425781250000 // .... and on forever .

Haskell beats CL quite comfortably using the same algorithm : module Main( main ) where import System( getArgs ) arccot :: Integer -> Integer -> Integer arccot x unity = arccot' x unity 0 start 1 1 where start = unity `div` x arccot' x unity sum xpower n sign | xpower `div` n == 0 = sum | otherwise = arccot' x unity (sum + sign*term) (xpower `div` (x*x)) (n+2) (-sign) where term = xpower `div` n machin_pi :: Integer -> Integer machin_pi digits = pi' `div` (10 ^ 10) where unity = 10 ^ (digits+10) pi' = 4 * (4 * arccot 5 unity - arccot 239 unity) main :: IO () main = do args <- getArgs putStrLn (show (machin_pi (read (head args) :: Integer))) The first 10000 digits.

Thanks to metacircular for pointing out that (floor (/ x y)) can be written as (floor x y) while avoiding the intermediate rational. (defun machin-pi (digits) "Calculates PI digits using fixed point arithmetic and Machin's formula with double recursion" (labels ((arccot-minus (xsq n xpower) (let ((term (floor xpower n))) (if (= term 0) 0 (- (arccot-plus xsq (+ n 2) (floor xpower xsq)) term)))) (arccot-plus (xsq n xpower) (let ((term (floor (/ xpower n)))) (if (= term 0) 0 (+ (arccot-minus xsq (+ n 2) (floor xpower xsq)) term)))) (arccot (x unity) (let ((xpower (floor (/ unity x)))) (arccot-plus (* x x) 1 xpower)))) (let* ((unity (expt 10 (+ digits 10))) (thispi (* 4 (- (* 4 (arccot 5 unity)) (arccot 239 unity))))) (floor thispi (expt 10 10))))) The first 10000 digits again.

Update 2009-07-23 : Faster version in CL and a Haskell version. ——————————————————————————– A trivial approximation using the Leibniz formula. (defun leibniz-pi() (labels ((local-pi(sum n) (if (< n (expt 10 6)) (local-pi (+ sum (/ (expt -1 n) (+ (* 2 n) 1))) (+ n 1)) sum))) (* 4 (local-pi 0f0 0f0)))) And here’s a longer version(but faster and more precise) using Machin’s formula with fixed point arithmetic to x digits.