janmr blog The blog of Jan Marthedal Rasmussen 2021-01-24T00:00:00Z https://janmr.com/blog/ Jan Marthedal Rasmussen jan@janmr.com Rust and Iterator Adapters 2021-01-24T00:00:00Z https://janmr.com/blog/2021/01/rust-and-iterator-adapters/ Iterators are a big part of writing good, idiomatic Rust code. Creating an iterator is quite simple in that it requires you to implement the Iterator trait for a struct that holds the iterator's state. The Rust documentation does a good job of documenting how to do this. If we have an iterator adapter, that is, a function which take an Iterator and returns another Iterator, then Rust makes it possible to chain iterators together. But how do you implement your own iterator adapter and make it available as a method on any iterator? Here, the Rust documentation is much less explicit. The nth Bit of a Negative Number 2021-01-09T00:00:00Z https://janmr.com/blog/2021/01/nth-bit-of-negative-number/ Assume a positive integer is given and we wish to get the value of the nth bit of the number's two's complement. Now if a fixed number of bits is used to represent the number, say 32 or 64, the two's complement can be computed explicitly and the nth bit can be found directly. But if we work with arbitrary precision then any two's complement representation has infinitely many 1s at the left. Generating All Permutations 2020-06-14T00:00:00Z https://janmr.com/blog/2020/06/generating-all-permutations/ Python and Rust library routines for generating all permutations of a list of objects is mentioned, as well as an algorithm for lexicographic r-permutation generation (in both pseudo and Rust code) Leap Year Rules 2020-04-15T00:00:00Z https://janmr.com/blog/2020/04/leap-year-rules/ According to the The Astronomical Almanac, a tropical year comprises a complete cycle of seasons and is approximately 365 days, 5 hours, 48 minutes, 45 seconds, or 365.242188 days. Such a complete cycle of seasons could be measured as one solstice or equinox to the next corresponding solstice or equinox. The length of a tropical year, however, is not constant. For instance, the length of tropical years as measured from one March equinox to the next can vary up to 30 minutes. Wrapping HTML inside MathML 2017-02-23T00:00:00Z https://janmr.com/blog/2017/02/wrapping-html-inside-mathml/ MathML is a mathematical markup language that can be used to integrate math into web pages. Unfortunately, browser support is far from great. What people do instead is use libraries such as MathJax which can replace the math container with the appropriate HTML, either server-side or client-side. However, putting math markup in a structured way inside math elements has many advantages, such as accessibility and search engines. So let's put the HTML inside the math element, alongside the MathML. Tiling with L-Trominos 2016-01-24T00:00:00Z https://janmr.com/blog/2016/01/tiling-with-l-trominos/ An L-tromino is a figure in the plane made of three equal-sized squares connected in an L-shape. Consider now the following question: Given a 2^n x 2^n square grid with exactly one cell occupied, is it possible to tile the remaining area using L-trominos? Time Budgets for the Web 2015-04-26T00:00:00Z https://janmr.com/blog/2015/04/time-budgets-for-the-web/ I was recently introduced to the so-called RAIL principle in the Udacity MOOC Browser Rendering Optimization. It is an acronym for **R**esponsive, **A**nimation, **I**dle and **L**oad and introduces some time budgets to follow when creating a smooth and responsive web experience. It seems to have been a concept coined by the Google Chrome team and is also mentioned in a recent talk by Google's Paul Irish. [...] MathJax 2.4 vs 2.5 2015-03-08T00:00:00Z https://janmr.com/blog/2015/03/mathjax-2.4-vs-2.5/ MathJax version 2.5 was released around a month ago. One of that version's features were speed improvements and that's always a good thing. Seen in the light of my recent experiments with MathJax and KaTeX, it was straightforward to set up an experiment that compared MathJax versions 2.4 and 2.5 with respect to rendering speed. [...] Grouping Typesets With MathJax 2015-03-03T00:00:00Z https://janmr.com/blog/2015/03/grouping-typesets-with-mathjax/ When MathJax typesets the equations on a web page, it does a good job of grouping the work into chunks, so that a chunk of equations (see the EqnChunk option) will be typeset before they are displayed and the next chunk is processed. Typesetting and displaying one equation at a time leads to a lot of screen flickering and it also takes longer before the page is completed because of the increased work for the browser. Sometimes you want to typeset and display a lot of equations dynamically [...] Typesetting Math Using HTML and CSS: Fractions 2015-01-24T00:00:00Z https://janmr.com/blog/2015/01/typesetting-math-with-html-and-css-fractions/ Currently, there is no best way of showing math on the web. An HTML5 standard exists, MathML, but unfortunately it doesn't have broad browser support. Instead, many alternatives exist, all with varying quality and speed. I would like to explore how far you can get by using just HTML and CSS (including web fonts). My findings should be considered experimental. This post will deal with one way of typesetting fractions, inspired by the approach taken by Kahn Academy's KaTeX project. MathJax, KaTeX and a lot of Math 2015-01-11T00:00:00Z https://janmr.com/blog/2015/01/mathjax-katex-and-a-lot-of-math/ Prior to the current post, this blog contained 45 posts with a total of 2307 math items, where a math item is anything from single-letter variable identifiers to large, multi-line equations. That's an avarage of 51 math items per post, ranging from a few posts containing no math at all to one containing 267 items. From the beginning I have used MathJax to display the math [...] Entering the World of Web Components 2014-07-02T00:00:00Z https://janmr.com/blog/2014/07/entering-the-world-of-web-components/ I am very excited about Web Components. It is going to fundamentally change the way we do web development. This post is going to contain miscellaneous information and links related to Web Components. The specification is still being developed, but the overall parts have been decided upon. To quote Introduction to Web Components, Web Components consists of five main parts... Deriving the Closed Form for Square Pyramidal Numbers 2014-06-14T00:00:00Z https://janmr.com/blog/2014/06/deriving-closed-form-for-square-pyramidal-numbers/ The sum of the first n squares is s_n = 1/6 n (n+1) (2n+1). The numbers s_0, s_1, s_2, ... are called the square pyramidal numbers. Many different proofs exist. Seven different proofs can be found in Concrete Mathematics and even a visual proof has been published. One of the simplest proofs uses induction on n. This approach assumes that you know (or guess) the correct formula beforehand, though. This post will show a derivation which is a formalization of the derivation shown on wikipedia. Structure of a Multiple-Precision Library in C++ 2014-06-03T00:00:00Z https://janmr.com/blog/2014/06/structure-of-a-multiple-precision-library-in-cpp/ This post will present an overview of the implementation of Kanooth Numbers, a portable multiple-precision library in C++. Comparing Rational Numbers Without Overflow 2014-05-18T00:00:00Z https://janmr.com/blog/2014/05/comparing-rational-numbers-without-overflow/ Say you want to know if the inequality n_1/d_1 < n_2/d_2 is true (n_1, n_2, d_1, d_2 are all assumed to be positive integers). Of course, one could just multiply both sides with d_1 d_2, obtaining the equivalent n_1 d_2 < n_2 d_1, and we were done. But if our number representation allowed only numbers up to a certain size, say 32 bit unsigned integers, the multiplication could overflow. Of course, double-precision could be used to do the multiplication anyway, but this post will present a different method. The method effectively computes the continued fraction representation of each fraction simultaneously, but stops as soon as they differ. It is also the algorithm used for comparisons in the Boost C++ library Rational. Bresenham's Line Algorithm 2014-04-24T00:00:00Z https://janmr.com/blog/2014/04/bresenhams-line-algorithm/ In 1965 Jack Elton Bresenham published the paper Algorithm for computer control of a digital plotter in the IBM Systems Journal, volume 4, number 1. It explained how a line could be approximated on an integer grid. The algorithm is still used today as a rasterization technique for rendering lines on video displays or printers. As Bresenham's paper suggests, however, it was originally devised for a plotter, capable of moving from one grid point to one of the adjacent eight grid points. We consider drawing a line... Basic Multiple-Precision Long Division 2014-04-14T00:00:00Z https://janmr.com/blog/2014/04/basic-multiple-precision-long-division/ We consider the task of dividing a positive integer u by another positive integer v, thus obtaining a quotient q=u/v and a remainder r such that u = q v + r with 0 <= r < v. The method presented here is based on The Classical Algorithms, Section 4.3.1, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. The material is quite theory-heavy and if you are just looking for the main algorithm, you can skip to the bottom and Algorithm L. Six Circles Theorem Illustrated 2014-04-06T00:00:00Z https://janmr.com/blog/2014/04/six-circles-theorem-illustrated/ Given a triangle, start with a circle tangent to two sides. Then draw a new circle tangent to this first circle and a different pair of sides. Continue this process in the same direction. The sixth circle will be tangent to both the fifth and the first circle, thus producing a cyclic chain of touching circles. Archimedes' Twin Circles Illustrated 2014-04-03T00:00:00Z https://janmr.com/blog/2014/04/archimedes-twin-circles-illustrated/ The green circles will always be of equal size Thales' Theorem Illustrated 2014-04-02T00:00:00Z https://janmr.com/blog/2014/04/thales-theorem-illustrated/ Thales' Theorem: If A, B and C are points on a circle with the segment AC as a diameter, then the angle at B is a right angle. An Infinite Series Involving a Sideways Sum 2013-07-03T00:00:00Z https://janmr.com/blog/2013/07/infinite-series-involving-sideways-sum/ I found a recent question on Mathematics Stack Exchange quite interesting. It simply asked: How does one easily calculate ... Good Rational Bounds 2013-01-07T00:00:00Z https://janmr.com/blog/2013/01/good-rational-bounds/ Say we have a k-bit integer and we want to allocate a character array to hold the decimal digits of this number. How large must the array be? Well, the exact formula is [...] Basic Multiple-Precision Short Division 2012-11-28T00:00:00Z https://janmr.com/blog/2012/11/basic-multiple-precision-short-division/ Let us consider short division, by which we mean a multiple-digit number u divided by a single digit v [...] Basic Multiple-Precision Multiplication 2011-11-09T00:00:00Z https://janmr.com/blog/2011/11/basic-multiple-precision-multiplication/ After addressing multiple-precision addition and subtraction, we now turn to multiplication of two multiple-precision numbers. Once again, we use the number representation and notation introduced earlier. Several algorithms exist for doing multiple-precision multiplication. This post will present the basic, pencil-and-paper-like method. Basically, it consists of two parts: Multiplying a number by a single digit and adding together the sub-results, aligned appropriately. [...] Multiple-Precision Subtraction 2011-10-26T00:00:00Z https://janmr.com/blog/2011/10/multiple-precision-subtraction/ We now turn to multiple-precision subtraction for non-negative integers. The algorithm is very similar to that of multiple-precision addition, but some minor differences make it worth while considering subtraction separately. [...] Multiple-Precision Addition 2011-10-12T00:00:00Z https://janmr.com/blog/2011/10/multiple-precision-addition/ This post will cover a basic addition algorithm for multiple-precision non-negative integers. The algorithm is based upon that presented in Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. The notation and bounds used in this post were presented in a previous post. We consider adding two n-digit numbers [...] Multiple-Precision Number Representation 2011-10-05T00:00:00Z https://janmr.com/blog/2011/10/multiple-precision-number-representation/ Let us consider a common way to represent non-negative integers. An integer u >= 0 will be represented in radix b >= 2 using the notation [...] Bell Numbers 2011-06-23T00:00:00Z https://janmr.com/blog/2011/06/bell-numbers/ I recently studied a system of linear ODEs, where n parameters, [...] described the system. It turned out that the structure of the solutions depended on whether any of the parameters where equal to each other. For instance, with three parameters there were five possibilities: [...] We can quickly go through small values of n and we get (starting with n=0): 1, 1, 2, 5, 15, .... How do we obtain a general formula? [...] Going Functional 2011-05-31T00:00:00Z https://janmr.com/blog/2011/05/going-functional/ Imperative programming languages--such as C++, Java, Perl and assembly are by far the most common. They all lie fairly close to the underlying computer architecture by executing one statement at a time, changing a state along the way. They describe how to compute something. Purely functional languages--such as Erlang and Haskell--have no state, only values, expressions and functions. All variables are immutable, that is, when a value has been assigned to a variable, it can never change. Purely functional programming languages describe what to compute, but not explicitly how. The Crossed Ladders Problem 2011-03-27T00:00:00Z https://janmr.com/blog/2011/03/crossed-ladders-problem/ I was recently reminded of the crossed ladders problem. The following simple figure should be adequate in defining the problem: [...]. If you haven't seen the problem before, I highly recommend trying to solve it before reading on. Fast Evaluation of Fibonacci Numbers 2011-03-11T00:00:00Z https://janmr.com/blog/2011/03/evaluation-of-fibonacci-numbers/ The integer sequence 0, 1, 1, 2, 3, 5, 8, 13, ... is well known as the Fibonacci sequence. It is easily defined by F_0 = 0, F_1 = 1 and F_n = F_{n-1} + F_{n-2} for n >= 2. To compute F_n you could use this definition directly, but that leads to a highly inefficient algorithm that is both recursive and which uses a number of additions which grows exponentially with n. Stackexchange Lists 2011-02-03T00:00:00Z https://janmr.com/blog/2011/02/stackexchange-lists/ Stack Exchange is a network of free, community-driven Q&A sites (in their own words). There are a lot of them and more are coming. The most relevant of them, in relation to this blog, are probably MathOverflow, Mathematics, Theoretical Computer Science, and StackOverflow. I recently looked through those sites for interesting questions tagged big-list. These questions typically encourage many different answers. I recommend the following: Evaluation of Powers 2011-01-30T00:00:00Z https://janmr.com/blog/2011/01/evaluation-of-powers/ How do you efficiently compute x^n for a positive integer n? Take x^{15} as an example. You could take x and repeatedly multiply by x 14 times. A better way to do it, however, is this: [...] Where Did pi Come From? 2011-01-09T00:00:00Z https://janmr.com/blog/2011/01/where-did-pi-come-from/ [...] where did that pi come from? What do trees have to do with pi? That was the subject of Donald E. Knuth's 16th Annual Christmas Tree Lecture, given on December 6, 2010. Prime Factors of Factorial Numbers 2010-10-30T00:00:00Z https://janmr.com/blog/2010/10/prime-factors-of-factorial-numbers/ Factorial numbers, n! = 1 * 2 * ... * n, grow very fast with n. In fact, n! ~ sqrt{2 pi n} (n/e)^n according to Stirling's approximation. The prime factors of a factorial number, however, are all relatively small, and the complete factorization of n! is quite easy to obtain. Computing the Integer Binary Logarithm 2010-09-27T00:00:00Z https://janmr.com/blog/2010/09/computing-the-integer-binary-logarithm/ The binary logarithm, or the logarithm to the base 2, of a number x > 0 is the number y = log_2 x such that 2^y = x. This article looks at how we can determine the integer part of the binary logarithm using integer arithmetic only. Naturally, the binary logarithm is especially easy to work with on (binary) computers and bitwise operations come in handy. C++ Templates and Usual Arithmetic Conversions 2010-08-28T00:00:00Z https://janmr.com/blog/2010/08/cpp-templates-usual-arithmetic-conversions/ If you add a short int and a char in C++, what is the resulting type? What if you subtract a long int from an unsigned int? The answers actually depend on the compiler and the target architecture (int or unsigned in the first case and long int or unsigned long int in the second). This article lists the rules from the current C++ standard and gives an example of how the type can be resolved at compile time using templates. Bitwise Operators and Negative Numbers 2010-07-24T00:00:00Z https://janmr.com/blog/2010/07/bitwise-operators-and-negative-numbers/ When representing integers using a fixed number of bits, negative numbers are typically represented using two's complement. If using n bit numbers, the two's complement of a number x with 0 <= x < 2^n is (-x) mod 2^n = 2^n - x. But what do you do if you want to work with unbounded/multiple-precision integers? [...] Book Review: The Book of Numbers 2010-05-23T00:00:00Z https://janmr.com/blog/2010/05/book-review-the-book-of-numbers/ 'The Book of Numbers' is a wonderful book about, well, numbers. And lots of them. From ancient ways of writing numbers to Gaussian integers to surreal numbers. The authors are some tough mathematicians, too. John H. Conway is Professor of Mathematics at Princeton University, an authority in game theory and group theory, and the inventor of the Game of Life and surreal numbers. Richard K. Guy is professor emeritus of mathematics at the University of Calgary and has (co)authored several hundred publications on combinatorial game theory, number theory and graph theory. Arithmetic by Geometry 2010-04-24T00:00:00Z https://janmr.com/blog/2010/04/arithmetic-by-geometry/ Today real numbers are most often represented by applying (elementary) functions to (decimal) integers. Throughout history, though, arithmetic and propositions involving (positive) real numbers were often considered from a purely geometrical point of view. Real numbers were identified by the length of some line segment and, e.g., the product of two numbers was identified by the area of a rectangle with side-lengths equal to the two numbers. This made sense from a physical/applied point of view, but it had certain shortcomings. Line-line Intersection in the Plane 2010-03-30T00:00:00Z https://janmr.com/blog/2010/03/line-line-intersection/ How do you calculate the point where two lines in the plane intersect? It is not very hard to do, but the formula can look quite complicated, depending on how you write it up. This article is a reminder that it can be expressed in a simple manner. Visualizing the Pythagorean Theorem 2010-02-14T00:00:00Z https://janmr.com/blog/2010/02/visualizing-the-pythagorean-theorem/ Most people are familiar with the Pythagorean theorem: In a right-angled triangle the square of the hypotenuse is equal to the sum of the squares of the other two sides. As the name of the theorem implies, it is attributed to Pythagoras, a Greek mathematician who lived around 500 B.C. The theorem is also included in Euclid's Elements, an encyclopedia of all known mathematics around 300 B.C. But how do you actually prove the Pythagorean theorem? Fractions and Circles 2010-02-06T00:00:00Z https://janmr.com/blog/2010/02/fractions-and-circles/ Fractions produced by mediants have some very interesting properties. We saw some of them in connection with the Stern-Brocot tree. This articles explores a more curious property, relating fractions to circles in the plane. It was discovered in 1938 by Lester R. Ford and is also mentioned in Conway and Guy's The Book of Numbers. Book Review: Prime Obsession 2010-01-09T00:00:00Z https://janmr.com/blog/2010/01/book-review-prime-obsession/ 'Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics' is a book about the Riemann Hypothesis, posed by Bernhard Riemann in 1859. As the book title says, it is one of the greatest unsettled mathematical conjectures remaining today. It is among David Hilbert's list of twenty-three mathematical problems and one of the seven millennium problems presented by the Clay Mathematics Institute. The Stern-Brocot Tree of Fractions 2009-12-04T00:00:00Z https://janmr.com/blog/2009/12/the-stern-brocot-tree-of-fractions/ Consider two fractions m_1/n_1 and m_2/n_2 with positive numerators and denominators. The fraction (m_1+m_2)/(n_1+n_2) is called the mediant of m_1/n_1 and m_2/n_2. It is straightforward to show that the mediant is placed numerically between the original fractions, Book review: The Pleasures of Counting 2009-11-15T00:00:00Z https://janmr.com/blog/2009/11/book-review-the-pleasures-of-counting/ The Pleasures of Counting is a book about people working with mathematics and challenges they have faced. The book has 544 pages with a total of 19 chapters and 3 appendices. It contains a lot of material and is split into five parts: The uses of abstraction, Meditations on measurement, The pleasures of computation, Enigma variations, and The pleasures of thought. Continued Fractions and Continuants 2009-11-10T00:00:00Z https://janmr.com/blog/2009/11/continued-fractions-and-continuants/ We will be considering continued fractions of the form [...] Computing the Greatest Common Divisor 2009-10-29T00:00:00Z https://janmr.com/blog/2009/10/computing-the-greatest-common-divisor/ The greatest common divisor of two integers is the largest positive integer that divides them both. This article considers two algorithms for computing gcd(u,v), the greatest common divisor of u and v [...] Remembering Trigonometric Addition Formulas 2009-09-23T00:00:00Z https://janmr.com/blog/2009/09/remembering-trigonometric-addition-formulas/ The addition formulas for sine and cosine look like this: [...] I can never remember them. [...] Useful Properties of the Floor and Ceil Functions 2009-09-09T00:00:00Z https://janmr.com/blog/2009/09/useful-properties-of-the-floor-and-ceil-functions/ This articles explores some basic properties of the integer functions commonly known as floor and ceil. Most of the statements may seem trivial or obvious, but I, for one, have a tendency to forget just how exact you can be when it comes to expressions/equations where floor or ceil functions appear. On the Divergence of a Geometric Progression Sum 2009-08-28T00:00:00Z https://janmr.com/blog/2009/08/on-the-divergence-of-a-geometric-progression-sum/ Let us revisit the geometric progression sum considered in an earlier article, s_r = sum_{k=0}^infty r^k = 1 + r + r^2 + r^3 + ..., where r here is a complex number. For what values of r does this infinite sum make sense? [...] Implementing Multiple-Precision Arithmetic, Part 2 2009-08-20T00:00:00Z https://janmr.com/blog/2009/08/implementing-multiple-precision-arithmetic-part-2/ This article is a follow-up to part 1 where multiple-precision addition, subtraction, and multiplication for non-negative integers was discussed. This article deals with division. Again, the theoretic foundation is based on Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth. Implementing Multiple-Precision Arithmetic, Part 1 2009-07-23T00:00:00Z https://janmr.com/blog/2009/07/implementing-multiple-precision-arithmetic-part-1/ This article is the first in a series dealing with algorithms for multiple-precision arithmetic. The goal is to present both a theoretical foundation with high-level algorithm descriptions (based on Section 4.3.1, The Classical Algorithms, of The Art of Computer Programming, Volume 2, by Donald E. Knuth) and a portable C++ implementation of the algorithms. The theory and high-level algorithms will be quite universal and generic, whereas the presented code will be just one way to implement the algorithms in a specific programming language. The Game of Nim 2009-04-20T00:00:00Z https://janmr.com/blog/2009/04/the-game-of-nim/ I have known the game of Nim for many years. Once, a friend of mine beat me repeatedly in one game after another and I had no idea how he did it. Looking back, I am not sure he knew the perfect Nim-strategy, but he knew enough to frustrate me immensely. A year ago or so, I was flicking through Fascicle 1 of The Art of Computer Programming, Volume 4 by Donald E. Knuth, and I read about the strategy of Nim. The strategy is very simple but I could not possibly understand why it worked. This article shows why the strategy works, introducing the necessary game theory along the way. [...] Twelve Ways of Counting 2008-12-26T00:00:00Z https://janmr.com/blog/2008/12/twelve-ways-of-counting/ I have for a long time had an ambition of getting better at combinatorics, especially enumerative combinatorics, the discipline of counting the number of arrangements, given some pattern. Getting introduced to The Twelvefold Way was a real eye-opener in this regard. It is a way to categorize some fundamental combinatorial counting problems by considering different ways of putting balls into urns. Different setups arise depending on whether the balls are labeled or unlabeled, whether the urns are labeled or unlabeled, and whether each urn can contain any number of balls, at most one or at least one, leading to 2*2*3 = 12 cases. [...] Nice Proof of a Geometric Progression Sum 2008-10-08T00:00:00Z https://janmr.com/blog/2008/10/nice-geometric-progression-proof/ Consider the geometric series, s_r = sum_{k=0}^infty r^k = 1 + r + r^2 + r^3 + ..., for 0 < r < 1. The goal is to find a closed-form expression for s_r. [...]