I recently collaborated with Boris Alexeev, Evan Conway, Matthieu Rosenfeld, Andrew Sutherland, Terence Tao, and Markus Uhr on a problem posed in this blog post by Tao, which has now culminated in a joint paper. While the paper and posts give a more detailed treatment, I wanted … Continue reading The Guy-Selfridge Conjecture
Author: Kevin Ventullo
Fast Exact Integer Roots
Suppose you knew that 9,273,284,218,074,431 was a perfect 7th power. How would you compute the 7th root? This is a long overdue sequel to the previous post, in which the author promised to derive an efficient algorithm for computing exact k-th roots of integers. That … Continue reading Fast Exact Integer Roots
2-adic Logarithms and Fast Exponentiation
In this post, we're going to investigate an underexplored bridge between computer science and algebraic number theory. To motivate it, consider the analogy between floating point arithmetic and the theoretical real numbers. While floating points can only approximate the precision of a real number, much … Continue reading 2-adic Logarithms and Fast Exponentiation
Hashing Unordered Sets: How Far Will Cleverness Take You?
(Or: Enforced Algebraic Structure of Commutative Accumulative Hash Functions) While there are several documented approaches to defining a hash function for lists and other containers where iteration order is guaranteed, there seems to be less discussion around best practices for defining a hash function for … Continue reading Hashing Unordered Sets: How Far Will Cleverness Take You?
Kevin Ventullo 