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:
A generic O(log n) version of power is discussed in Elements of Programming.
Lots of interesting "tricks" with integers are discussed in Hacker's Delight.
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.
There are certainly ways to compute integral powers of 10 faster than using
std::pow()! The first realization is thatpow(x, n)can be implemented in O(log n) time. The next realization is thatpow(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 ifxis a big integer type.In case you are interested in games like this:
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...
Both the Gries book and Stepanov's book have really impressive reviews on Amazon, am looking forward to diving into them.
http://www.amazon.com/Science-Programming-Monographs-Compute...
http://www.amazon.com/Elements-Programming-Alexander-Stepano...
It proposes how to write C++-ish (it's an extremely minimal subset of C++ proper) 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.youtube.com/watch?v=4moyKUHApq4&t=39m30s Another point of his is that the explosion of written code we are seeing isn't sustainable and that so much of this code is algorithms or data structures with overlapping functionalities. As the codebases grow, and these functionalities diverge even further, pulling the reigns in on the chaos becomes gradually impossible. Bjarne Stroustrup (aka the C++ OG) gave this book five stars on Amazon (in what is his one and only Amazon product review lol). https://smile.amazon.com/review/R1MG7U1LR7FK6/
This style might become dominant because it's only really possible in modern successors of C++ such as Swift or Rust that have both "direct" access to memory and type classes/traits/protocols, not so much in C++ itself (unless debugging C++ template errors is your thing).
# Elements of Programming
https://www.amazon.com/Elements-Programming-Alexander-Stepan...
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
https://www.amazon.com/Scala-Machine-Learning-Patrick-Nicola...
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
https://www.amazon.com/Hands-Machine-Learning-Scikit-Learn-T...
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
https://www.amazon.com/Markov-Logic-Interface-Artificial-Int...
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)
https://www.amazon.com/Designing-Scalability-Erlang-OTP-Faul...
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
https://www.amazon.com/First-Course-Network-Theory/dp/019872...
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.