π 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 HoyteThis 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."
So you say that programming language choice does not matter ...
Posted by jgrant, 2010-06-16 23:30:07
One popular interview question that never dies : write some code to reverse a singly linked-list.
Now understanding the problem for interviewees is one thing but getting it right in an imperative language seems to be quite a feat based on my experience as an interviewer. Most take 15-20 minutes to get this completely correct and sometimes even longer.
Here's a quick solution that took me 10 minutes (in C) :
The code is fairly straight-forward for anyone familiar with C. Think about it though, when someone is under pressure to answer this question and they are coding this up on paper for the interviewer there are about 50 lines of code in which the interviewee can go wrong.
This is the imperative paradigm that most programmers live with on a daily basis and which they need to prove they can deal with in many interviews every day around the world. To make it worse this is also the only paradigm that most interviewers really know.
Now the equivalent in a functional language is a one-liner (in Clojure) :
So at the low-level of a developer's daily life experience with imperative languages, how many programming bugs happen as a result ? What about lost time and the individual productivity ?
Moving up a level : what does this do to the team's productivity ? What is the 'new feature vs. fire drill' ratio for this team that is forced to worship at the altar of imperative languages by academia and industry ?
Now on the macro level translate all this into costs in time and lost revenue for a company. What is the estimated percentage of lost revenue and profit due to being stuck with this paradigm ?
Middle-management's sales-pitchy MBA approach to software developer fungibility and hence their love of lowest common denominator languages costs companies untold losses in the millions. They have also been much of the cause for a generation of below-average programmers.
(The cancer that is the MBA club in the world of software development is a topic for another essay).
Language matters at all levels.
Here's a quick solution that took me 10 minutes (in C) :
#define LIST_SIZE 10000000
#define SHOW_SIZE 5
typedef struct node {
struct node* next;
int val;
} node;
int main(int argc, char* argv[])
{
int i;
long start, end;
node* head = malloc(sizeof(node));
node* cur = head; node* cur2 = head;
node* prev = NULL; node* next = NULL;
// init linked list
printf(" linked list : ");
for (i=1; i <= LIST_SIZE; i++)
{
cur->val = i;
if (i < SHOW_SIZE) printf("%d -> ", cur->val);
if (i != LIST_SIZE) cur->next = malloc(sizeof(node));
cur = cur->next;
}
cur = NULL;
printf(" ... (%d more)\n", LIST_SIZE - SHOW_SIZE);
// reverse linked list
start = clock();
while (cur2 != NULL)
{
next = cur2->next;
cur2->next = prev;
prev = cur2;
cur2 = next;
}
node* head2 = prev;
end = clock();
printf("reversed linked list : ");
for (i=1; i <= LIST_SIZE; i++)
{
if (i < SHOW_SIZE) printf("%d -> ", head2->val);
head2 = head2->next;
}
printf(" ... (%d more)\n", LIST_SIZE - SHOW_SIZE);
printf("Elapsed time: %.3lf msecs\n", (double)(end - start));
}
The code is fairly straight-forward for anyone familiar with C. Think about it though, when someone is under pressure to answer this question and they are coding this up on paper for the interviewer there are about 50 lines of code in which the interviewee can go wrong.
This is the imperative paradigm that most programmers live with on a daily basis and which they need to prove they can deal with in many interviews every day around the world. To make it worse this is also the only paradigm that most interviewers really know.
Now the equivalent in a functional language is a one-liner (in Clojure) :
(let [nums (range 1 1e6)]
(time (take 5 (reduce (fn [rlst item] (cons item rlst)) '() nums))))
So at the low-level of a developer's daily life experience with imperative languages, how many programming bugs happen as a result ? What about lost time and the individual productivity ?
Moving up a level : what does this do to the team's productivity ? What is the 'new feature vs. fire drill' ratio for this team that is forced to worship at the altar of imperative languages by academia and industry ?
Now on the macro level translate all this into costs in time and lost revenue for a company. What is the estimated percentage of lost revenue and profit due to being stuck with this paradigm ?
Middle-management's sales-pitchy MBA approach to software developer fungibility and hence their love of lowest common denominator languages costs companies untold losses in the millions. They have also been much of the cause for a generation of below-average programmers.
(The cancer that is the MBA club in the world of software development is a topic for another essay).
Language matters at all levels.
