Elements of Programming

Author: Alexander A. Stepanov, Paul McJones
All Hacker News 7
This Year Hacker News 2
This Month Stack Overflow 1


by anonymous   2019-07-21

There are certainly ways to compute integral powers of 10 faster than using std::pow()! The first realization is that pow(x, n) can be implemented in O(log n) time. The next realization is that pow(x, 10) is the same as (x << 3) * (x << 1). Of course, the compiler knows the latter, i.e., when you are multiplying an integer by the integer constant 10, the compiler will do whatever is fastest to multiply by 10. Based on these two rules it is easy to create fast computations, even if x is a big integer type.

In case you are interested in games like this:

  1. A generic O(log n) version of power is discussed in Elements of Programming.
  2. Lots of interesting "tricks" with integers are discussed in Hacker's Delight.
by earthicus   2018-12-19
Thanks for stopping by! I'd like to ask a question / make a request. Unlike most of the people here, I was trained in mathematics but am just learning how to program, so I was wondering if you had any desire to expand the online algorithms material. In particular the 'generic programming' technique illustrated by Alexander Stepanov in these lectures (Four Algorithmic Journeys) [1] and book [2] caught my attention. He takes a simple number theoretic algorithm, considers what properties are required for it to work, then generalizes it and applies it in other useful and surprising cases.

For example, Stepanov starts with the problem of multiplying two integers n * m using the Ancient Egyptian Multiplication algorithm from the Rhind Papyrus (which runs in log n if i remember correctly), then observes the only property needed for the algorithm is associativity, so that it can run on any semi-group: mult(n,s) is n repetitions of the semi-group element s, using the semi-group operation. Useful and surprising applications are (1) matrix exponentiation to solve systems of linear recurrences in log n steps (no stupid Fibonacci implementation here!), and (2) encode a graph in your matrix, with elements in a tropical semi-ring, then matrix exponentiation solves shortest path. Not too bad for a 4,000 year old multiplication algorithm.

A second example is the euclidean algorithm, which he extends first to polynomials following Stevin, then to Gaussian integers, then to euclidean domains. A surprising application was to permutation algorithms managing memory.

Anyhow, I think it would be really cool if you showed these kind of applications of number-theoretic algorithms as well as the cryptography stuff. Unfortunately basically all of the modern algorithms literature seems to avoid even the tiniest hint of abstraction; it makes the subject so much harder to hold in your head! So providing a new set of examples that is more accessible than Stepanov would be doing the world a great service, i think.

[1] https://www.amazon.com/Elements-Programming-Alexander-Stepan...

by davidmathers   2017-08-20
He has a book now, Elements of Programming: http://www.amazon.com/dp/032163537X/
by limist   2017-08-20
@jhck, drothlis: Thank you very much to both of you, those suggestions are exactly what was asked for. I'd upvote you more if I could. :)

Both the Gries book and Stepanov's book have really impressive reviews on Amazon, am looking forward to diving into them.



by adamnemecek   2017-08-19
I'll give you a couple. Note that some of these are rehashes of my earlier comments.

# Elements of Programming


This book proposes how to write C++-ish code in a mathematical way that makes all your code terse. In this talk, Sean Parent, at that time working on Adobe Photoshop, estimated that the PS codebase could be reduced from 3,000,000 LOC to 30,000 LOC (=100x!!) if they followed ideas from the book https://www.amazon.com/Grammar-Graphics-Statistics-Computing...

This book changed my perception of creativity, aesthetics and mathematics and their relationships. Fundamentally, the book provides all the diverse tools to give you confidence that your graphics are mathematically sound and visually pleasing. After reading this, Tufte just doesn't cut it anymore. It's such a weird book because it talks about topics as disparate Bayesian rule, OOP, color theory, SQL, chaotic models of time (lolwut), style-sheet language design and a bjillion other topics but always somehow all of these are very relevant. It's like if Bret Victor was a book, a tour de force of polymathical insanity.

The book is in full color and it has some of the nicest looking and most instructive graphics I've ever seen even for things that I understand, such as Central Limit Theorem. It makes sense the the best graphics would be in the book written by the guy who wrote a book on how to do visualizations mathematically. The book is also interesting if you are doing any sort of UI interfaces, because UI interfaces are definitely just a subset of graphical visualizations.

# Scala for Machine Learning


This book almost never gets mentioned but it's a superb intro to machine learning if you dig types, scalable back-ends or JVM.

It’s the only ML book that I’ve seen that contains the word monad so if you sometimes get a hankering for some monading (esp. in the context of ML pipelines), look no further.

Discusses setup of actual large scale ML pipelines using modern concurrency primitives such as actors using the Akka framework.

# Hands-On Machine Learning with Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques for Building Intelligent Systems


Not released yet but I've been reading the drafts and it's a nice intro to machine learning using modern ML frameworks, TensorFlow and Scikit-Learn.

# Basic Category Theory for Computer Scientists


Have you ever wondered what's the relationship between machine learning and logic? If so look no further.

# Machine Learning: A Probabilistic Perspective (Adaptive Computation and Machine Learning series)


Even though this is an Erlang book (I don't really know Erlang), 1/3 of the book is devoted to designing scalable and robust distributed systems in a general setting which I found the book worth it on it's own.

# Practical Foundations for Programming Languages


Up until recently I didn't know the difference between graphs and networks. But look at me now, I still don't but at least I have a book on it.