π in assembly (spigot algorithm)

Posted by jgrant, 2010-07-22 09:25:30

//   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:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	movq	%rsp, %rbp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movq	%rdi, -24(%rbp)
	movl	%esi, -28(%rbp)
	movq	-24(%rbp), %rax
	addq	$2, %rax
	movzwl	(%rax), %eax
	movzwl	%ax, %edx
	movl	$.LC0, %eax
	movl	%edx, %esi
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf
	movl	$2, -4(%rbp)
	jmp	.L2
.L3:
	movl	-4(%rbp), %eax
	cltq
	addq	%rax, %rax
	addq	-24(%rbp), %rax
	movzwl	(%rax), %eax
	movzwl	%ax, %edx
	movl	$.LC1, %eax
	movl	%edx, %esi
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf
	addl	$1, -4(%rbp)
.L2:
	movl	-28(%rbp), %eax
	subl	$1, %eax
	cmpl	-4(%rbp), %eax
	jg	.L3
	movl	$10, %edi
	call	putchar
	leave
	ret
	.cfi_endproc
.LFE0:
	.size	print, .-print
.globl main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	movq	%rsp, %rbp
	.cfi_offset 6, -16
	.cfi_def_cfa_register 6
	pushq	%rbx
	subq	$56, %rsp
	movl	%edi, -52(%rbp)
	movq	%rsi, -64(%rbp)
	cmpl	$1, -52(%rbp)
	jle	.L6
	.cfi_offset 3, -24
	movq	-64(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rax
	movq	%rax, %rdi
	call	atoi
	addl	$3, %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	addl	$3, %eax
	jmp	.L7
.L6:
	movl	$253, %eax
.L7:
	movl	%eax, -20(%rbp)
	movl	-20(%rbp), %eax
	cltq
	addq	%rax, %rax
	movq	%rax, %rdi
	call	malloc
	movq	%rax, -40(%rbp)
	movl	-20(%rbp), %eax
	cltq
	leaq	(%rax,%rax), %rdx
	movq	-40(%rbp), %rax
	movl	$0, %esi
	movq	%rax, %rdi
	call	memset
	movq	-40(%rbp), %rax
	addq	$2, %rax
	movw	$4, (%rax)
	cvtsi2sd	-20(%rbp), %xmm0
	movsd	.LC2(%rip), %xmm1
	mulsd	%xmm1, %xmm0
	cvttsd2si	%xmm0, %eax
	movl	%eax, -24(%rbp)
	jmp	.L8
.L13:
	movl	$0, -32(%rbp)
	movl	-20(%rbp), %eax
	subl	$1, %eax
	movl	%eax, -28(%rbp)
	jmp	.L9
.L10:
	movl	-28(%rbp), %eax
	cltq
	addq	%rax, %rax
	addq	-40(%rbp), %rax
	movzwl	(%rax), %eax
	movzwl	%ax, %eax
	imull	-24(%rbp), %eax
	addl	%eax, -32(%rbp)
	movl	-28(%rbp), %eax
	cltq
	addq	%rax, %rax
	movq	%rax, %rbx
	addq	-40(%rbp), %rbx
	movl	-32(%rbp), %ecx
	movl	$1759218605, %edx
	movl	%ecx, %eax
	imull	%edx
	sarl	$12, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %esi
	subl	%eax, %esi
	movl	%esi, %eax
	imull	$10000, %eax, %eax
	movl	%ecx, %edx
	subl	%eax, %edx
	movl	%edx, %eax
	movw	%ax, (%rbx)
	movl	-32(%rbp), %ecx
	movl	$1759218605, %edx
	movl	%ecx, %eax
	imull	%edx
	sarl	$12, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movl	%eax, -32(%rbp)
	subl	$1, -28(%rbp)
.L9:
	cmpl	$0, -28(%rbp)
	jns	.L10
	movl	$0, -44(%rbp)
	movl	-44(%rbp), %eax
	movl	%eax, -48(%rbp)
	movl	$0, -28(%rbp)
	jmp	.L11
.L12:
	movl	-24(%rbp), %eax
	addl	%eax, %eax
	leal	1(%rax), %edx
	movl	-28(%rbp), %eax
	cltq
	addq	%rax, %rax
	addq	-40(%rbp), %rax
	movzwl	(%rax), %eax
	movzwl	%ax, %ecx
	movl	-44(%rbp), %eax
	imull	$10000, %eax, %eax
	leal	(%rcx,%rax), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	div
	movq	%rax, -48(%rbp)
	movl	-28(%rbp), %eax
	cltq
	addq	%rax, %rax
	addq	-40(%rbp), %rax
	movl	-48(%rbp), %edx
	movw	%dx, (%rax)
	addl	$1, -28(%rbp)
.L11:
	movl	-28(%rbp), %eax
	cmpl	-20(%rbp), %eax
	jl	.L12
	movq	-40(%rbp), %rax
	addq	$2, %rax
	movq	-40(%rbp), %rdx
	addq	$2, %rdx
	movzwl	(%rdx), %edx
	addl	$2, %edx
	movw	%dx, (%rax)
	subl	$1, -24(%rbp)
.L8:
	cmpl	$0, -24(%rbp)
	jg	.L13
	movl	-20(%rbp), %edx
	movq	-40(%rbp), %rax
	movl	%edx, %esi
	movq	%rax, %rdi
	call	print
	movl	$0, %eax
	addq	$56, %rsp
	popq	%rbx
	leave
	ret
	.cfi_endproc
.LFE1:
	.size	main, .-main
	.section	.rodata
	.align 8
.LC2:
	.long	3161095930
	.long	1076532084

Google to acquire ITA ?

Posted by jgrant, 2010-06-29 20:51:17

Update 2010-06-30 : So just over a day after I posted this entry Google announced that they have acquired ITA. Announcement

There was buzz back in April about Google possibly acquiring ITA Software.
A few days ago Dan posted that these were just rumors based on a single Bloomberg article.
Well it seems that it may be more than just a rumor : The Wall Street journal now has an article regarding the potential acquisition.
The silence seems quite confirming : "Google declined to comment. ITA didn't respond to calls seeking comment.".
Also fairly interesting is that ITA uses a very similar combination of languages to what Google does : Python, C++, Java. Would this factor in Google's interest ?

Hopefully, if this does happen, the ITA Lisp hackers get a substantial financial reward for all their innovative work. Fingers crossed ...

Summer 2010 reading

Posted by jgrant, 2010-06-19 14:13:23

"Let over Lambda - 50 Years of Lisp" by Doug Hoyte
This one had been sitting on my bookshelf for almost a year.

"Let Over Lambda is one of the most hardcore computer programming books out there. Starting with the fundamentals, it describes the most advanced features of the most advanced language: COMMON LISP. The point of this book is to expose you to ideas that you might otherwise never be exposed to."

and

"Macros are what make lisp the greatest programming language in the world."

and

"If you are looking for a dry coding manual that re-hashes common-sense techniques in whatever langue du jour, this book is not for you. This book is about pushing the boundaries of what we know about programming."
"Only the top percentile of programmers use Lisp and if you can understand this book you are in the top percentile of Lisp programmers."

I'm sure that the author has received his fair share of derision for making statements like these and for his clear and well researched content showing how Lisp is the greatest programming language ever invented. It may come off as conceited to some, but he is right. He's also in good company with the greatest computer scientists ever known who have also made similarly bold statements regarding Lisp. This style is lacking in most technical writing today, there has been too much coddling and dilution in programming texts over the last decade. The fact is that unless you have mastered this language then you are in no position to even begin disussing this topic. This book, much like any of the posts on this site, is not for convincing the majority of Blub programmers that they should be using Lisp but to encourage a few that have an appreciation for the world's greatest programming language to look even deeper.
Here's a quote from the first chapter for those that might have known for a long while that there is more to programming than the hype of formal object systems that we've all been subjected to for the past few decades :

"Object systems are a formalisation of a subset of let and lambda combinations, sometimes with gimmicks like inheritance bolted on. Because of this, Lisp programmers often don't think in terms of classes and objects. Let and lambda are fundamental; objects and classes are derivatives. As Steele says, the 'object' need not be a primitive notion in programming languages. Once assignable value cells and good old lambda expressions are available, object systems are, at best, occasionally useful abstractions and, at worst, special-case and redundant."

Buy the book. Programming language choice matters.


"Introduction to Metamathematics" by Stephen Cole Kleene
Not much more needs to be said about this one.


"The Deniable Darwin and Other Essays" by David Berlinksi Ph.D
Michael W. Perry has this to say regarding the book :
"This book is an intriguing collection of essays on science and scientific topics written by Dr. Berlinski, the author of The Devil's Delusion: Atheism and its Scientific Pretensions. In the Introduction, he summarizes their underlying theme:

"My own view, repeated in virtually all of my essays, is that the sense of skepticism engendered by the sciences would be far more appropriately directed toward the sciences than toward anything else. It is not a view that the scientific community has ever encouraged. The sciences require no criticism, many scientists say, because the sciences comprise a uniquely self-critical institution, with questionable theories and theoreticians passing constantly before stern appellate review. Judgment is unrelenting. And impartial. Individual scientists may make mistakes, but like the Communist Party under Lenin, science is infallible because its judgments are collective. Critics are not only unwelcome, they are unneeded."

For those who believe that the present and fleeting 'consensus' among scientists is far from infallible, this book is a delightful feast of thought-stimulating ideas. Here's a list of the essays included:

---- 1996 ----
The Soul of Man Under Physics
The Deniable Darwin
Denying Darwin: David Berlinski & Critics
Keeping an Eye on Evolution
The End of Materialist Science
Full House Follies

---- 1998 ----
Gödel's Question
Was There a Big Bang?

---- 2001 ----
What Brings a World into Being?
Where Physics and Politics Meet

---- 2002 ----
God, Man and Physics
Einstein And Gödel: Friendship Between Equals
Lucky Jim
Stephen Jay Gould, 1942-2002: In Memoriam
Has Darwin Met His Match?

---- 2003 ----
Darwinism versus Intelligent Design: David Berlinski & Critics
Borges on Intelligent Design
A Scientific Scandal
A Scientific Scandal? David Berlinski & Critics
The Vampire's Heart

---- 2004 ----
On the Origins of the Mind

---- 2005 ----
All Those Darwinian Doubts
Academic Extinction
The Strength of Natural Selection in the Wild
An Open Letter to the Amazing Randi
Our Silent Partners
Copernicus Stages a Comeback

---- 2006 ----
On the Origins of Life

---- 2007 ----
Inside the Mathematical Mind

---- 2008 ----
Connecting Hitler and Darwin
The Scientific Embrace of Atheism

---- 2009 ----
The State of the Matter

Highly recommended!"


"The Stuff of Thought: Language as a Window into Human Nature" by Steven Pinker
From the Washington Post :
"Language comes so naturally to us that it's easy to believe there's some sort of intrinsic logic connecting the thing and its name, the signifier and the signified. In one of Plato's dialogues, a character named Cratylus argues that "a power more than human gave things their first names."

But Cratylus was wrong. Human language is an emanation of the human mind. A thing doesn't care what we call it. Words and their rules don't tell us about the world; they tell us about ourselves.

That's the simple premise behind Steven Pinker's latest work of popular science. According to the Harvard psychologist, people are "verbivores, a species that lives on words." If you want to understand how the brain works, how it thinks about space and causation and time, how it processes emotions and engages in social interactions, then you need to plunge "down the rabbit hole" of language. The quirks of our sentences are merely a portal to the mind.

In The Stuff of Thought, Pinker pitches himself as the broker of a scientific compromise between "linguistic determinism" and "extreme nativism." The linguistic determinists argue that language is a prison for thought. The words we know define our knowledge of the world. Because Eskimos have more nouns for snow, they are able to perceive distinctions in snow that English speakers cannot. While Pinker deftly discredits extreme versions of this hypothesis, he admits that "boring versions" of linguistic determinism are probably accurate. It shouldn't be too surprising that our choice of words can frame events, or that our vocabulary reflects the kinds of things we encounter in our daily life. (Why do Eskimos have so many words for snow? Because they are always surrounded by snow.) The language we learn as children might not determine our thoughts, but it certainly influences them.

Extreme nativism, on the other hand, argues that all of our mental concepts -- the 50,000 or so words in the typical vocabulary -- are innate. We are born knowing about carburetors and doorknobs and iPods. This bizarre theory, most closely identified with the philosopher Jerry Fodor, begins with the assumption that the meaning of words cannot be dissected into more basic parts. A doorknob is a doorknob is a doorknob. It only takes Pinker a few pages to prove the obvious, which is that each word is not an indivisible unit. The mind isn't a blank slate, but it isn't an overstuffed filing cabinet either.

So what is Pinker's solution? He advocates the middle ground of "conceptual semantics," in which the meaning of our words depends on an underlying framework of basic cognitive concepts. (As Pinker admits, he owes a big debt to Kant.) The tenses of verbs, for example, are shaped by our innate sense of time. Nouns are constrained by our intuitive notions about matter, so that we naturally parcel things into two different categories, objects and substances (pebbles versus applesauce, for example, or, as Pinker puts it, "hunks and goo"). Each material category comes with a slightly different set of grammatical rules. By looking at language from the perspective of our thoughts, Pinker demonstrates that many seemingly arbitrary aspects of speech, like that hunk and goo distinction, aren't arbitrary at all: They are byproducts of our evolved mental machinery.

Pinker tries hard to make this tour of linguistic theory as readable as possible. He uses the f-word to explore the topic of transitive and intransitive verbs. He clarifies indirect speech by examining a scene from "Tootsie," and Lenny Bruce makes so many appearances that he should be granted a posthumous linguistic degree. But profanity from Lenny Bruce can't always compensate for the cryptic vocabulary and long list of competing 'isms. Sometimes, the payoff can be disappointing. After a long chapter on curse words -- this book deserves an "explicit content" warning -- Pinker ends with the banal conclusion that swearing is "connected with negative emotion." I don't need conceptual semantics to tell me that.

The Stuff of Thought concludes with an optimistic gloss on the power of language to lead us out of the Platonic cave, so that we can "transcend our cognitive and emotional limitations." It's a nice try at a happy ending, but I don't buy it. The Stuff of Thought, after all, is really about the limits of language, the way our prose and poetry are bound by innate constraints we can't even comprehend. Flaubert was right: "Language is a cracked kettle on which we beat out tunes for bears to dance to, while all the time we long to move the stars to pity."